典型排序问题

我们在实际生活中可能会遇到各种各样的排序问题，比如：对学生信息进行排序，信息可能有学号，成绩，电话等

这里可能需要针对某些关键字（key）进行排序，比如按 key = name 排序

我们在排序时除了按名称也可能按学号，name 是 String 类型，学号是 Int 类型，也可能是 Long，我们还可能在真实的场景中遇到其他的类型，如日期，文件等，所以我们应该设计一个可以满足各种数据类型的排序算法 sort()

我们的目标是：可以对任何类型数据进行排序
问：在无法预知需要排序的 key 是什么类型时，比如 String, Integer, Long 甚至是 java.io.File 类型，sort()方法该如何对数据进行比较呢？

我们可以使用回调方法来解决这个问题

• 客户端将要排序的数组传给 sort() 方法
• sort() 方法按需调用对象的 compareTo() 方法来进行真正的比较

如何实现这个回调方法呢，不同的语言都有类似的解决方案，如下：

• Java: interfaces
• C: function pointers.
• C++: class-type functors.
• C#: delegates.
• Python, Perl, ML, Javascript: first-class functions.

本文以 Java 为例

Java Comparable Interface

public interface Comparable<T> {
   public int compareTo(T that);
}

需要比较的类型都实现这个接口，并实现 compareTo 方法就可以了

public class File implements Comparable <File> {
    ...
    public int compareTo(File b) {
        ...
        return -1;
        ...
        return +1;
        ...
        return 0;
    }
}

如果是自定义的类要进行比较也是同样的实现，自己定义比较的规则

对于两个值的比较有三种情况 ，compareTo 对应的是

v > w : v.compareTo(w) > 0
v = w : v.compareTo(w) = 0
v < w : v.compareTo(w) < 0

接下来我们来讨论几种经典的排序算法，并对其性能进行逐一分析
在讨论这些算法之前，我们先抽象几个排序方法都会用到的工具方法，我们定义一个基类 Sort

包含以下几个方法

• Less: 判断 ?
• Exchange: 交换目标排序数组
• isSort: 测试数组是否是有序的

public class Sort {
    public static boolean less(Comparable v, Comparable w) {
         return v.compareTo(w) < 0;
    }

    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i] + "");
        }
        System.out.println();
    }

    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) return false;
        }
        return true;
    }
}

选择排序

这是一种非常简单的基本排序方法，核心思想如下：

1. 找到数组中最小的元素 A1
2. 将 A1 与数组的第一个元素交换位置
3. 在剩下的数组中找到最小的元素 A2
4. 与数组的第二个元素交换位置
5. 如此循环直至将整个数组排好序

图解过程如下

选择排序图解

代码实现：

public class SelectionSort extends Sort {
    public void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (less(a[j], a[minIndex])) minIndex = j;
           }
            exch(a, i, minIndex);
        }
    }
}

性能分析

• 比较次数： 次
• 交换次数： 次

我们可以画一下排序过程来验证上面的结论

选择排序轨迹图

我们找到最小元素后就需要进行一次交换 ，所以是 次交换，而每次交换后，左边部分的元素已经是有序了，无需再参与比较，所以是 次比较，我们也可以直接观察图，图中黑色部分就是每次遍历比较的元素，网格是 大小，黑色和灰色部分各占了一半

时间复杂度
我们可以观察到，这个排序算法无论如何都需要进行 次比较，也就是说不管这个数组输入时是什么样的，即便是排好序的一个数组，也需要这么多次比较，意味着在最好的情况下这个算法并不会减少开销
结论：最好时间复杂度=最坏时间复杂度=平均时间复杂度=

hmm，一看就不是什么好的排序算法

空间复杂度

因为我们在算法执行过程中只是在交换时申请了一个临时常量空间，下一次执行前这个空间就会释放掉，所以相当于只有 1 个空间开销，空间复杂度为 ，注意 是指常量级，并不是特指 1 个，如果这里 的空间开销是 2，3，4 这样的可数常量，也是

我们在分析排序算法时，还有一个重要的指标：是否是稳定排序
稳定排序是指如果我有两个值相等的元素，但是在 不同的位置上，比如有两个 E，一个在索引 1 上，一个在索引 4 上，排完序是否能保证，1 上的 E 是否仍排在 4 上的 E 之前，这个非常重要，因为在实际的场景中我们排序的元素一般都是含有多个字段的对象，比如前面说的学生信息，如果需要先对学号排序，再对分数进行排序，如果排序是不稳定的，那我们怎么排都无法达到我们想要的效果了。

这里的选择排序明显是非稳定排序，因为每次交换都是选一个最小值与未排序的第一个进行交换，破坏了原来元素的相对顺序，大家可以打印元素地址来进行验证

插入排序

1. 数组分为两部分，左边是排好序的，右边是未排序的
2. 每次取未排序的第一个元素与排好序的部分进行比较
3. 如果比排好序的元素小，则交换位置直至左边元素全部升序排列

我们看下图解过程

插入排序

根据以上步骤实现代码

public class InsertionSort extends Sort {
    public void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0; j--) {
            if (less(a[j], a[j - 1])) {
                exch(a, j, j - 1);
            } else break;
        }
    }
}

