算法设计（二）
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();
}
}