第二章：排序算法 及其他 Java代码实现
——算法导论（Introduction to Algorithms, Third Edition）
插入排序
//打印输出数组模块
public class PrintArrays
{
public static void printA(int []A)
{
for (int aInput : A)
{
System.out.print(aInput+ " ");
}
}
}
//产生随机数组模块
import java.util.*;
public class RandomArray
{
public static int[] randomArray( int num)
{
Random rad =new Random(System.currentTimeMillis());
int array[] = new int[num];
for (int i= 0 ; i<num ; i++)
{
array[i] = rad.nextInt(100);
}
return array;
}
}
//正常循环迭代实现
public class InsertSort02
{
public static void main(String args[])
{
int A[] = {1,9,6,8,4,5,3,7,2,0};
for (int j= 0; j<A.length-1 ; j++)
{
int key =A[j+1] ;
int i= j;
//关键性插入
while ((i >= 0)&&(key< A[i]))
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}
PrintArrays.printA(A);
}
}
//递归实现
public class InsertSort03
{
public static void main(String srgs[])
{
//产生随机数组
int A[] =RandomArray.randomArray(8);
insertSort(A, 0, A.length);
//输出数组
PrintArrays.printA(A);
}
//插入排序最后一个参数 r 为数组长度，p 为数组起始位置。
public static void insertSort(int []A,int p, int r)
{
// if 用于控制递归终止
if (r >p)
{
r--;
//递归拆解
insertSort(A ,p , r);
int i = r-1;
int key = A[r];
//位置插入关键
//边查找合适的插入位置，边挪动数组的元素
while (( i>=p) && (key <A[i]))
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}
}
}
归并排序
//常规归并排序
public class MergeSort01
{
public static void main(String args[])
{
int A[] = RandomArray.randomArray(8);
mergeSort(A, 0, A.length-1);
//打印输出模块同上
PrintArrays.printA(A);
}
//归并排序（递归调用）
public static void mergeSort(int A[], int p, int r)
{
if ( r>p)
{
int q= (p+r-1)/2;
//方法形参传递 为值传递 ，数组形参传递的是引用地址
mergeSort(A, p, q);
mergeSort(A, q+1,r);
mergeArray(A, p, q, r);
}
}
//合并子问题的解 模块
public static void mergeArray(int A[] , int p,int q,int r)
{
int n1 = q - p + 1;
int n2 = r - q ;
int []L = new int[n1];
int []R = new int[n2];
for (int i =0; i< n1 ; i++)
{
L[i] = A[p+i];
}
for (int j =0; j< n1 ; j++)
{
R[j] = A[q+j+1];
}
for (int k= 0 ,i=0 ,j=0; ((i<n1) || (j<n2))&&(k< r-p+1) ; k++)
{
if (i>= n1)
{
A[p+k] = R[j];
j++;
} else if(j>= n2)
{
A[p+k] = L[i];
i++;
//以上是其中一个数组遍历完的处理
} else if ( L[i]< R[j])
{
A[p+k] = L[i];
i++;
} else{
A[p+k] = R[j];
j++;
}
}
}
}
//归并排序与插入排序结合
public class MergeSort02
{
public static void main(String args[])
{
//随机数组的产生
int A[] = RandomArray.randomArray(128);
PrintArrays.printA(A);
System.out.println();
mergeSort(A, 0, A.length-1, 4);
//输出
PrintArrays.printA(A);
}
//归并排序 参数说明：
// p 为数组起始位置 r 为数组末尾位置 nk 为子数组插入排序长度
public static void mergeSort(int A[], int p, int r, int nk)
{
int q= (p+r-1)/2;
if ((q-p+1) > nk)
{
//递归分解
mergeSort(A, p, q, nk);
mergeSort(A, q+1,r, nk);
}
else
{
//分治算法 解决最小的子问题
//插入排序最后一个参数为数组长度
InsertSort03.insertSort(A,p ,q +1);
InsertSort03.insertSort(A,q+1 ,r+1 );
}
MergeSort01.mergeArray(A, p, q, r);
//方法形参传递 为值传递 ，数组形参传递的是引用地址
//由于 数组传递引用地址的特性，解决了分治算法的合并子答案步骤
}
}
选择排序算法
//选择排序算法
public class SelectionAlgorithm01
{
public static void main(String args[])
{
int A[] = {1,9,6,8,4,5,3,7,2,0};
//选择算法
//变量 min 依次提取最小值
for ( int j=1 , k=0; j < A.length ; j++)
{
int min = A[j-1] ;
int i = j;
//变量 K 用于记录最小值的位置
while( i < A.length)
{
if( min >A[i])
{
min = A[i];
k = i;
}
i++;
}
A[k] = A[j-1];
A[j-1] = min;
}
// 4 重复
PrintArrays.printA(A);
}
}
冒泡排序
public class BubbleSort
{
//冒泡排序法
public void maoPaoPX(int[] arryA)
{
//将最大的依次 冒泡到最右边
for (var i=arryA.length; i>0;i--)
{
for (var j=0;j<i;j++)
{
if ((j+1)==arryA.length)
{
break;
}
if ( arryA[j] > arryA[j+1] )
{
int temp = arryA[j+1];
arryA[j+1] =arryA[j];
arryA[j] =temp;
}
}
}
}
}
查找算法
//查找算法
public class LinearSearch
{
static final int NIL = -1 ;
public static void main(String args[])
{
int v = 8;
int []A = {1,9,6,8,4,5,3,7,2,0};
//排序
A = InsertSort03.insertSort(A, A.length);
PrintArrays.printA(A);
System.out.println();
//线性查找
int j = linearSearch(A , v);
System.out.println("j = "+ j);
//二分法查找
j= binarySearch02(A , v, 1 ,A.length ,1 ) ;
System.out.println("j = "+ j);
/*
j= binarySearch(A , v , true , 0, A.length-1);
System.out.println("j = "+ j);
*/
}
//二分法查找
public static int binarySearch02(int []A,int v , int left,int right ,int mid)
{
mid = (left+ right)/2;
int aMid= mid -1;
if (A[aMid] == v)
{
return mid;
} else if( A[aMid] > v){
right = mid;
}else {
left = mid;
}
return binarySearch02(A , v ,left ,right ,mid);
}
//线性查找
public static int linearSearch(int []A, int v)
{
int i=1;
int j=NIL;
for (int atemp : A)
{
if( atemp == v)
{
j=i ;
}
i++;
}
return j;
}
}
习题 2.3.7
public class BookTest2o3o7
{
public static void main(String args[])
{
int A[] = {2 , 4, 5,6, 8, 10};
int x= 17;
System.out.println(bookTest2o3o7(A, x));
}
/*
描述一个运行时间为@(nlgn) 的算法，给定n 个整数的集合S 和另一个整数X ， 该算法能
确定S 中是否存在两个元素其和刚好为x的元素。
*/
public static boolean bookTest2o3o7(int []A, int x)
{
if (A.length <=1)
{
return false;
}
int i=0;
int j= A.length-1;
while(i<j)
{
//x 与 A[i]+A[j] 比较。
//若 x 较大，则 i 增大 ，否则 j 减小，直到 i >= j 结束循环。
if (x ==(A[i] + A[j]) )
{
return true;
} else if( x > A[i] + A[j]){
i++;
} else {
j--;
}
}
return false;
}
}