2019-11-21

算法关于排序

words: 5.7k views: time: 23min

排序即将一组对象按照某种逻辑顺序重新排列的过程，通常，整理数据的第一步就是进行排序，因此它是后面很多其它算法和数据结构的基础。在计算机早期年代，据说大约有30%的计算周期都花在了排序操作上，如今这个比例有所降低，并非排序的重要性降低了，而是前辈们不懈的研究，使得如今的排序算法更加高效。

在不同的场景下选择合适的排序算法其实是很重要的，比如下面是使用文中的几种排序策略对同样的1000个随机数进行排序的结果，可以看出来差距还是比较大的

SELECT         comp=511566  swap=251579  cost=16355ms
INSERT         comp=252594  wap=251584   cost=16449ms
INSERT_BINARY  comp=14294   move=1011    cost=111ms
INSERT_XIER    comp=13576   swap=8453    cost=578ms
MERGE          comp=9413    swap=0       cost=68ms
QUICK          comp=15391   swap=2225    cost=191ms
QUICK2         comp=13857   swap=13853   cost=905ms

引言

为了方便说明和比较各种排序算法，这里先设计一个排序工具类Sorts，其提供对List进行排序的接口，同时支持对排序策略的选择，还可以通过给定比较器Comparator来设置排序的顺序

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

public static <T extends Comparable<? super T>> void sort(List<T> list, String algorithm, Comparator<? super T> comp) {
    doSort(list, algorithm, comp);
}

private static <E> void doSort(List<E> list, String algorithm, Comparator<? super E> comp) {
    LOGGER.debug("before sort: {}", list); 

    Object[] array = list.toArray();
    switch(algorithm){
    case ALGORITHM_SELECT: sort_select(array, comp); break;               // 选择排序（冒泡）
    case ALGORITHM_INSERT: sort_insert_swap(array, comp); break;          // 插入排序
    case ALGORITHM_INSERT_BINARY: sort_insert_binary(array, comp); break; // 插入排序（二分法改进）
    case ALGORITHM_INSERT_XIER: sort_xier(array, comp); break;            // 希尔排序
    case ALGORITHM_MERGE: sort_merge(array, comp); break;                 // 归并排序
    case ALGORITHM_QUICK: sort_quick(array, comp); break;                 // 快速排序
    case ALGORITHM_QUICK2: sort_quick2(array, comp); break;               // 快速排序（重复场景改进）
    }

    ListIterator<E> i = list.listIterator();
    for (Object e : array) {
        i.next();
        i.set((E) e);
    }
}

然后在内部定义两个统一的操作，即比较comp和交换swap，这样方便查看排序的过程，以及比较各个排序算法的复杂度

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static int comp(Object[] array, int a, int b, Comparator comp) {
    times_compare++;
    LOGGER.debug(String.format("%60s %2s comp：%2s<>%2s ([%2s]<>[%2s])", " ", times_compare, array[a], array[b], a, b)); 
    if(comp != null){
        return comp.compare(array[a], array[b]);
    }else{
        return ((Comparable)array[a]).compareTo(array[b]);
    }
}

private static void swap(Object[] array, int a, int b) {
    Object t = array[a];
    array[a] = array[b];
    array[b] = t;
    times_swap++;
    LOGGER.debug(String.format("%2s swap： %2s<>%2s ([%2s]<>[%2s]) = %s", times_swap, array[b], array[a], a, b, Arrays.toString(array))); 
}

下面构造一个List[5, 2, 10, 7, 6, 3, 8, 4]，然后分别使用不同的排序算法来对其进行排序和复杂度分析比较

1. 选择排序

选择排序是很容易理解和简单的一种排序：即每次从剩下的元素中找出最小的元素进行排定

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_select(Object[] array, Comparator comp) {
    for(int i = 0; i < array.length; i++){
        for(int j = i + 1; j < array.length; j++){
            if(comp(array, i, j, comp) > 0){
                swap(array, i ,j);
            }
        }
    }
}

.这里写的冒泡实现，思路是一样的，只是没有用一个临时变量来记录最小值，区别就是交换次数偏多，但比较次数一样

选择排序的时间复杂度与输入的初始顺序无关，也就是无论输入时是怎样的顺序，其比较和交换次数都是固定的。

