【JavaDS】排序——快排 & 归并

上接【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）：冒泡、插排、希尔、选择、堆排

    属于分治算法（把问题分成多个子问题分别处理）：快排、归并