排序指的是将一组对象按照特定的逻辑顺序重新排列的过程，排序的应用十分广泛，可以说是无处不在，它在商业数据处理和现代科学计算中发挥着举足轻重的作用，目前已知的应用最广泛的排序算法—快速排序，更是被誉为了 20 世纪科学和工程领域的十大算法之一。

排序算法有很多，有比较常见的有比如插入排序、归并排序、快速排序，就是我接下来会讲解的这几种；也有一些非常冷门的排序算法，有一些可能你连名字都没听过，例如鸡尾酒排序、侏儒排序、图书馆排序、耐心排序、臭皮匠排序等等……

这篇文章的篇幅较长，涉及到大量图例、证明、代码示例，一次性全部看完可能有点困难，可以分几次多看几遍，自己思考一下，结合一些经典书籍资料等等，相信看完之后你对排序算法的认识会有很大的提升。

在开始讲解之前，先定义一个游戏规则，为了复用部分代码，我写了一个排序的抽象类，当然你可以转换成任何你熟悉的编程语言，如下：

public abstract class AbstractSort {
    public abstract void sort(Object[] nums);
    /**
     * 比较两个数的大小
     */
    @SuppressWarnings({"unchecked", "rawtypes"})
    public boolean compare(Object v, Object w){
        return ((Comparable)v).compareTo(w) < 0;
    }
    /**
     * 交换两个数组元素
     */
    public void swap(Object[] nums, int i, int j){
        Object temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    /**
     * 输出数组内容
     */
    public void showArray(Object[] nums){
        for (Object num : nums) {
            System.out.print(num + " ");
        }
    }
}

这个类里面的方法也很简单，一个 sort 抽象方法，后续的排序实现类都会实现这个方法，来填充具体的排序逻辑；排序的操作基本上都会依赖比较和交换，因此写了一个 compare 比较方法，比较两个数字的大小，还有一个 swap 方法交换两个数组的元素；最后是一个 showArray 方法，打印出数组内容查看排序的结果是否符合预期。

然后再介绍两个基本的概念，在文章里接下来的分析中我会经常提到：

复杂度

按照惯例，对算法的分析需要关注其复杂度，包括时间复杂度和空间复杂度，排序算法当然也不例外。对于不占用额外的存储空间，空间复杂度是 O(1) 的排序，有一个专用的名词来称呼，叫做原地排序。

稳定性

稳定的排序指的是在排序前后，相等的值的先后顺序不会发生改变，反之即是不稳定的排序。举个例子，一组数据 3 4 4 2 1 5，排序之后是 1 2 3 4 4 5，数组中有两个 4，如果排序之后，两个 4 的先后顺序没有改变，则称排序算法是稳定的。稳定的排序算法在某些特定的场景中会非常有用。

一、基础排序

1. 冒泡排序

很容易想到的一种排序思路是，每次都遍历数组，查看相邻的两个数字的大小并交换位置，这样每次都能够将较大的那个元素移动至数组的另一端。每一次遍历，较大的元素都会像气泡一样慢慢的“浮动”至数组另一端，这便是这个算法被叫做冒泡排序的原因。

下面这张动图展示了冒泡排序的整个过程：

E}FF7%QZN)27R1C$@2RVPT3.png

冒泡排序很容易理解，复杂度也很好分析，在最好的情况下，如果数组本来就是有序的，那么只需要遍历一次数组即可，时间复杂度是 O(n)，在最坏的情况下，每排列一个数据，都需要遍历整个数据集，因此时间复杂度是 O(n²)，平均情况下也接近 O(n²)。排序过程不会使用到额外的存储空间，因此空间复杂度是 O(1)，是原地排序。

冒泡排序是稳定的吗？从上面的图中可以看到，每次比较都是交换的两个数值不相等的数据，而相等的数据要么不满足条件不移动，要么满足条件则全部移动，这保证了相等数据的前后顺序不发生改变，因此冒泡排序是稳定的。

下面是一个简单的代码实现供参考：

