排序算法进阶–排序算法优化
- 2019 年 10 月 15 日
- 筆記
排序算法进阶
上篇文章中我们主要介绍了经典的八大排序算法，从算法思想，动图演示，代码实现，复杂度及稳定性分析等角度进行学习。还没阅读的童鞋可以点这里进行浏览。
求知若渴的你肯定不会满足于入门的内容，今天，小编在上一篇的基础上，对多种排序算法进行优化，让我们一起来康康吧~~
01冒泡排序
1. 优化一
-
优化思路：优化外层循环，我们知道，冒泡排序的每一轮都会对未排序部分进行一次遍历，如果在某次循环中没有交换操作，就说明数组已经有序，不用继续排序。
-
实现代码
1 public static int[] bubbleSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 for (int i = 0; i < array.length; i++){ 5 boolean isSwap = false;//标记是否已经有序 6 for (int j = 0; j < array.length - 1 - i; j++) 7 if (array[j + 1] < array[j]) { 8 int temp = array[j + 1]; 9 array[j + 1] = array[j]; 10 array[j] = temp; 11 isSwap = true; 12 } 13 if(!isSwap) 14 break; 15 } 16 return array; 17 }
2. 优化二
-
优化思路：优化内层循环，记住上一次发生交换的位置pos，则有序区扩展为[pos, len-1]，下一趟排序只需遍历[0, pos-1]即可。
-
实现代码
1 public static int[] bubbleSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 int pos = 0;//标记最后一次交换的位置 5 int k = array.length-1; 6 for (int i = 0; i < array.length; i++){ 7 boolean isSwap = false; 8 for (int j = 0; j < k; j++) 9 if (array[j + 1] < array[j]) { 10 int temp = array[j + 1]; 11 array[j + 1] = array[j]; 12 array[j] = temp; 13 isSwap = true; 14 pos = j; 15 } 16 k=pos; 17 if(!isSwap) 18 break; 19 } 20 return array; 21 } 1570932802569
3. 优化三
-
优化思路：双向冒泡排序（鸡尾酒排序），先从前往后，再从后往前去比较序列中的元素大小，每一次排序分别能确定未排序序列的最大最小值并放在相应位置。
-
实现代码
1 public void cocktail_sort(int[] a){ 2 int left = 0, right = a.length-1; 3 int temp; 4 while(left<right){ 5 //找到当前排序元素里最大的那个，放在右侧 6 for(int i=left;i<right;i++){ 7 if(a[i]>a[i+1]){ 8 temp = a[i]; 9 a[i] = a[i+1] ; 10 a[i+1] = temp; 11 } 12 } 13 right--; 14 //找到当前排序元素里最小的那个，放在左侧 15 for(int j=right;j>left;j--){ 16 if(a[j-1]>a[j]){ 17 temp = a[j]; 18 a[i] = a[j+1] ; 19 a[j+1] = temp;} 20 } 21 left++; 22 } 23 }
当然，你也可以结合上述的优化算法实现：优化外层循环+优化内层循环+双向冒泡排序。
02选择排序
1. 优化一
-
优化思路：
-
实现代码
1 public static int[] selectSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 int left = 0; 5 int right = array.length-1; 6 int min = left;//最小值下标 7 int max = right;//最大值下标 8 while(left<=right){ 9 min = left; 10 max = right; 11 for(int i=left; i<=right; i++){ 12 if(array[i]<array[min]){ 13 min = i; 14 } 15 if(array[i]>array[max]) 16 max = i; 17 } 18 swap(array[left],array[min]); 19 if(left==max) 20 max = min; 21 swap(array[right],array[max]); 22 ++left; 23 --right; 24 } 25 return array; 26 }
03插入排序
1. 优化一
-
优化思路：每一次查找最大值的时候，也可以同时查找最小值，然后分别放在相应的位置。
-
实现代码
1 public static int[] BinsertSort(int[] a){ 2 int left, right, m, num; 3 for(int i=1;i<a.length;i++){ 4 num = a[i]; 5 left = 0; 6 right = i-1; 7 //二分查找 8 while(left<=right){ 9 m = (left+right)/2; 10 if(num<a[m]) 11 right = m-1; 12 else 13 left = m+1; 14 } 15 for(int j=i-1;j>=right+1;--j) 16 a[j+1]=a[j]; 17 a[right+1]=num; 18 } 19 return a; 20 }
04快速排序
1. 优化一
-
优化思路：优化基准值选取：采用固定基准的方法来对数组进行划分时，如果数组元素基本有序，容易产生最坏时间复杂度O(n^2)；所以可以采用随机基准值确定；但是如果数组值是随机的，采用固定基准可能比随机的要快；故可考虑三数取中：选取待排序数组的开头中间和结尾，通过比较，选取中间值作为基准；
-
实现代码
1 public static void swap(int[] arr,int left,int right) 2 { 3 int temp; 4 temp=arr[left]; 5 arr[left]=arr[right]; 6 arr[right]=temp; 7 } 8 public static int partition(int[] arr,int left,int right) 9 { 10 int m=left+(right-left)/2;//找到中间的数字的下标 11 if(arr[left]>arr[right])//最左大于最右的时候，交换左右 12 { 13 swap(arr,left,right); 14 } 15 if(arr[m]>arr[right])//如果中间的>right ,交换 16 { 17 swap(arr,m,right); 18 } 19 if(arr[m]>arr[left])//如果中间的>left，交换 20 { 21 swap(arr,m,right); 22 } 23 int temp=arr[left];//基准 24 while(left<right)//知道left和right重合的时候，才找到合适的位置 25 { //从后向前找到比小的数字 26 while(left<right && arr[right]>=temp) 27 { 28 right--; 29 } 30 arr[left]=arr[right];//当right的值小于temp的值的时候执行 31 while(left<right && arr[left] <= temp)//从前往后找到比基准大的数字 32 { 33 left++; 34 } 35 arr[right]=arr[left];//当left的值大于temp的时候执行 36 } 37 arr[left]=temp;//此时的left和right在同一个位置，此时为合适的位置，把temp的值给left 38 return left;//此时返回的值是temp合适的位置，即小于它的在它的左边，大于它的在它的右边 39 } 40 public static int[] Quicksort(int array[], int left, int right) { 41 if(left < right){ 42 int pos = partition(array, left, right); 43 Quicksort(array, left, pos - 1); 44 Quicksort(array, pos + 1, right); 45 } 46 return array; 47 }
2. 优化二
-
优化思路：序列长度达到一定大小时，使用插入排序：当快排达到一定深度后，划分的区间很小，使用快排效率不高，可以使用插入排序；
-
实现代码
1 public static void quickSort(int[] arr,int left,int right) 2 { 3 int length=right-left; 4 if(length>max_len ) 5 { 6 int pivot=partition(arr,left,right); 7 quickSort(arr,left,pivot-1); 8 quickSort(arr,pivot+1,right); 9 } 10 else 11 { 12 BinsertSort(arr); 13 } 14 }
3. 优化三
-
优化思路：尾递归优化，快排的递归出现在函数的尾部，且它的返回值不作为表达式的一部分，即递归回溯后不需要做任何操作，编译器检测到尾递归时，他就覆盖当前的活动记录而不是在栈中去创建一个新的，节省了大量栈空间；
4. 优化四
-
优化思路：聚集元素，在一次分割结束后，将与本次基准相等的元素聚集在一起，再分割时，不再对聚集过的元素进行分割（可以在划分过程中，将与本次基准相等元素放入数组两端，划分结束后再将这些元素一道基准值周围）；
-
代码实现
1 //找基准 2 public static int partion(int[] array,int low,int high){//一次快排 3 int tmp=array[low]; 4 while(low < high){ 5 //从后找 6 while(low < high && array[high] >= tmp){ 7 --high; 8 } 9 if(low >= high){ 10 break; 11 }else{ 12 array[low] = array[high]; 13 } 14 //从前找 15 while(low < high && array[low] <= tmp){ 16 ++low; 17 } 18 if(low >= high){ 19 break; 20 }else{ 21 array[high] =array[low]; 22 } 23 } 24 array[low] = tmp; 25 return low; 26 } 27 //将相同元素聚集在一起 28 public static int[] focusNum(int[] array,int start,int end,int par){ 29 int tmp = 0; 30 //查找范围 31 int left=par-1; 32 int right=par+1; 33 //交换的指引变量 34 int parLeft=par-1; 35 int parRight=par+1; 36 //左边找 37 for(int i = left;i >= start;i--){ 38 if(array[i] == array[par]){//遍历过程中，有与par相同的元素时 39 if(i != parLeft){//若i 和parLeft相同，将两下标所对应的元素交换 40 tmp = array[i]; 41 array[i] = array[parLeft]; 42 array[parLeft] = tmp; 43 parLeft--; 44 }else{ 45 parLeft--; 46 } 47 } 48 } 49 //右边找 50 for(int j = right;j <= end;j++){//遍历过程中，有与par相同的元素时 51 if(array[j] == array[par]){//若i 和parRight相同，将两下标所对应的元素交换 52 if(j != parRight){ 53 tmp = array[j]; 54 array[j] = array[parRight]; 55 array[parRight] = tmp; 56 parRight++; 57 }else{ 58 parRight++; 59 } 60 } 61 } 62 int[] focus={parLeft,parRight}; 63 return focus; 64 } 65 //基准左右进行递归排序 66 public static void Quick(int[] array,int start,int end){ 67 int par = partion(array,start,end); 68 int[] brray = focusNum(array,start,end,par);//相同元素聚集在一起后，新的left和right 69 int left = brray[0]; 70 int right = brray[1]; 71 if(par > start+1){ 72 Quick(array,start,left); 73 } 74 if(par < end-1){ 75 Quick(array,right,end); 76 } 77 }
5. 优化五
-
优化思路：采用多线程，因为子问题是独立的。
欢迎补充，指错，提建议，感谢阅读，感谢支持！
关注我 获取更多知识
长按扫码关注