由于每次交换都能排定一个元素，所以最多只需要寻找并交换 $N-1$ 次，但每次遍历寻找最小元素的操作，并不能为下一次遍历提供有用信息，因此即便对于一个已经排序的数组，同样需要比较次数：$(N-1) + (N-2) + … + 1 = N(N-1)/2 \in N^2$

2. 插入排序

选择排是每次将待排元素与剩下的无序数组进行排序，所以它每次都要与剩下的所有元素进行比较，这样前面的排序操作无法为后续的工作提供提供条件。

相反的，插入排序每次将待排元素与已排定的元素进行排序，这样就不一定每次都要与所有已排定的元素进行比较了，只要找到正确的位置就可以停止比较了，可以想象一下抓牌的过程，每次抓到一张新牌都是将其插入到前面已经有序的牌中。

与选择排序一样，当前位置左边的所有元素都是有序的，但是它们的最终位置还不确定，为了给更小的元素腾出位置，它们可能还会被移动，当索引到达数组最右端时，数组排序也就完成了。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_insert_swap(Object[] array, Comparator comp) {
    for(int i = 1; i < array.length; i++){
        for(int j = i; j > 0 && comp(array, j, j - 1, comp) < 0; j--){
            swap(array, j-1 ,j);
        }
    }
}

插入排序的时间复杂度与输入的初始顺序相关，最好的情况是数组已经排序，那么只需要 $N-1$ 次比较和 $0$ 次交换，相反，最差情况则是逆序数组，那么就需要 $N(N-1)/2$ 次比较，以及 $N(N-1)/2$ 次交换，如果取平均复杂度，那就是好坏参半，可以约为 $\in N^2/4$

改进

对于插入操作，还可以通过二分法改进一下，即每次从已排定数组的中间位置开始进行比较，这样便可以将每次插入时的比较次数稳定在 $\log_{2} {k}$，其中 $k$ 是每次插入时已排定的元素个数，当然具体实现时还可以找到一些优化点，比如当遇到大小相等的元素时便可以原地插入，并不一定要二分法进行到最后。

这样在大部分情况下应该都能提高插入排序的效率，但如果原数组已经高度有序，那么效率反而不如标准版的插入排序，另外由于二分法插入是跳着进行比较的，所以这里用移动操作move代替了交换操作swap。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_insert_binary(Object[] array, Comparator comp) {
    if(array.length < 2){
        return;
    }else if(comp(array, 0, 1, comp) > 0){
        swap(array, 0 ,1);
    }
        
    if(array.length > 2){
        for(int i = 2; i < array.length; i++){
            int mid = mid(array, i, comp);
            if(comp(array, i, mid, comp) > 0){
                move(array, mid + 1, i);
            }else{
                move(array, mid, i);
            }
        }
    }
}
    
private static int mid(Object[] array, int target, Comparator comp){
    int left = 0;
    int right = target;
    int mid = (left + right) / 2;
    while(mid > left && mid < right){
        if(comp(array, target, mid, comp) < 0){ 
            right = mid; 
        }else if(comp(array, target, mid, comp) > 0){
            left = mid;
        }else{
            return mid; // 等于位置直接可以原地插入
        }
        mid = (left + right) / 2;
    }
    return mid;
}
    
private static void move(Object[] array, int mid, int target) {
    Object t = array[target];
    System.arraycopy(array, mid, array, mid + 1, target - mid);
    array[mid] = t;
        
    times_swap++;
    LOGGER.debug(String.format("%2s move： %s([%s]->[%s]) = %s", times_swap, t, target, mid, Arrays.toString(array)));
}

3. 希尔排序

由于插入排序对初始顺序的敏感性，那么对于一个数组，如果能提高其局部有序性，就可以降低在插入排序时的比较次数，而希尔排序应该就是基于这个想法对插入排序进行的改进。

具体做法是将原数组按照固定间隔 h 拆分成若干个独立的子数组，然后分别对这些子数组进行排序，那么对这些子数组的排序即提高了原数组的局部有序性，而由这些有序子数组构成的数组，我们称其为 h 有序。

考虑大规模的数组，如果最小元素在数组尽头，那么通过插入排序要将它移到正确的位置就需要 N-1 次比较和移动。而通过对数组进行 h 间隔拆分，如果 h 很大，那么就能一次将元素移动到很远的地方，然后再逐步减小 h 进行拆分，这样前面大 h 的排序结果就能为后面更小 h 的排序创造方便，并从整体上降低比较和交换次数，如果最终 h 为 1，那么就能将数组完成排序。

