上接【JavaDS】排序——快速排序
快排的另一种 partition 方法
通过算法的设计将序列分成如图所示的三个区间
[ from, s ) 元素 <= pivot
[ s, i ) 元素 >= pivot
[ i, to ) 待比较元素
遍历 [ from, to )
比较 array[i] 和 pivot ，array[i] < pivot ，交换 i 和 s 的元素，同时 i++，s++;
array[i] > pivot, i++;
遍历比较完成之后，交换 pivot 和 s 的值
代码参考
private static int partitionMethodC(long[] array, int from, int to) { int s = from; long pivot = array[to]; for (int i = from; i < to; i++) { // 遍历 [from, to) // 这里加 == 号也保证不了稳定性，有交换操作 if (array[i] < pivot) { // TODO: 可以进行简单的优化：如果 i == s，就不交换 long t = array[i]; array[i] = array[s]; array[s] = t; s++; } } array[to] = array[s]; array[s] = pivot; return s; }
快排的几个常见优化手段
1. 前提结论：在待排序元素比较少的情况下，快排的速度低于插排，所以，在待排序元素个数的个数低于一个阈值（20）时，直接使用插排完成
2. partition 算法上的优化（比如，把 == pivot 的提前找出来），
同时选择多个基准值，比如三个，记为 p1, p2, p3, 其中 p1 < p2 < p3 , 如下图所示
3. 选择 pivot 的方式上优化
三数取中法
取区间最开始，最中间以及最后面的三个数，取这三个数大小上是中间的数作为基准值，最后再把确定的基准值交换到区间最后面
归并排序
将区间分成如图所示的两个小区间，如果可以使左右两个区间都变得有序，那么合并两个有序区间之后，整个区间变得有序
归并排序的基本思想
1. 如果待排序区间已经有序（区间内的元素个数 <= 1)，则排序操作直接返回
2. 确定区间中间位置的下标 mid （ mid = from + （size / 2）），所以 [ from, to ) 的区间，被我们从逻辑上视为是左右两个小区间（[ from, mid) 和 [ mid, to )）组成
3. 先对左右两个小区间使用相同的方法，进行排序
4. 当左右两个小区间已经有序时，执行合并两个有序区间的操作，得到一个最终的有序大区间
具体步骤演示
和并两个小区间为一个有序大区间的方法
合并两个有序区间，需要用到同等大小的一个额外空间
从两个区间分别挑出最小的元素比较，确定两个元素在新区间内的相对位置，循环执行此过程，直至一个小区间内的元素全部被比较，如果另一个区间内还有元素，则按照顺序插入新区间即可
代码参考
private static void merge(long[] array, int from, int mid, int to) { // 先计算出来额外空间需要多个，计算两个区间加起来多少个元素 int size = to - from; // 申请一个额外的数组作为临时保存的地方 long[] other = new long[size]; // 需要一个 和 n 长度一致的空间 int left = from; // 左边小区间的下标 int right = mid; // 右边小区间的下标 int dest = 0; // 临时空间的下标 // 只要左右两个小区间还有元素要参与比较 while (left < mid && right < to) { if (array[left] <= array[right]) { other[dest++] = array[left++]; } else { other[dest++] = array[right++]; } } // 其中一个区间的元素取完了，另一个区间里一定还有元素，再把剩余的元素，统统放入 other // 看起来左右两个都写了，但执行起来的时候一定只有一个会执行 while (left < mid) { other[dest++] = array[left++]; } while (right < to) { other[dest++] = array[right++]; } // 把 other 中的有序元素，复制回 array 中，要注意下标的问题 for (int i = 0; i < size; i++) { array[from + i] = other[i]; // array 下标的基准是从 [from] 开始，other 下标的基准是从 [0] 开始 // offset(偏移）是一致的，都是 i } }
7 种基于比较的排序
快速排序、归并排序、冒泡排序、插入排序、希尔排序、选择排序、堆排序
按照不同的标准，划分这些排序
1. 具备稳定性的排序：冒泡、插排、归并
2. 平均情况下，执行速度分为两组：
1）慢：冒泡、插排、选择——排序的元素个数在 10万 级别左右
2）快：快排、归并、希尔、堆排——个数在 1忆 级别
3. 空间角度
1）空间复杂度是 O(1) ：冒泡、插排、希尔、选择、堆排
2）空间复杂度是 O(log(n) ~ O(n))：快排
3）空间复杂度是 O(n)：归并
4. 属于减治算法（每次问题规模减少1）：冒泡、插排、希尔、选择、堆排
属于分治算法（把问题分成多个子问题分别处理）：快排、归并