public class BubbleSort extends AbstractSort {
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int n = nums.length;
        boolean swap = true;
        for (int i = 0; swap && i < n; i++) {
            swap = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (compare(nums[j + 1], nums[j])){
                    swap(nums, j, j + 1);
                    swap = true;
                }
            }
        }
    }
}

需要注意的是，代码中使用到了一个辅助变量 swap，它的作用是标识数据是否已经没有交换了，如果没有则说明数据已经有序了，直接跳出循环，这样可以避免多余的冒泡操作。例如数据 1 2 3 4 5 6，第一遍历之后，发现已经是有序的了，就没有必要再进行后续的遍历。

2. 选择排序

选择排序也很容易理解，对于一个要排序的数组，我们每次都从数组中寻找最小值，并把它和第一个元素交换，然后在剩下的数据中继续寻找最小值，然后将其与数组第二个元素交换，如此循环往复，直到整个数组有序。

下面这张动图可以帮助你理解选择排序的整个过程：

X4O5269_DY@4G})LCL9}1[G.png

无论在最好还是平均情况下，选择排序的时间复杂度都是 O(n²)，因为就算是要排序一个已经有序的数组，选择排序的逻辑还是要遍历数组寻找最小值。空间复杂度则和冒泡排序一样，是 O(1)。

需要注意的是，选择排序是不稳定的，这是由它的交换特性决定的，我举个例子就容易明白了，例如数据 3 3 2 0 1 5，第一次遍历，我们找到了最小值 0，并把它和第一个数据 3 交换位置，那么这两个 3 的前后顺序就被改变了，因此选择排序不能保证稳定性。

下面是一个简单的代码示例供参考：

public class SelectionSort extends AbstractSort {
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i + 1;
            for (int j = i; j < n; j++) {
                if (compare(nums[j], nums[min])){
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

3. 插入排序

插入排序的基本思路是：依次遍历每一个数字，并将其和前面已排序的数据进行对比，将其插入到合适的位置。生活中也有很多这样的例子，假如我们手中有一副扑克牌，当新来了一张扑克牌之后，我们便会依次查找，将新来的扑克牌放到合适的位置。

插入排序的过程如下图：

2E]2}R78G6PK%~$%[G~T33F.png

插入排序的时间复杂度和冒泡排序类似，这里不再赘述了，平均情况下的时间复杂度是 O(n²)，空间复杂度是 O(1)，是原地排序。并且插入排序也是稳定的，从上图也很容易明白，在每个数据的遍历交换过程中，相同数据的前后顺序肯定不会被改变。

下面是一个简单的代码示例供参考：

public class InsertionSort extends AbstractSort {
      @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int j = i + 1;
            Object k = nums[j];
            while (j > 0 && compare(k, nums[j - 1])){
                nums[j] = nums[--j];
            }
            nums[j] = k;
        }
    }
}

4. 希尔排序

希尔排序其实是插入排序的一个优化版本，如果你搞懂了插入排序，那么弄懂希尔排序就非常容易了。回想一下，插入排序的特点是：每次比较的时候交换相邻元素，因此数据每次只能移动一位。如果这样的话，对于一些大规模乱序的数据，例如最大值刚好在头部，那么将其移动至尾部，需要移动大概 n - 1 次。

而希尔排序则将数据分成了 n 个组，对每个组内的数据分别进行插入排序，这样就能够将较大的数据一次性移动很多位，为后续的比较交换提供了便利。文字描述起来可能比较的晦涩抽象，可以结合下面的图来看一下：

5N[GK6G@Q5[R9DSLU]81LP2.png

我们先定义一个增量 k，k 一般为数组长度的 1 / 2 ，上图中要排序的原始数据的个数是 8 ，因此 k = 8 / 2 = 4，所以第一次可以将数组分为 4 组，分别是 (9, 5), (2, 1), (4, 0), (3, 6)，即上图中用直线连接起来的数据，然后将每个组内的数据分别进行插入排序，那么第一次排序之后的结果为：5 1 0 3 9 2 4 6。

可以看到最开始 9 在数组最前面，但是经过第一次排序之后，9 已经向后移动了 4 位，相较于插入排序，这样就减少了移动的次数，希尔排序的性能提升就主要体现在这里。

然后继续进行分组，这时 k 缩小一半变为 2，因此我们将数组分为两组，然后在组内再进行插入排序，如下图：

3UI[PKCBW7CH`8}OX7S%WPA.png

此时分为了两组，分别是(5, 0, 9, 4), (1, 3, 2, 6)，进行排序之后的结果是：0 1 4 2 5 3 9 6，可以看到此时数组已经基本上是有序的了。

然后 k 再次缩小为 1，我们将数组分为 1 组，其实就是原始的数据了，然后再进行一次插入排序，由于其实数据已经是基本上有序的了，因此只需要微调即可，一般不会进行大量的数据移动：

U26IRNR37GA~[G[[HQ(I@0Z.png

整个排序的过程当中，增量 k 是一步一步缩小的，正因此，希尔排序其实也叫做缩小增量排序。

下面是一个简单的希尔排序的代码示例：

public class ShellSort extends AbstractSort {
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int n = nums.length;
        int k = n / 2;
        while (k >= 1){
            for (int i = 0; i < n - k; i++) {
                int j = i + k;
                Object v = nums[j];
                while (j > k - 1 && compare(v, nums[j - k])){
                    nums[j] = nums[j - k];
                    j = j - k;
                }
                nums[j] = v;
            }
            k = k / 2;
        }
    }
}

希尔排序的时间复杂度比较难分析，可以大致概括为 O(nlog²n)，但实际上它和定义的增量、数据本身的排列特性等相关，有很多相关论文都进行了分析，但都无法得到具体选择哪个增量是最好的。已知的最好的增量是 Sedgewick 提出的 (1, 5, 19, 41, 109,……)，感兴趣的可以看下 wikipedia 上关于步长序列的描述：维基百科—希尔排序

希尔排序的空间复杂度很好理解，是 O(1)，并且希尔排序是不稳定的，因为它和选择排序类似，都是跳着进行数据的交换，这样就会破坏稳定性。

当数据量较小的时候，希尔排序是一个不错的选择，但是它并没有被广泛的应用，因为在数据量较大的时候，我们更倾向于使用复杂度更优的 O(nlogn) 的排序算法。

5. 总结

前面说到的这几种基础排序算法，在实际当中的使用并不是很多，因为它们的时间复杂度较高，应用在大规模数据中的话，效率将会非常低下，因此它们只适合小规模的数据排序。例如 Java 中的双轴快速排序，在数据量小于 47 时便使用了插入排序。

你也许会纳闷，为什么插入排序、冒泡排序、选择排序的平均时间复杂度都是 O(n²)，但是在大多数情况下，针对数据量较少的情况，一般都会采用插入排序呢？

简单分析一下，选择排序就不用说了，因为它的性能并没有绝对优势，即便是在数组已经有序的情况下，它的时间复杂度仍然是 O(n²)，并且它还不是稳定的，因此选择排序一般并不会考虑使用。

接下来再看看冒泡排序和插入排序，这两者虽然时间复杂度是一样的，但是在实际的排序过程中，冒泡排序的数据交换次数更多，你可以从上面的代码示例中看到，冒泡排序的一次交换涉及到三次操作，而插入排序只需要一次数据赋值，这样的话便使插入排序要稍微快一些。

你可以构造一组随机数据来测试这两种排序算法，例如我在本机测试了一组 5 万个数据，冒泡排序的耗时是 8 秒多一点，而插入排序只使用了不到 3 秒。

//冒泡排序，swap 函数涉及到三次赋值操作
for (int j = 0; j < n - i - 1; j++) {
   if (compare(nums[j + 1], nums[j])){
     swap(nums, j, j + 1);
     swap = true;
   }
}
//插入排序，交换时只需要一次数据赋值
while (j > 0 && compare(k, nums[j - 1])){
   nums[j] = nums[j - 1];
   j--;
}

最后再来看看希尔排序，希尔排序发明于 1959 年，它是最早的时间复杂度突破 O(n²) 的排序算法之一，但是它的应用并不是很广泛，原因在于它遇到了更强劲的“对手”，相较于归并排序，它并不是稳定的，而相较于快速排序，它的性能又没有任何优势可言，因此归并排序和快速排序更受青睐。

二、归并排序

在介绍归并排序之前，先简单说下分治思想。分治，顾名思义就是分而治之，它是一种解决问题的思路，将原始问题分解为多个相同或相似的子问题，然后将子问题解决，并将子问题的求得的解进行合并，这样原问题就能够得到解决了。分治思想是很多复杂算法的基础，例如归并排序、快速排序、二分查找等等。

言归正传，再来看归并排序，它的概念理解起来非常简单，如果我们要对一组数据进行排序，我们可以将这个数组分为两个子数组，子数组再进行分组，这样子数组排序之后，将结果合并起来，就能够得到原始数据排序的结果，相信你已经发现了，这就是典型的利用分治思想解决问题的思路。

下面这张图展示了将一个问题分解为多个子问题的过程：

E]Z2]CQIY72ZZ6K[L9MSW2A.png

子问题得到解决之后，需要将结果合并，合并的过程如下图：

F%`HFIRJC@YOQ$)TLRQZ260.png

下面的动图比较直观的展示了归并排序的整个过程，可以对照起来理解一下：

U%9W@YO%)$5HZ{MNYHJ@W[R.png

如果使用一个简单的公式来表示归并排序的话，那么可以写成这样：

merge_sort(data, p, r) = merge(merge_sort(data, p, q), merge_sort(data, q + 1, r));

我来简单解释一下这个公式，我们将排序的数组叫做 data，p 和 r 分别表示其起始和终止下标，因为要进行分组，因此取 p 和 r 的中间值 q，然后对 p 到 q 和 q + 1 到 r 的数据分别再进行排序。

排序之后的结果需要用一个合并的函数来将结果合并，这个函数可以叫做 merge，merge 函数的功能很简单，对于两个已排序的数据区间，假设下标是 p ~ r，我们可以新建一个临时数组，然后依次比较两个已排序的数据区间的值，并将其一一复制到临时数组中，你可以结合下图来理解一下：

GJ]Z)1NMC(ST$GMUSPW]B61.png

理解了这些之后，再来看归并排序的代码实现就会非常简单了，下面是一个代码示例：

public class MergeSort extends AbstractSort {
    private Object[] temp;
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int n = nums.length;
        temp = new Object[n];
        sortHelper(nums, 0, n - 1);
    }
    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }
        int q = p + (r - p) / 2;
        sortHelper(data, p, q);
        sortHelper(data, q + 1, r);
        merge(data, p, q, r);
    }
    private void merge(Object[] data, int p, int q, int r){
        int i = p, j = q + 1;
        System.arraycopy(data, p, temp, p, r - p + 1);
        for (int k = p; k <= r; k++) {
            if (i > q) data[k] = temp[j++];
            else if (j > r) data[k] = temp[i++];
            else if (compare(temp[j], temp[i])) data[k] = temp[j++];
            else data[k] = temp[i++];
        }
    }
}

