算法设计（二）

1.归并排序

介绍

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

算法实现

package com.practice.java;import java.util.Scanner;
public class Example1 {//合并子序列static void Merge(int c[],int left,int mid,int right){int [] d = new int[right - left + 1];int i,j,k=0,cunt;i = left;j = mid + 1;while (i <= mid && j <= right) {if (c[i] <= c[j]) {d[k++] = c[i++];} else {d[k++] = c[j++];}}//前子序列先结束while(j <= right) {d[k++] = c[j++];}//后子序列先结束while(i <= mid) {d[k++] = c[i++];}for(cunt = 0,i = left;i <= right;cunt++,i++) {c[i] = d[cunt];}}//划分子序列static void MergeSort(int a[],int left,int right) {if(left<right) {int mid = (left + right) / 2;MergeSort(a,left,mid);MergeSort(a,mid + 1,right);for(int i = 0;i < right+1;i++) {System.out.print(a[i] +" ");}System.out.println();Merge(a,left,mid,right);}}public static void main(String[] args) {int n,i;System.out.print("请输入数组的规模：");Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int [] num = new int[n];System.out.print("请输入要排序" + n + "的个元素： ");for(i = 0;i < n;i++) {num[i] = scanner.nextInt();}System.out.print("排序前" + n + "的个元素：");for(i = 0;i < n;i++) {}System.out.println();MergeSort(num,0,n-1);System.out.print("排序后" + n + "的个元素：");for(i = 0;i < n;i++) {System.out.print(num[i] +" ");}scanner.close();}}

2.快速排序

介绍

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

算法实现

package com.practice.java;import java.util.Scanner;public class Example2 {public static int partion(int num[],int left,int right) {int i = left,j = right + 1;do {do i++;while(num[i] < num[left]);do j--;while(num[j] > num[left]);if(i < j) {int t = num[i];num[i] = num[j];num[j] = t;}}while(i < j);//i>j时，交换分界元素与主元int t = num[left];num[left] = num[j];num[j] = t;return j;}public static void quickSort(int num[],int x,int y) {if(x < y) {int m = partion(num,x,y);quickSort(num,x,m - 1);quickSort(num,m + 1,y);}}public static void main(String[] args) {int n,i;System.out.print("请输入数组的规模：");Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int [] num = new int[n];System.out.print("请输入要排序" + n + "的个元素： ");for(i = 0;i < n;i++) {num[i] = scanner.nextInt();}System.out.print("排序前" + n + "的个元素：");for(i = 0;i < n;i++) {System.out.print(num[i] +" ");}System.out.println();quickSort(num,0,n-1);System.out.print("排序后" + n + "的个元素：");for(i = 0;i < n;i++) {System.out.print(num[i] +" ");}scanner.close();}}

3.折半查找

介绍

折半查找法是效率较高的一种查找方法。
假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，
其基本思想是：设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；
1如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高

算法实现

package com.practice.java;import java.util.Scanner;
public class Example3 {static int chack(int[] a,int low,int high,int key) {if(high - low == 0) {if(key == a[low]) {return low + 1;}else {return -1;}}else {int mid = (high + low) / 2;if(a[mid] == key) {return mid + 1;}else {if(key < a[mid]) {return chack(a,low,mid,key);}else {return chack(a,mid + 1,high,key);}}}}public static void main(String[] args) {int[] a = {-7,-2,0,15,27,54,80,88,102};//查找值int key;System.out.print("请输入查找的数字：");Scanner scanner = new Scanner(System.in);key = scanner.nextInt();System.out.println("查找到返回key在数组中的位置 || 找不到返回-1");System.out.println(chack(a,0,8,key));	scanner.close();}}

4.选择问题

介绍

选择问题是求一个n个数列表的第k个最小元素的问题。这个数字被称为第k个顺序统计量。当然，对于k=1或者k=n的情况，我们可以扫描整个列表，找出最小或者最大的元素。对于其他情况，我们可以对列表进行排序，然后返回第k个元素。

算法实现

package com.practice.java;import java.util.Scanner;
public class Example4 {public static int partion(int num[],int left,int right) {int i = left,j = right + 1,t;do {do i++;while(num[i] < num[left]);do j--;while(num[j] > num[left]);if(i < j) {t = num[i];num[i] = num[j];num[j] = t;}}while(i < j);//i>j时，交换分界元素与主元t = num[left];num[left] = num[j];num[j] = t;return j;}static int select(int[] a,int left,int right,int key) {int j;j = partion(a,left,right);if(key == (j -left + 1)) {return a[j];}else {if(key > j -left + 1) {return select(a,j+1,right,key - (j -left + 1));}else {return select(a,left,j - 1,key);}}}public static void main(String[] args) {int[] a = {41,76,55,19,59,63,12,47,67};//查找第几小的数int key;System.out.print("请输入查找第几小的数字：");Scanner scanner = new Scanner(System.in);key = scanner.nextInt();System.out.println("查找到返回在数组中对应的数 || 超出查找范围返回-1");System.out.println(select(a,0,8,key));	scanner.close();}
}

5.最大字段求和

介绍

给出一些数，计算这些数能达到的最大值

算法实现

package com.practice.java;
public class Example5 {static int maxsum(int a[],int left,int right) {int maxsum,mid,leftsum,rightsum,midsum,i,j;if(left == right) {return left;}else {mid = (left + right) / 2;leftsum = maxsum(a,left,mid);rightsum = maxsum(a,mid + 1,right);int leftsum1 = 0;int lefts = 0;for(i = mid;i >= left;i--) {lefts = lefts + a[i];if(lefts > leftsum1) {leftsum1 = lefts;}}int rightsum1 = 0;int rights = 0;for(j = mid + 1;j <= right;j++) {rights = rights + a[j];if(rightsum1 < rights) {rightsum1 = rights;}}midsum = leftsum1 +rightsum1;maxsum = rightsum;maxsum = (rightsum > midsum)? rightsum:midsum;maxsum = (maxsum > leftsum)?maxsum:leftsum;return maxsum;}}public static void main(String[] args) {int a[] = {-5,11,-4,13,-4,-2};System.out.println("最大字段和为：" + maxsum(a,0,5));}}

6.棋盘覆盖问题

介绍

将含有特殊方格且具有一定规格的棋盘用各种 L 型方格覆盖

算法实现

package com.practice.java;import java.util.Scanner;
public class Example6 {static int title = 1;//记录骨牌的型号static int [][] board = new int[20][20];//存储棋盘被覆盖的情况static void ChessBoard(int tr,int tc,int dr,int dc,double size) {int t = 0;int s;if(size == 1)return;t = title++;s = (int) (size / 2);//划分棋盘//覆盖左上角棋盘if(dr < (tr+s) && dc < (tc+s)) {//特殊方格在棋盘左上角ChessBoard(tr,tc,dr,dc,s);}else {board[tr + s - 1][tc + s -1] = t;ChessBoard(tr,tc,tr + s - 1,tc + s - 1,s);}//覆盖右上角棋盘if(dr<tr+s && dc >= tc+s) {ChessBoard(tr,tc+s,dr,dc,s);}else {board[tr + s - 1][tc + s] = t;ChessBoard(tr,tc + s,tr + s - 1,tc + s,s);}//覆盖左下角棋盘if(dr >= tr+s && dc < tc+s) {ChessBoard(tr+s,tc,dr,dc,s);}else {board[tr + s][tc + s - 1] = t;ChessBoard(tr+s,tc,tr+s,tr+s-1,s);}//覆盖右下角棋盘if(dr >= tr+s && dc >= tc+s) {ChessBoard(tr+s,tc+s,dr,dc,s);}else {board[tr + s][tc + s] = t;ChessBoard(tr+s,tc+s,tr+s,tr+s,s);}}public static void main(String[] args) {int k,x,y,i,j;Scanner scanner = new Scanner(System.in);System.out.println("请输入棋盘的规模K(2**k)：");k = scanner.nextInt();System.out.println("请输入特殊方格的下标x,y：");x = scanner.nextInt();y = scanner.nextInt();ChessBoard(0,0,x,y,Math.pow(2,k));for(i = 0;i < Math.pow(2,k);i++) {for(j = 0;j < Math.pow(2,k);j++) {System.out.print(board[i][j] + " ");}System.out.println();}scanner.close();}
}