6. 快速排序
快速排序有几种写法, 我们这就列举相对简单的 Hoare 法:
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后将左右子序列重复该过程，直到所有元素都排列在相应位置上为止.
我们可以直接将最左边元素作为基准值来分割序列, 定义 l 和 r 分别代表该序列最左边与最右边位置下标, 先从右边开始往后找到比 6 小的元素下标, 再从左边开始找到比 6 大的元素下标, 然后将它两元素交换, 继续上述操作, 直到它两相遇, 然后交换基准值与相遇位置元素, 然后将 6 左边数组与右边数组重复上面操作.
public class Test { public static void Sort(int[] array){ int left = 0; int right = array.length-1; SortChild(array,left,right); } private static void SortChild(int[] array, int left, int right) { if(left >= right) { //结束递归条件 return; } int l = left; int r = right; int key = array[l]; //记录基准值 while(l < r) { while(l < r && array[r] >= key) { //注意找的是小于key的值, 得加等于号, 下面同理 r--; } while(l < r && array[l] <= key) { l++; } Swap(array,l,r); //找到后交换元素 } Swap(array,left,l); //最后把key与相遇下标值交换 SortChild(array,left,l-1); SortChild(array,l+1,right); } public static void Sort(int[] array){ int left = 0; int right = array.length-1; SortChild(array,left,right); } }
理想情况下, 它是类似与二叉树结构 , 每层都是比较 N 次, 那高度是 lgN, 时间复杂度就是N*lgN.
但这是理想情况, 如果我们给的是一个有序数组呢?
那它每层比较 N 次, 但它的高度却是 N, 所以时间复杂度为 N^2.
我们可以对它进行优化, 就是用三数取中法, 来取出首尾中三元素的中间值, 然后将中间值与首元素交换, 作为基准, 再来排序.
快速排序总结:
- 快速排序整体的综合性能和使用场景都是比较好的.
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
7. 归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
public class Test { public static void Merge(int[] array) { MergeChild(array,0,array.length-1); } private static void MergeChild(int[] array, int left, int right) { if(left >= right) { //递归结束条件 return; } int m = (left+right)/2; MergeChild(array,left,m); //往左递归 MergeChild(array,m+1,right); //往右递归 //将两个子序列合并 int a = left; int b = m+1; int size = right-left+1; int[] arr = new int[size]; //定义一个数组存放两个子序列 int j = 0; //将两个子序列有序放入arr数组中 while(a <= m && b <= right) { if(array[a] < array[b]) { arr[j++] = array[a++]; }else { arr[j++] = array[b++]; } } if(a > m) { while(b <= right) { arr[j++] = array[b++]; } }else { while(a <= m) { arr[j++] = array[a++]; } } //将arr数组元素重新放入array数组中 for(int i = 0; i < size; i++) { array[i+left] = arr[i]; } } }
归并排序总结:
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
8. 基数排序(了解)
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
public class Test { public static void Radix(int[] array) { int min = array[0]; int max = array[0]; //找出最大与最小值 for(int i = 1; i < array.length; i++) { if(array[i] < min) { min = array[i]; } if(array[i] > max) { max = array[i]; } } //创建一个元素大小范围的数组 int[] arr = new int[max-min+1]; //用该数组记录下标为 array[i]-min 的元素个数 for(int i = 0; i < array.length; i++) { arr[array[i]-min]++; } int j = 0; // j记录赋值时array的下标 //将记录的数据记录进原数组 for(int i = 0; i < arr.length; i++) { while(arr[i] != 0) { //根据arr[i]记录的个数来决定赋值次数 array[j++] = i+min; //i+m是利用i将原来元素的大小翻译出来 arr[i]--; } } } }
计数排序的特性总结:
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
总结
上述八大排序中, 稳定的排序仅三个 : 直接插入排序, 冒泡排序, 归并排序.
基数排序算不上稳定, 因为它存放的数据都不是原来的数据了.