于是，希尔排序的性能就取决于 h 序列的选择，不仅取决于 h 的大小，还取决于 h 之间的公因子等数学性质，下面令 $h = h * 3 + 1$

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_xier(Object[] array, Comparator comp) {
    int h = 1;
    while(h < array.length / 3){ 
        h = h * 3 + 1; // 1, 4, 13, 40, 121,364, 1093 ...
    }

    while(h >= 1){
        LOGGER.debug("compare interval: {}", h); 
        for(int i = h; i < array.length; i++){
            for(int j = i; j >= h && comp(array, j, j - h, comp) < 0; j -= h){
                swap(array, j-h ,j);
            }
        }
        h = h / 3;
    }
}

上面示例中的算法，在已知最坏情况下所需的比较次数大约为 $N^{3/2}$，这样希尔排序通过一个小小的改变就提高了插入排序的效率，并打破了平方级别的复杂度屏障，而且数组越大，优势越明显。

至于希尔排序复杂度的数学证明问题，已经超出了这里的讨论范围，不过可以尝试证明：当一个 h 有序的数组按照增幅 k 排序之后，其仍然是 h 有序的

4. 归并排序

归并排序是分治思想的一种体现，要将一个数组排序，可以先递归地将它分为两半分别排序，然后再逐步将结果归并起来。

然后在每次合并操作时，都有一个前提，即左右两边数组都分别是有序的，这样在合并的具体实现中，可以通过判断来省略一些步骤，比如当左子数组的最右元素，大于右子数组的最左元素时，就可以直接判定原数组已经有序，从而省略 merge 操作，另外，如果在 merge 的过程中，发现一边数组的元素已经全部用完，则可以直接将另一边数组剩余的元素进行整体拷贝，无需再逐个比较。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_merge(Object[] array, Comparator comp) {
    Object[] temp = array.clone();
    recursion_mid(array, temp, 0, array.length - 1, comp);
}
    
private static void recursion_mid(Object[] array, Object[] temp, int low, int high, Comparator comp) {
    if(low >= high){
        return;
    }

    int mid = (low + high) / 2;
    LOGGER.debug("mid={}", mid); 

    recursion_mid(array, temp, low, mid, comp);
    recursion_mid(array, temp, mid + 1, high, comp);
    merge(array, temp, low, mid, high, comp);
}
    
private static void merge(Object[] array, Object[] temp, int low, int mid, int high, Comparator comp) {
    if(comp(array, mid + 1, mid, comp) >= 0){
        LOGGER.debug("mid={} merge skipped...", mid); 
        return;
    }

    System.arraycopy(array, low, temp, low, high - low + 1);
    int i = low, j = mid + 1;
    for(int k = low; k <= high; k++){
        if(comp(temp, i, j, comp) > 0){
            array[k] = temp[j++];
        }else{
            array[k] = temp[i++];
        }

        if(i > mid){ 
            System.arraycopy(temp, j, array, k + 1, high - j + 1); // skip left copy
            break;
        }else if(j > high){
            System.arraycopy(temp, i, array, k + 1, mid - i + 1);
            break;
        } 
    }
    LOGGER.debug("mid={} merge {}", mid, Arrays.toString(array)); 
}

归并排序的缺点是在合并结果时，需要借助临时数组来整理顺序，然后再将临时数组中已排序的元素按照对应位置拷贝回原数组，这就增加了空间复杂度，并且所需的额外内存空间与 N 成正比，但是它对于时间复杂度可以保证：对于长度为 N 的任意数组进行排序，所需的比较次数最多为 $O(N\log_{2} {N}) $

证明：

首先，对于任意长度为 $n$ 的数组，将其所需的比较次数（时间复杂度）记为：$T(n)$，那么有：$T(n) = 0$， $n \leq 1$

如果将长度 $n$ 的数组一分为二，则可以将其所需的比较次数表示为：$T(n) = 2 \times T(\frac{n}{2}) + C(n)$

$C(n)$ 表示两边子数组合并所需的比较次数，最差情况是两个数组中的元素交叉排列，比如 [2,4,6,8] 与 [1,3,5,7] 那么 $C(n) = n - 1$

下面将拆分次数记为：$k$

于是：$k = 1$，有：$T(n) = 2 \times T(\frac{n}{2}) + n - 1 $