性能分析

比较次数：
交换次数：

同样我们画一下算法轨迹来验证

插入排序轨迹图

右边有一半的数据没有被比较，左边有序的部分大概也是比较交换一半的数据，所以是 左右次比较和交换

前面的选择排序在最好和最坏情况下的时间复杂度都是一样的，无论输入数据是否有序都不会有任何区别，而插入排序在最好和最差情况下是不同的

时间复杂度

• 最好情况：数据已经全部升序排列，这种情况就只需要 次比较，0 次交换
• 最差情况：数据降序排序，则需要 次比较和交换
• 空间复杂度：与选择排序一样
• 稳定排序：是，我们在交换数据时，只在前面的数据比后面大的情况下进行交换，所以如果相同数值的数据已经在前则不会被交换了，所以是稳定的

逆序对 INVERSION

这里我们引入一个定义 逆序对（inversion） 来表示初始数据的有序情况，即在一组数据中有多少对数据是不符合我们预期顺序的

比如下面这组数据，我们希望升序排列

将它们按初始的顺序两两组合，不是升序的对如下：

共3个逆序对

当一个数组的逆序对数量 （ 为远小于 的常量）时，我们称这个数组是部分有序的

由此我们可以得出这样的结论：对于部分有序的数组而言，插入排序的时间复杂度是线性的，因为交换次数就等于逆序对数， 就是线性时间复杂度

希尔排序

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的，这样的数组被称为 h 有序数组。

希尔排序是在插入排序的基础上实现的，是对插入排序的一种优化，也称缩小增量排序，由DL．Shell于1959年提出.

因为插入排序一次只进行一次位移，但排序过程其实需要移动很多次，所以希尔算法的思想是，我们一次移动多个位置，这种操作方式叫做 h-sorting 数组

h-sorting 数组

一个 h-sorted 数组就是以 h 为步长的数据组成的子数组是有序排列的，如下图所示

希尔排序

实现方式

实现一种排序算法，每次减少 h 的数值，比如先是实现一个 13-sorted 数组，进行数值交换，然后是 4-sorted，再进行数值交换，最后是 1-sorted ，这样整个数组就有序了

那么如何实现 h-sorted 呢，其实就是通过插入排序的方式来实现的，只是指针移动时的步长不同而已

代码如下

public static void sort(Comparable[] a) {
    int N = a.length;
    int h = 1;
    while (h < N / 3) h = 3 * h + 1;  //1, 4, 7...
        while (h >= 1) {
            for (int i = h; i < N; i++) {
            for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                exch(a, j, j - h);
            }
        }
        h = h / 3;
    }
}

为什么使用插入排序呢

1. 如果 h 比较大，那么我们的子数组数据就会很小，这种情况下插入排序的性能会很好，当然其他排序的性能也不会差
2. h 是逐渐减小的，也就是说h 越小，数组的有序度就会高，因为前面已经对 h 比较大的情况进行了部分排序，我们前面在分析插入排序时发现，在数组部分有序时插入排序性能能达到线性时间复杂度

接下来我们来看看一个数组分别使用 7，3，1 作为步长进行希尔排序的轨迹

希尔排序轨迹图

在进行希尔排序时应该如何选择 h 的值呢？

2 的次幂：1, 2, 4, 8, ...

使用 2 次幂无法正确排序，因为它不会将偶数位与基数位的值进行比较，所以不会全覆盖
那么基于这个问题，大家尝试了 2 的次幂 - 1

2 的次幂 - 1： 1，3，7，15，...

这个是可以正确排序的

knuth 提出的序列为 ，一般我们使用这个序列

3x + 1: 1, 4, 13, 40, 121, ...

这个是效果比较好的一个增量序列，因为计算起来很方便，每次我们只需要 /3 就可以了，当然我们的 h 值肯定不能大于数组的长度

选择 h 值是一个比较大的研究课题，这里不展开讨论

性能分析

最坏时间复杂度：时，最差时间复杂度为 .
当然实际情况要比这个快很多，应该是在 ~ 之间，目前关于希尔排序还没有特别好的模型，还有很多研究正在进行中，只能说目前的性能是这样的标准，后续可能会有更优的方案

希尔排序的优点

1. 性能比较好，除非数据非常非常大
2. 代码量比较少

实际上在代码量非常非常大的情况下，一般都不会使用单一的算法来完成，而在代码非常少的情况下就拥有了这种性能的算法并不多，因为一般达到这个性能的算法都会对数组进行大大小小的分区，代码量比希尔排序要大得多，所以希尔排序非常适合用在嵌入式或者硬件排序系统中。

关于希尔排序的研究和优化还远没有结束，而且据 DL．Shell 提出以来，大家已经为此努力了几十年，仍没有一个最优的解决方案

小结

算法	最好时间复杂度	最坏时间复杂度	空间复杂度	是否稳定排序
选择排序				❌
插入排序				✅
希尔排序				✅

本文由 coursera 上的算法第四版的公开课内容整理而成，这个公开课是算法（第四版）的作者 Robert Sedgewick 主讲，课程内容非常好，代码在这里，会持续更新课程内容上的代码实践以及课后的作业

参考资料

• 算法（第四版）
• Algorithms, Part I