2.1 算法分析

归并排序的时间复杂度，一般可以使用两种方式来进行推导，假如将要排序的数组的长度记为 n，排序一个长度为 n 的数组的时间记为 T(n)，由于归并排序需要将原问题分解成子问题，因此 T(n) 又可以写成 T(n) = 2 * T(n/2) + n，其中 n 表示合并两个子数组所需要的时间。

然后继续进行分解，这个公式可以表示成这样：

T(n) = 2 * T(n/2) + n

= 2 * ( 2 * T(n/4) + n/2) + n = 4 * T(n/4) + 2n

= 2 * ( 2 * (2 * T(n/8) + n/4) + n/2) + n = 8 * T(n/8) + 3n

… … …

= 2^k * T(n/2^k) + k*n

可以看到，时间计算公式可以记为：T(n) = 2^k T(n/2^k) + k n，当 n / 2^k = 1 的时候，可以得到 k = logn，然后再将 k 代入到公式中，可以得到 T(n) = Cn + nlogn （C 为常数），使用大 O 表示法，那么归并排序的时间复杂度可以大致记为 O(nlogn)。

当然这种分析方式较为复杂抽象，还有一种更加简单直观的方式，我们可以将归并排序的过程使用树的方式，形象的展示出来，大致就是这样的：

225)$Y(N$0}OORYZK{7CD`D.png

可以看到，归并排序的时间复杂度可以使用树结构分级展示，每一层涉及到的操作是分组和合并，所消耗的时间都是一样的 n，因此算法的总体时间复杂度就是 n * 树的高度，可以很明显的看出，这是一颗满二叉树，满二叉树的高度一般是 logn，因此归并排序的时间复杂度就是 O(nlogn)。

归并排序的空间复杂度比较简单，从代码中可以看到，当进行子数组合并的时候，需要一个临时数组 temp，数组的长度等于要排序的数组长度，因此空间复杂度可以表示为 O(n)。

其实归并排序并没有像快速排序那样应用广泛，其中很重要的原因便是它并不是原地排序算法，这是它的一个致命弱点。

最后思索一下归并排序是稳定的吗？这个问题比较好理解，数组的拆分并不会涉及到数据交换，只有合并才会，因此归并排序是否稳定主要取决于 merge 的过程。

假设我们需要合并 1 3 3 5 和 2 3 4 6，可以看到在合并的过程当中，我们的判断条件是单一的，如果第一个数字被放到的了临时数组中，那么后续相同的数字也会依次被放到临时数组中，前后顺序不会被改变，因此归并排序是稳定的。

2.2 自底向上

上面讲到的归并排序是最常见的一种类型，它的特点是自顶向下进行数据拆分，你可以从最开始的分解图清晰的看出来，其实还有另外一种归并排序，它的顺序恰恰相反，是自底向上的，只不过这种方式理解起来并不如上面的直观，你可以简单做个了解。

其思路是这样的：首先进行两两归并（你可以将数组想象成多个只有一个元素的子数组），然后是四四归并（将长度为 2 的子数组合并为长度为 4 的子数组），然后是八八归并，一直进行下去。

下面是一个简单的代码示例：

public class MergeSortBottomUp extends AbstractSort {
    private Object[] temp;
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int n = nums.length;
        temp = new Object[n];
        for (int i = 1; i < n; i = 2 * i) {
            for (int j = 0; j < n - i; j += (2 * i)){
                merge(nums, j, j + i - 1, Math.min(j + 2 * i - 1, n - 1));
            }
        }
    }
    private void merge(Object[] data, int p, int q, int r){
        if (compare(data[q], data[q + 1])){
            return;
        }
        int i = p, j = q + 1;
        System.arraycopy(data, p, temp, p, r - p + 1);
        for (int k = p; k <= r; k++) {
            if (i > q) data[k] = temp[j++];
            else if (j > r) data[k] = temp[i++];
            else if (compare(temp[j], temp[i])) data[k] = temp[j++];
            else data[k] = temp[i++];
        }
    }
}

经典排序算法分析（一）

复杂度

稳定性

一、基础排序

1. 冒泡排序

2. 选择排序

3. 插入排序

4. 希尔排序

5. 总结

二、归并排序

2.1 算法分析

2.2 自底向上

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

经典排序算法分析（一）

复杂度

稳定性

一、基础排序

1. 冒泡排序

2. 选择排序

3. 插入排序

4. 希尔排序

5. 总结

二、归并排序

2.1 算法分析

2.2 自底向上

热门文章

最新文章

相关课程

相关电子书

相关实验场景