对$\frac{n}{2}$继续拆分，即$k = 2$，则有：$T(n) = 2 \times (2 \times T(\frac{n}{4}) + \frac{n}{2} -1) + n - 1 = 4 \times T(\frac{n}{4}) + 2n - 1 - 2$

对$\frac{n}{4}$继续拆分，即$k = 3$，则有：$T(n) = 2 \times (2 \times (2 \times T(\frac{n}{8}) + n/4 - 1) + n/2 -1) + n - 1 = 8 \times T(\frac{n}{8}) + 3n - 1 - 2 - 4$

…

那么，在进行 $k$ 次拆分之后，则有：$T(n) = 2^k \times T(\frac{n}{2^k}) + kn - 1 - 2 - 4 - … - 2^{k-1} = 2^k \times T(\frac{n}{2^k}) + kn + 1 - 2^k$

并且，如果最终在 $k$ 次拆分之后，子数组的元素个数都为 $1$，那么就有：$2^k = n$

故：$T(n) = n \times T(1) + n\log_{2} {n} + 1 - n = n\log_{2} {n} + 1 - n \in O(n\log_{2} {n})$

类似的，在最好的情况下，每次合并操作只需要进行 $1$ 次比较，那么就有：$T(n) = 2^k \times T(\frac{n}{2^k}) + k = \log_{2} {n}$

5. 快速排序

快速排序也是分治思想的一种体现，它选取一个切分元素 K，然后将数组分成左右两个子数组，并保证左边子数组的所有元素都不大于 K，而右边子数组的所有元素都不小于 K，这样如果左右子数组都分别有序，那么整个数组就是有序的，然后，再对左右子数组以同样的方式进行递归操作，最终便完成了数组的排序。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_quick(Object[] array, Comparator comp) {
    recursion_partition(array, 0, array.length - 1, comp);
}

private static void recursion_partition(Object[] array, int low, int high, Comparator comp) {
    if(low >= high){
        return; 
    }
    
    int partition = partition(array, low, high, comp);
    LOGGER.debug(" partition={}", partition);
    
    recursion_partition(array, low, partition - 1, comp);
    recursion_partition(array, partition + 1, high, comp);
}

private static int partition(Object[] array, int low, int high, Comparator comp) {
    int i = low, j = high + 1; // 左右扫描指针
    while(true){ 
        while(++i < high && comp(array, low, i, comp) > 0){}
        while(--j > low && comp(array, low, j, comp) < 0){}
        if(i >= j){
            break;
        }

        swap(array, i, j);
    }

    if(low != j){
        swap(array, low, j); // 将切分元素交换到正确的位置 
    }
    return j;
}

快速排序与归并排序是互补的，它可以直接在原地排序，而不需要借助临时数组来进行整理和拷贝。但是在归并排序中，每次都能将数组等分为两半，而在快速排序中，切分的位置则取决于数组的内容。比如示例中的最后几趟，每次只能将子数组长度减1，因此如果数组原本就是有序的状态，那么快速排序的复杂度反而会降为 $N^2$ 级别。

但是快速排序相对更加简洁，其在切分方法的内循环中只需用一个递增的索引将数组元素与一个定值进行比较，而在希尔排序和归并排序的内循环中，一般还要移动数据，所以它们一般都会比快速排序慢。

快速排序的最好情况是每次都能刚好将数组等分，这时它的复杂度分析可以类似于归并排序，有：$T(n) = 2T(\frac{n}{2}) + n \in O(N\log_{2} {N})$，但最差情况为 $N^2$，这显然难以令人接受，不过人们对于快速排序的信心来自于其平均复杂度的证明，约为 $1.39N\log_{2} {N}$。

但是，对平均复杂度的证明需要每个切分位置的概率问题，这显然很复杂，书中通过一种通用的方式将问题转化为对曲线的积分计算问题，如果对数学有兴趣的话，可以研究一下。

改进

基于快速排序的特点，可以尝试做一些改进优化：

首先可以提高数组的顺序随机性，另外可以将小数组改为插入排序，比如在java.util.Arrays中启用插入排序的阈值就为7。

另外，可以每次从子数组中的小部分元素中计算一个中位数来进行切分，这样可以提高切分效果，但代价是需要计算中位数。

而在一些实际应用场景中，可能会存在大量重复的元素，这时如果使用标准快速排序，那么每次还是只选定一个切分元素将数组切分为两部分，但是如果能以切分元素为界，将数组分为小于、等于、大于三部分，那么就可以降低下一次递归子数组的长度，也就降低了后续切分和比较的次数，称为三向切分的快速排序。

