1.准备函数
1.1 验证排序
//验证排序是否正确public static boolean assert(int[] arr){for(int i = 0;i<arr.length-1;i++) {if(arr[i]>arr[i+1]) {return false;}}return true;}}
1.2生成随机数组
//生成随机数组public static int[] genereateRandomArray(int n,int rangeL,int rangeR) {int[] arr = new int[n];if(rangeL>rangeR){return arr;}Random ra = new Random();for(int i =0;i<n;i++) {int s = ra.nextInt(rangeR-rangeL);arr[i] = s+rangeL;}return arr;}
1.3循环遍历数组
//循环遍历数组public static void printfArray(int[] arr) {for(int i= 0;i<arr.length;i++) {System.out.print(arr[i]+" ");}}
1.4 交换两个元素
//交换两个数组元素public static void swapArr(int[] arr,int index1,int index2) {int i = arr[index2];arr[index2] = arr[index1];arr[index1] = i;}
2.O(n^2)的排序算法
2.1选择排序
2.1.1基本代码实现
//选择排序public static void selectionSort(int[] arr) {for(int i = 0;i<arr.length;i++) {//寻找（i,arr.length]之间的最小值int minIndex = i;for(int j = i+1;j<arr.length;j++) {if(arr[j]<arr[minIndex]) {minIndex = j;}}swapArr(arr,i,minIndex);}}
2.1.2运行
public static void main(String[] args) {int[] arr = genereateRandomArray(20000, 15, 50);printfArray(arr);System.out.println();long startTime=System.currentTimeMillis(); //获取开始时间selectionSort(arr);long endTime=System.currentTimeMillis(); //获取结束时间System.out.println("程序运行时间： "+(endTime-startTime)+"ms");printfArray(arr);}
2.2插入排序
2.1.2基本代码实现
对近乎有序的数组中，插入排序优势更大
//插入排序public static void insertionSort(int[] arr) {for(int i = 1; i<arr.length;i++) {//寻找元素arr[i]合适的插入位置int j;for(j = i;j>0;j--) {if(arr[j] < arr[j-1]) {//使用交换 需要赋值三次swapArr(arr, j, j-1);}else {break;}}}}
2.1.2插入排序改进
//插入排序public static void insertionSort(int[] arr) {for(int i = 1; i<arr.length;i++) {//寻找元素arr[i]合适的插入位置int e = arr[i];int j;for(j = i;j>0;j--) {if(arr[j-1] > e) {//改进后 只需要赋值一次arr[j] = arr[j-1];}else {break;}}arr[j] = e;}}
2.1.3 运行
public static void main(String[] args) {int[] arr = genereateRandomArray(20000, 15, 50);printfArray(arr);System.out.println();long startTime=System.currentTimeMillis(); //获取开始时间insertionSort(arr);long endTime=System.currentTimeMillis(); //获取结束时间System.out.println("程序运行时间： "+(endTime-startTime)+"ms");printfArray(arr);}
3.O(nlogn)的排序算法
3.1 归并排序
3.1.1 基本代码实现
//将arr[l..mid] 和 arr[mid+1 ... r]两部分进行归并private static void __merge(int[] arr,int l,int mid, int r) {int[] aux = new int[r-l+1];//将排序的空间赋值给auxint i;for(i = l;i <= r;i++) {aux[i-l] = arr[i];}i=l;int j = mid+1;//归并排序for(int k = l;k <= r;k++) {//1 看i j 是否越界if(i>mid) {arr[k] = aux[j-l];j++;}else if(j>r) {arr[k] = aux[i-l];i++;}else {if(aux[i-l]<aux[j-l]) {arr[k] = aux[i-l];i++;}else {arr[k] = aux[j-l];j++;}}}}//递归使用归并排序，对arr[l..r] 的范围进行排序private static void __mergeSort(int[] arr,int l,int r) {//结束条件if(l >= r) {return;}//求中点位置int mid = (l+r)/2;__mergeSort(arr,l,mid);__mergeSort(arr,mid+1,r);//进行最后排序__merge(arr,l,mid,r);}//归并排序public static void mergeSort(int[] arr) {//对arr[l..r] 的范围进行排序__mergeSort(arr,0,(arr.length)-1);}
3.1.2 运行
public class Test {
public static void main(String[] args) {
int[] arr = genereateRandomArray(20000, 15, 50);
printfArray(arr);
System.out.println();
long startTime=System.currentTimeMillis(); //获取开始时间
mergeSort(arr);
long endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
printfArray(arr);
}
3.1.3 优化
// 1.将基数变大
//结束条件，将和插入排序联合,将基数变大
//if(l >= r) {
// return;
//}
if(r-l <= 15) {
insertionSort2(arr,l,r);
return;
}
//2.如果右边的第一个大于左边的第一个则不需要排序
//因为 l-mid mid-r 为一个有序的如果右边的第一个大于左边的第一个则不需要排序
if(arr[mid]>arr[mid+1]) {
//进行最后排序
__merge(arr,l,mid,r);
}
3.2 至下而上的归并排序
3.2.1 基本代码实现
//将arr[l..mid] 和 arr[mid+1 ... r]两部分进行归并
private static void __merge(int[] arr,int l,int mid, int r) {
int[] aux = new int[r-l+1];
//将排序的空间赋值给aux
int i;
for(i = l;i <= r;i++) {
aux[i-l] = arr[i];
}
i=l;
int j = mid+1;
//归并排序
for(int k = l;k <= r;k++) {
//1 看i j 是否越界
if(i>mid) {
arr[k] = aux[j-l];
j++;
}else if(j>r) {
arr[k] = aux[i-l];
i++;
}else {
if(aux[i-l]<aux[j-l]) {
arr[k] = aux[i-l];
i++;
}else {
arr[k] = aux[j-l];
j++;
}
}
}
}
//从下往上的归并排序
public static void mergeSortBU(int[] arr) {
for(int sz =1;sz <=arr.length ; sz += sz) {
//切分到最后只有一半和一半以内则直接跳过
for(int i = 0;i+sz <arr.length;i +=sz+sz) {
__merge(arr,i,i+sz-1,min(i+sz+sz-1,arr.length-1));
}
}
}
//min 两值取最小
private static int min(int i,int j) {
if(i<j) {
return i;
}
return j;
}
3.2.2运行
public class Test {
public static void main(String[] args) {
int[] arr = genereateRandomArray(20000, 15, 50);
printfArray(arr);
System.out.println();
long startTime=System.currentTimeMillis(); //获取开始时间
mergeSortBU(arr);
long endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
printfArray(arr);
}
3.3 快速排序
3.3.1 基本代码实现
//对arr[l...r] 部分进行partiton 操作
//返回p 使得arr[l...p-1] <arr[p] arr[p+1 ...r] >arr[p]
private static int __partition(int[] arr,int l, int r) {
int v = arr[l];
// j的值指向第一个大于V的值的下标
int j = l+1;
// 遍历整个数组 一直到 i<= r 时候结束
for(int i = l+1;i<=r;i++) {
if(arr[i] < v) {
swapArr(arr, i,j);
j++;
}
}
swapArr(arr, l, j-1);
return j-1;
}
//对arr[l...r] 部分进行快速排序
private static void __quickSort(int[] arr,int l,int r) {
if(l>=r) {
return;
}
int p = __partition(arr,l,r);
__quickSort(arr, l, p-1);
__quickSort(arr, p+1, r);
}
//快速排序
public static void quickSort(int[] arr) {
__quickSort(arr,0,arr.length-1);
}
3.3.2 运行
public static void main(String[] args) {
int[] arr = genereateRandomArray(20000, 0, 10000);
int[] copyArr = copyArray(arr);
long startTime=System.currentTimeMillis(); //获取开始时间
mergeSort(arr);
long endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
long startTime1=System.currentTimeMillis(); //获取开始时间
quickSort(copyArr);
long endTime1=System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间： "+(endTime1-startTime1)+"ms");
}
3.3.3 优化
为了防止快速排序退化成O(n^2)
//对arr[l...r] 部分进行partiton 操作
//返回p 使得arr[l...p-1] <arr[p] arr[p+1 ...r] >arr[p]
private static int __partition(int[] arr,int l, int r) {
//优化
Random ra = new Random();
int rand = ra.nextInt(r-l)+l;
swapArr(arr, rand,l);
int v = arr[l];
//记录大于v 的值的下标
int j = l;
for(int i = l+1;i<=r;i++) {
if(arr[i] < v) {
swapArr(arr, i,j+1);
j++;
}
}
swapArr(arr, l, j);
return j;
}
平衡优化
//优化
private static int __partition2(int[] arr,int l, int r) {
int v = arr[l];
int i = l+1;
int j = r;
while(true) {
while(i<=r && arr[i] <v) {
i++;
}
//当一个有序数组进来的时候，运行完这个后j指向arr[l]
while(j>l && arr[j]>v) {
j--;
}
if(i>j) {
break;
}
swapArr(arr,i, j);
i++;
j--;
}
swapArr(arr,l, j);
return j;
}
3.4三路快速排序
3.4.1 基本代码实现
private static void __quickSort3Ways(int[] arr,int l,int r) {
if(r-l<=15) {
insertionSort(arr);
return;
}
Random ra = new Random();
swapArr(arr, l, ra.nextInt(r-l)+l);
int v = arr[l];
//__partition3Ways(arr,r,l);
//partiton3Ways
int lt = l;
int gt = r;
int i = l+1;
while(i<gt){
if(arr[i]>v) {
swapArr(arr, i, gt);
gt--;
}else if(arr[i]<v) {
swapArr(arr, i, lt+1);
i++;
lt++;
}else {
i++;
}
}
swapArr(arr, l, lt);
__quickSort3Ways(arr,l,lt-1);
__quickSort3Ways(arr,gt,r);
}
//三路快速排序
public static void quickSort3Ways(int[] arr) {
__quickSort3Ways(arr,0,arr.length-1);
}
若有收获，就点个赞吧
0 人点赞