其思路是从两侧将元素向中间靠，通过巧妙的设计三个索引lt,i,gt，其中lt是切分元素，i则是下一个要比较的元素
对于左端元素，如果小于切分元素就进行位置对调，
对于右端元素，每次比较前先与i交换位置，然后与i位置比较，如果等于直接将i右移一位，接着再对新的右端元素进行同样的操作

这样就保证i位置就是切分元素，而且与其重复的元素都在左侧附近，并以lt和gt为左右边界

.《算法》一书中的这个示例应该是有些问题，并不能正确排序，不过如果能看明白作者的意图，可以修正一下。另外，需要知道三向切分能提升性能的前提是数组中存在大量重复元素，因为其降低切分和比较次的背后，是以提高交换次数为代价的。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/Sorts.java

private static void sort_quick2(Object[] array, Comparator comp) {
    recursion_partition2(array, 0, array.length - 1, comp);
}

private static void recursion_partition2(Object[] array, int low, int high, Comparator comp) {
    if(high <= low){ // high - low <= 8 改为插入排序
        return; 
    }

    int lt = low, i = low + 1, gt = high;
    while(i <= gt){
        int cmp = comp(array, i, lt, comp);
        if(cmp < 0){
            swap(array, lt++, i++);
        }else if(cmp > 0){
            swap(array, i, gt--);
        }else{
            i++;
        }
    }
    recursion_partition2(array, low, lt - 1, comp);
    recursion_partition2(array, gt + 1, high, comp);
}

对于标准的快速排序，随着数组规模的增大其运行时间会趋于平均运行时间，大幅偏离的情况非常罕见，因此可以肯定三向切分快速排序的运行时间与输入信息量 N 是成正比的。在实际应用中这个性质很重要，因为对于包含大量重复元素的数组，它将排序时间从线性对数级降低到了线性级别。

关于空间复杂度

上面的讨论都是站在时间复杂度的问题上对各种排序算法进行的分析，但在实际应用中还有一个需要考虑的问题就是空间复杂度，即内存使用

下面主要从java实现的角度来分析一下其内存使用情况，因为对于一个使用java作为第一开发语言的程序员来讲，实现各种算法或数据结构时，一般都是先将数据封装成对象，比如链表中的节点Node，如果要考虑内存消耗，那么首先就是计算其中有多少属性数据以及哪些引用。

java最重要的特性之一就是其内存分配系统，它的目标是希望将开发者从对内存的操作之中解脱出来。作为一个面向对象的语言，它可以在对象头中记录一些额外信息，比如类引用、锁信息以及垃圾收集信息，然后配合引用计数统计信息，便能实现对垃圾对象占用内存的自动回收（当然具体实现肯定还需要考虑很多问题），然后以对象为单位统一对内存进行申请和释放操作。

对应的java中定义了8种基本数据类型，以及一个引用类型 reference（指向一个地址）

类型	字节
boolean	1
byte	1
short	2
int	4
float	4
long	8
double	8
reference	8

对于一个java对象，其内存消耗等于它所有实例变量使用的内存加上对象本身（对象头，一般是16字节）开销，以及对其填充（64位机器上，一般会将对象的内存使用填充为8的倍数）。

比如一个int所需的内存为4字节，而对应的一个Integer则需要24字节，数据4字节，对象头16字节，对其填充4字节；
对于一个长度为 N 的int数组，其所需内存为 24 + 4N，数组对象头24字节，因为需要额外4字节来存储数组长度，然后有4字节作为填充；
而对于一个长度为 N 的Integer数组，则需要 24 + 32N 字节，数组对象头24字节，每个Integer对象24字节，以及每个引用占用8字节

一般在设计一个通用的容器或者排序工具时，都会考虑使用泛型，而java中的泛型是通过在编译器中进行简单的类型擦除和强制转换来实现的，这就导致了其无法支持基本数据类型（因为基本类型与Object之间无法强制转换），然后java通过提供基本类型的自动装箱/拆箱操作来弥补了这个问题，但是这样是以降低性能以及更多的内存消耗作为代价的。所以java需要在JVM通过各种办法来对执行过程进行优化确实是一种刚需，它不像C++一样将优化手段直接放在编译器中进行，当然，作为具体语言的使用者只能聊聊一些使用体会，很难站到语言设计者的高度去考虑和权衡他们遇到的问题。

参考：