十大经典排序算法详解

排序算法是《数据结构和算法》中非常基础的算法，但却占据着十分重要的位置，几乎可以说是我们在日常编程代码中使用最频繁的基础算法。本文对常见的十大经典排序算法进行了详细的知识点梳理，从排序思路、动图演示、代码实现、复杂度分析、算法优化等多个方面分别对不同的排序算法进行讲解，内容翔实，一篇文章几乎囊括了排序算法所有必会的知识点。

1.排序算法的分析和评价

时间复杂度

• 最好情况、最坏情况、平均情况时间复杂度

  分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。之所以这样区分分析，一是便于排序算法的对比分析，二是待排序数据有的接近有序而有的则完全无序，我们需要知道排序算法在不同数据下的性能表现，从而能够在不同的场景下选择更加适合的排序算法。

• 时间复杂度的系数、常数 、低阶

  时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候通常会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

• 比较次数和交换（或移动）次数

  基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

空间复杂度

排序算法的空间复杂度引入了一个特别的概念，即原地排序 (Sorted in place)，也称内部排序。原地排序算法特指空间复杂度是 $O(1)$ 的排序算法，也就是不借用外部多余的（内存）空间消耗，只占用待排序数据原有的空间。

稳定性

排序算法还有一个重要的度量指标是稳定性。它表示如果待排序的数列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。稳定性也是实际业务中必须要考虑的因素，比如交易系统，订单金额可能一样，但订单依然有时间上的前后顺序关系。从稳定性角度来讲，有稳定的排序算法也有不稳定的排序算法¹。

2.十大排序经典算法总览

2.1.排序算法的分类

为了便于集中分析，我们可以把经典的十大排序算法进行分类。

按时间复杂度，可以把排序算法分为平方阶、对数阶、线性阶三类；

按空间复杂度，可以分为原地（In-place）排序算法和非原地（Out-place）排序；

按稳定性，可以分为稳定排序算法和不稳定排序算法；

按是否基于比较，可以分为比较排序算法和非比较排序算法。

2.2.排序算法的性能

*符号说明：$n$ 为数据规模，$k$ 为分桶数量。

2.3.各阶复杂度性能对比

2.4.排序算法的初始状态影响

1. 算法复杂度与初始状态无关的算法：

   选择排序、归并排序、堆排序、基数排序。

2. 总排序趟数与初始状态无关：

   快速排序的排序次数（递归深度）与分区点选择（初始状态）有关，还有一个优化后的冒泡排序和后序是否有序有关，其他均只与总长度 n 有关，与初始状态无关²。

3. 元素总比较次数与初始状态无关：

   基数排序、选择排序。

4. 元素总移动次数与初始状态无关：

   基数排序、归并排序。

2.5.排序算法选择经验

1. 待排序数组规模 $n$ 较小时（如 $n \le 50$），可采用直接插入或直接选择排序；
2. 若初始状态基本有序（正序），则应选用直接插入、冒泡或快速排序为宜；
3. 当待排数组规模 $n$ 较大时，则应采用时间复杂度为 $O(n \log n)$的排序方法：快速排序（效率更高）、堆排序（原地排序）或归并排序（稳定排序）；
4. 数据范围不大的整数、存在很多重复元素的排序场景，可以考虑使用计数排序；
5. 数据范围固定、数值都比较大（位数较多）的场景，可以考虑使用基数排序；
6. 可以利用快速排序在 $O(n)$ 的时间复杂度内查找一个无序数组中的第 K 大元素；
7. 可以利用堆排序高效计算 TopK 或者流式数据的中位数。

3.十大经典排序算法详解

3.1.冒泡排序（Bubble Sort）

思路

冒泡排序的基本思路是重复地走访要排序的数列，每次比较两个相邻元素，顺序错误则交换位置（大的下沉放后面、小的上浮放前面），重复进行直到没有元素再需要替换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。冒泡排序名字由来是因为越小或越大的元素会经由交换慢慢 “浮” 到数列的顶端（升序或降序排列），如同一个个上升的气泡。

场景

适用于元素较少和数组基本有序的情况。

步骤

1. 比较相邻的元素，如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较³。

动图

主要动作：比较和移动

代码

性能

• 时间复杂度

  • （最好）当输入的数据已经是正序时，不需要进行排序，$O(n)$。

  • （最坏）当输入的数据是反序时，n 个元素每个元素都要交换 n 次，所以是 $O(n)$。

  • （平均）冒泡排序的时间复杂度和逆序度有关系，每交换一次，有序度就加 1。不管算法怎么优化改 进，交换次数总是确定的，即为逆序度（这个也是冒泡排序的一大缺点，可优化空间太小），逆序对也就是满有序度 – 初始有序度（相当于排序后的有序度减去开始排序前的有序度）。

    有序度是数列中具有有序关系的元素对的个数，逆序度定义相反，完全有序的数列的有序度叫作满有序度，值为 $n \times(n-1)/2$，逆序度 = 满有序度 – 有序度。排序的过程就是一种增加有序度，减少逆序度的过程，直到最后达到满有序度。

    最坏情况下，初始状态的有序度是 0，所以要进行 $n \times(n-1)/2$ 次交换。

    最好情况下，初始状态的有序度是 $n \times(n-1)/2$，就不需要进行交换。

    我们可以取个中间值 $n \times(n-1)/4$，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要 $n \times(n-1)/4$ 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n)，所以平均情况下的时间复杂度就是 O(n)。

• 空间复杂度

  冒泡排序的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

• 稳定性

  相邻的两个元素大小相等时不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

优化

冒泡排序的优化思路主要是识别出已经有序的部分，避免这些部分被重复遍历比较。

优化一：对于连片有序而整体无序的数据 (例如：1， 2，3 ，4 ，7，6，5)，当已经完成有序时，后面的剩余走访都是多余的，因此加入一个标记（代码中的 is_sorted），如果某次遍历没有发生元素交换，说明说明这组数据已经有序，不用再继续下去，直接跳出循环。

优化二：对于前面大部分是无序而后边小半部分有序的数据 (例如：1，2，5，7，4，3，6，8，9，10)，我们可以继续优化。可以记下最后一次交换的位置（代码中 last_exchange_index），后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

冒泡排序优化代码：

参考：冒泡排序算法优化

特点

• 适用场景：适用元素较少的情况下和数组基本有序的情况；
• 优点：实现简单，空间复杂度低，稳定；
• 缺点：时间复杂度高，效率慢。

3.2.选择排序（Selection Sort）

思路

将待排序数据分为两个区间，已排序区间和未排序区间。选择排序每次会从剩余未排序区间中选择一个最小（大）的元素，将其交换至已排序区间的末尾，直到所有元素排序完毕。

步骤

1. 首先在未排序序列中找到最小（大）元素，交换到排序序列的起始位置；
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后交换到已排序序列的末尾；
3. 重复第二步，直到所有元素均排序完毕。

动图

主要动作：比较和交换

代码

性能

• 时间复杂度

  最好、最坏、平均时间复杂度均为 $O(n^2)$，因为选择排序的时间复杂度与数据原本有序度没有关系，它需要的遍历次数是固定的，不会受到数据原本的有序度的影响。

  虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 $N-1$次交换。而冒泡排序最坏的情况下要发生 $\frac{N^2}{2}$ 次交换操作。从这个意义上讲，选择排序的性能略优于冒泡排序。而且，选择排序比冒泡排序的思想更加直观。

• 空间复杂度

  选择排序只涉及最小（大）元素和已排序的末尾元素的交换，只需要常量级的临时空间，不需要额外空间来进行排序，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

• 稳定性

  选择排序是不稳定排序算法，因为每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，等值的元素随时可能会被置换到后面，发生相对位置改变，这样破坏了稳定性。

优化

选择排序优化思路之一是 “双路优化”，每次遍历剩余元素的时候，一次确定两个元素的位置，找出其中最小值和最大值，比如升序排序，每次将最小值放在起始位置，最大值放在末尾位置。这样遍历的次数会减少一半。时间复杂度是 $O(\frac{N}{2} \times \frac{N}{2})$，虽然还是平方级别的，但是运行时间有了相应的减少。

选择排序优化代码：

参考：选择排序-优化

特点

• 适用场景：适用元素较少的情况下和数组基本有序的情况；
• 优点：交换次数少，移动次数确定 n 次；
• 缺点：效率慢，不稳定。

3.3.插入排序（Insertion Sort）

思路

将待排序数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组中的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

步骤

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

动图

主要动作：比较和移动

代码

性能

• 时间复杂度

  • （最好）如果要排序的数据已经是有序的，并不需要搬移任何数据。只是从头到尾遍历了一遍有序数据进行比较，所以这种情况下，最好是时间复杂度为 $O(n)$。
  • （最坏）如果数组是完全倒序的，每次插入都相当于在数组的第一个位置插入新的数据，需要移动大 量的数据，所以最坏情况时间复杂度为 $O(n^2)$。
  • （平均）数组中插入一个数据的平均时间复杂度是 $O(n)$。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 $O(n^2)$。

• 空间复杂度

  插入排序算法的运行并不需要额外空间来进行排序，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

• 稳定性

  等值元素可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

优化

上面提到的插入排序算法其实是直接插入排序（straight insertion sort），它还有很多优化算法，如：

• 折半插入排序（binary insertion sort）

  思路：直接插入排序在插入到已排序的数据时采用的是顺序查找的方式，因为已排序区域已经是有序数据，所以可以考虑使用折半查找（二分查找）的方法来进行插入，所以称为折半插入排序。

  优缺点：折半插入排序算法相比较于直接插入排序算法，只是减少了比较次数，而移动次数没有进行优化，所以该算法的时间复杂度仍是 $O(n^2)$。

• 二路插入排序（two-way insertion sort）

  思路：

  直接插入排序是一个原地排序算法，因为基础数据结构是数组，内存空间固定，将后面的元素插入到前面必然需要先将其他元素往后移动，以此来保持相对有序。当前位置与正确顺序位置的距离越远，那么需要移动次数就越多。二路插入排序算法是对折半插入排序的进一步改进，主要目的是减少其在排序过程中移动元素的次数从而提高效率。

  为了减少移动次数，二路插入排序借助了一个辅助数组 A，其大小与原数组一样，这个数组需要设置成环状数组（代码中通常是在基本数组结构中对数组索引进行一个巧妙取余运算来实现的，所以仅仅是一个逻辑环状数组），这样便可以进行双端插入，这也是二路插入排序名称的由来。大致过程是将（原数组）无序表中第一个记录添加进 A[0] 的位置上，然后从无序表中第二个记录开始，同 A[0] 作比较：如果该值比 A[0] 大，则添加到其右侧；反之添加到其左侧。当所有元素分配好后，其实数组已经变成两个有序区，整体也是一个有序序列。

  详细步骤说明：

  1. 设定一个辅助数组 A，大小是原来数组相同的大小，将原数组第一个元素赋值给 A[0]，作为标志元素；
  2. 通过设置 first 和 final 指向整个有序序列的最小值和最大值，即为序列的尾部和头部，并且将其设置位一个循环数组，这样就可以进行双端插入；
  3. 按顺序依次插入剩下的原数组的元素；
  4. 将待插入元素与 A[0] 比较，偌大于 A[0]，则插入 A[0] 前面的有序序列，否则插入后面的有序序列，具体定位可用折半查找。
  5. 查找到插入位置后进行记录的移动，分别往 first 方向前移和往 final 方向移动
  6. 插入记录将排序好的 A 数组的数据从 first 到 final，按次序赋值回原数组。

  二路插入排序 Python 代码（含折半插入排序代码）：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

  def two_insertionSort(arr):     n = len(arr)     A = [0] * n     A[0] = arr[0]     first, final = 0, 0     for i in range(1, n):         cur = arr[i]         if cur >= A[final]:  # 待插入元素比最大的元素大，插入右边             final += 1             A[final] = cur         elif cur <= A[first]: # 待插入元素比最小的元素小，插入左边             first = (first - 1 + n) % n  # 取余运算，模拟环状数组，已实现前端插入             A[first] = cur         else: # 插入元素比最小大，比最大小，这里使用折半插入（二分查找）法插入             if cur < A[0]:                 low, high = first, n - 1             else:                 low, high = 0, final             while low <= high:                 m = low + (high - low) // 2                 if cur < A[m]:                     high = m - 1                 else:                     low = m + 1             # 用二分查找查到的要插入的位置是high+1，需要先移动原来的有序元素，腾出位置来。             j = final             while j != high:                   # 考虑环形数组，全部用取余的方式实现分别往first方向前移和往final方向移动。                 A[(j + 1) % n] = A[j]                 j = (j - 1 + n) % n             # 插入新元素             A[(high + 1) % n] = cur             final += 1     # 将排序好的A数组的数据从first到final，按次序赋值回原数组。     j = first     for i in range(n):         arr[i] = A[j]         j = (j + 1) % n     return arr

  优缺点：

  二路插入排序在折半插入排序减少比较次数的基础上，进一步减少了移动次数，其平均移动次数约为 $\frac{1}{8}n^2$，但也只是减少了移动次数，并没有从根本上避免，所以其时间复杂度仍为 $O(n^2)$。而且二路插入排序为了减少移动次数借助了外部空间，其空间复杂度变为 O(n)，不再是原地排序算法。

• 表插入排序（list insertion sort）

  思路：

  前面所介绍到的三种插入排序算法，其基本数据结构都采用数组的形式进行存储，因而无法避免排序过程中产生的数据移动的问题。如果想要从根本上解决只能改变数据的存储结构，比如可以使用链表存储。

  表插入排序，即使用链表的存储结构对数据进行插入排序。在对记录按照其关键字进行排序的过程中，不需要移动元素的存储位置，只需要更改结点间指针的指向。

  优缺点：

  与直接插入排序相比只是避免了插入时元素的移动，而插入过程中比较次数并没有改变，所以表插入排序算法的时间复杂度仍是 $O(n^2)$。

• 希尔排序（Shell’s Sort）希尔排序是直接插入排序的一种更高效的改进版本，它从根本上降低了时间复杂度，也被列入常见的十大排序算法之一，具体内容可参考下一小节。

参考：插入排序算法原理及实现和优化

特点

• 适用场景：数据少并且数组大部分有序时；
• 优点：稳定，相对于冒泡和选择更快；
• 缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

3.4.希尔排序（Shell’s Sort）

希尔排序是直接插入排序算法的一种更高效的改进版本，又称 “缩小增量排序”（Diminishing Increment Sort）。

思路

希尔排序对直接插入排序的两个改进点是：越有序直接插入排序效率越高，直接插入排序每次只能移动一位。

希尔排序利用分组粗调的方式使得整个序列先变得 “基本有序”，这样再用插入排序可以极大地减少工作量。希尔排序的整个排序过程按照不同步长（增量）对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。具体做法是先设定一个缩小增量的规则，以某个增量选取数组中元素进行分组，对每个分组进行直接插入排序，然后缩小增量再次分组排序，依次类推，直到增量缩小到 1，程序结束。

增量也被称为间隔（gap）或步长，用途就是按照一个增量跨越选取进行多次分组，增量的选择可以有很多种，比较常用的是逐步折半的增量方法，如 8 个元素所使用的分组跨度为（4，2，1），这个逐步折半法是 Donald Shell 在发明希尔排序时提出的一种朴素方法，被称为希尔增量。

希尔排序的核心在于增量序列的设定。代码中既可以提前设定好增量序列，也可以动态的定义增量序列。动态定义增量序列的算法是《算法（第 4 版）》的合著者 Robert Sedgewick 提出的。

步骤

1. 选择一个增量序列 $t_1$，$t_2$，……，$t_k$，其中 $t_i > t_j$， $t_k = 1$；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 $t_i$，将待排序列分成若干长度为 m 的组，分别对各组元素进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图

主要动作：分组、比较、移动

代码

使用希尔增量序列，最坏复杂度 $O(n^2)$：

性能

• 时间复杂度

  希尔排序在直接插入排序的基础上，增加了一个新的特性，从根本上提高了效率。希尔排序的排序效率取决于分组使用的增量序列，除了大小关系，还有序列间的数学性质，比如它们的公因子等。但关键词比较次数、记录移动次数和增量序列选择之间的关系，至今没有一个统一的公式可以归纳，是数学上的一个难题，所以分析起来情况比较复杂，所以这里我们只简单总结一下，不再进行详细分析。

  • （最好）因为希尔排序的性能和增量序列的设计有关，对于大部分增量序列的设定方法，最好的情况可以达到 $O(n\log n)$；对于比较差的增量序列设定方法，最好的时间复杂度是 $O(n\log^2n)$。

    目前已知最好增量序列是由 Sedgewick 提出的 $(1, 5, 19, 41, 109, 209,505,929,2161…)$，该序列的项来自 $9 \times 4^i – 9 \times 2^i+1$以及 $2^{i+2} \times (2^{i+2}-3) + 1$这两个算式。

    关于希尔排序最好情况的时间复杂度，其实有些争议，我目前看到有三种不同的说法：$O(n)$、$O(n \log n)$、$O(n \log^2 n)$。

    经过上面的分析，$O(n \log^2 n)$应该是不太可能的，因此争议主要集中在 $O(n)$和 $O(n \log n)$这两种，对于大部分增量序列设定，在待排序列已经完全有序情况下，最内层的循环实际上基本不会发生，因此每个间隔（或增量）的比较总数等于数组的大小。以希尔增量序列为例，其时间复杂度为：

    $$\begin{align}&O((n – n/2) + (n – n/4) + (n – n/8) + \cdots + (n – 1))\\=&O(n\log n – n)\\=&O(n\log n) \end{align} $$

    参考：Shell sort running time on pre-sorted list (best case)

    可能确实有某些希尔排序的变体可以实现最好情况的时间复杂度是 O(n)，不过对于大部分增量序列的设定方法，最好情况的时间复杂度是 $O(n \log n)$，在英文维基百科中，也是这样标注的，所以本文将 $O(n \log n)$作为希尔排序的最好情况时间复杂度。

  • （最坏）对于目前已知最好的增量序列设定方法在最坏情况下，复杂度是 $O(n\log^2n)$；对于比较差的的增量序列设定方法（比如常用希尔增量序列），最坏的时间复杂度是 $O(n^2)$。

  • （平均）希尔排序的平均时间复杂度与增量序列有关，很多资料讲希尔排序平均时间复杂度是 $O(n \log n)$，但实际上不一定能达到，因为希尔算法在最坏的情况下和平均情况下执行效率相差不是很多（百度百科），个人觉得可以概括性的认为大部分的较好的增量序列方法平均时间复杂度是 $O(n\log^2n)$，是介于 $O(n \log n)$和 $O(n^2)$之间的复杂度（也有些地方提到复杂度大概是 $O(n^{(1.3)})$~$O(n^2)$）。

    这样我们很容易作对比，希尔排序没有快速排序算法快（$O(n \log n)$），因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择，但是比直接插入排序等 $O(n^2)$复杂度的算法快得多。一个应用经验是，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。

  注：$O(\log^2 n)= O(\log n)^2 = O(\log n \times \log n)$

  因此，复杂度 $O(\log^2 n) > O(\log n)$。

• 空间复杂度

  希尔排序只需要在原数组内部完成逻辑分组和交换，并不需要额外空间来进行排序，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

• 稳定性

  一次插入排序是稳定的，不会改变相同元素的相对顺序，但希尔排序进行了多次分组插入排序，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

希尔排序的优势是实现简单，空间复杂度和时间复杂度都不是很高，劣势是希尔排序是非稳定排序算法，另外希尔排序的时间复杂度分析比较困难。

优化

希尔排序的复杂度和增量序列直接相关，可以使用更加复杂的增量序列达到优化目的。 比如使用 Knuth 增量序列，最坏复杂度 $O(n^\frac{3}{2})$：

特点

• 适用场景：可以用于大型数组，比插入排序和选择排序快；
• 优点：原地排序，空间复杂度 O(1)。改进的插入排序，相对高效的基于交换元素的排序算法；
• 缺点：不稳定，时间复杂度依赖于增量序列函数。

3.5.归并排序（Merge Sort）

思路

归并排序的核心思想就是把要排序的序列从中间分成前后两部分，然后对前后两部分分别排序，这个分裂过程可以进行多次，直到最小单元非常容易完成排序，最后再将排好序的两部分依次合并在一起，这样整个序列就都有序了。通常我们提到的归并排序大部分情况是将两个有序序列合并成一个有序序列，称为二路归并（2 路归并），当然也有多路的归并排序。

归并排序使用的是分治思想（Divide and Conquer），也称分治法，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

分治思想通常用递归来实现，分治是一种解决问题的算法思想，递归是一种编程技巧，二者并不冲突。因为递归都可以用迭代重写（只是有些实现起来逻辑非常复杂），所以归并也可以用迭代来实现，不同的是，递归是自上而下的，而迭代是自下而上的。

步骤

分裂部分

1. 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列；

合并部分

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动图

主要动作：分解、对比、合并

参考动图 1

参考动图 2（理解分裂合并过程）

代码

归并排序的递归法 Python 实现（自上而下）

归并排序的迭代法 Python 实现（非递归，自下而上）

非递归的方法，可以避免递归时使用的深度为 $\log_2N$的栈空间，额外空间只是用到归并临时申请的跟原来数组一样大小的空间，并且在时间性能上也有一定的提升，因此对于归并排序，迭代法比递归法效率更高，不过实现思路稍比递归法复杂。

性能

• 时间复杂度

  归并排序涉及递归，时间复杂度的分析稍微有点复杂，递归代码的时间复杂度也可以写成递推公式来分析。

  递归的整个过程可以简单概括为一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合并成 a 的结果。

  可以定义求解决问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，所以可以得到这样的递推关系式：

  $$T(a) = T(b) + T(c) + K$$

  其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。

  对应的，可以写出归并排序的时间复杂度计算公式：

  $$T(n)=\begin{cases}T(1) = C, & n=1 \\ 2 \cdot T(n/2) +n , & n \gt 1 \\\end{cases}$$

  其中，C 表示常量级的执行时间，归并排序中合并两个有序子序列时间复杂度是 $O(n)$，因此递推公式中的 K 等于 n。

  进一步分解计算过程，可得：

  $$\begin{align} T(n)&=2 \cdot T(n/2) +n \\&=2 \cdot (2 \cdot T(n/4) + n/2) + n = 4\cdot T(n/4) + 2\cdot n \\&= 4\cdot(2\cdot T(n/8) + n/4) + 2\cdot n = 8\cdot T(n/8) + 3\cdot n \\&=8\cdot (2\cdot T(n/16) + n/8) + 3\cdot n = 16\cdot T(n/16) + 4\cdot n \\&……\\&=2^k \cdot T(n/2^k) + k \cdot n \\&…… \end{align}$$

  通过这样一步一步分解推导，我们可以得到 $T(n) = 2^kT(n/2^k)+kn$。当 $T(n/2^k)=T(1)$时，也就是 $n/2^k=1$，我们得到 $k=\log_2 n$ 。我们将 k 值代入上面的公式，得到 $T(n)=Cn+n\log_2 n$ 。用大 O 标记法来表示，$T(n)$ 就等于 $O(n\log n)$。所以归并排序的时间复杂度是 $O(n\log n)$。

  从原理分析可以看出，归并排序的执行效率与要排序的原始序列的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 $O(n \log n)$。

• 空间复杂度

  归并排序不是原地排序算法，因为归并排序的每次合并都要借助一个额外空间来完成，其大小是两个待合并子序列的大小之和。不过递归代码的空间复杂度并不像时间复杂度那样累加，虽然每次合并都需要申请额外的内存空间，但在合并完成后，临时开辟的内存空间就会被释放掉。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 $O(n)$，而不是 $O(n\log n)$。

  虽然归并排序的时间复杂度任何情况下都是 $O(n\log n)$，看起来非常优秀（快排最坏情况也是 $O(n^2)$），但它不是原地排序算法，因此归并排序并没有像快排那样得到广泛应用。

• 稳定性

  归并排序的稳定性主要体现在合并的过程中，如果两个子序列之间有值相同的元素，可以先把前面序列中的元素放入临时空间，这样就保证了等值元素在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

优化

归并排序常用的三种优化方法：

1. 用迭代法替代递归法

   迭代法可以避免递归调用，虽然不能降低时间和空间复杂度，但可以减少时间和空间消耗，代码详见归并排序迭代法实现。

2. 对小规模子数组使用插入排序

   和快速排序一样，可以加一个规则判断，对于小数组可以使用插入排序或者选择排序，也是为了避免递归调用，虽然不能降低复杂度，但可以减少耗时。

3. 判断数组是否有序

   根据归并排序的特点，每次归并的两个小数组都是有序的，a[mid]是第一个子数组的最大值，a[mid+1]是第二个子数组的最小值，当 a[mid]<=a[mid+1]时表明已经整体有序，我们可以跳过 merge 方法，这样并不影响排序的递归调用。

归并排序优化算法 Python 实现

参考：算法（Algorithms）第 4 版 练习

特点

• 适用场景：待排序数组规模较大时更好；
• 优点：稳定，效率高；
• 缺点：占用内存，需要 $O(n)$的辅助空间。

3.6.快速排序（Quick Sort）

思路

快速排序非常有名，通常被简称为 “快排”，它也是利用了分治思想，不过与归并排序的思路完全不一样，本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤

1. 从待排序数组中选择一个元素，作为 “分区点”（pivot）;

2. 重新排序数组，所有比分区点小的元素放在分区点前面，比分区点大的元素放在分区点的后面（相同的数可以到任一边），在这个分区退出之后，该分区点就处于序列的中间位置，这个过程称为分区（partition）操作；

   为了不使用额外的空间进行排序，分区操作通过一种巧妙的处理方法来实现原地分区。具体过程如下图所示：

   

   这里有点类似选择排序。通过游标 i 把 A[l…r-1] 分成两部分。A[l…i-1] 的元素都是小于 pivot 的，我们暂且叫它 “已处理区间”，A[i…r-1] 是 “未处理区间”。我们每次都从未处理的区间 A[i…r-1] 中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i] 的位置，可结合之后的代码理解。另外还用到的一个处理技巧是通过交换的方式在 O(1) 时间复杂度内完成插入操作，从而避免数据搬移，属常规操作。

3. 递归地（recursive）对两个分区后的子序列进行排序；

4. 直到区间缩小为 1，就说明所有的元素都有序了，退出迭代。

动图

主要动作：选分区点，对比，交换

参考动图一：分区点选择最左边的元素

参考动图二：分区点选最右边的元素，理解

代码

代码一：选取最后一个元素作为分区点

代码二：（极简版本）选取第一个元素作为分区点

性能

• 时间复杂度

  快速排序也是用递归方法实现的，其时间复杂度分析方法同归并排序一样也可以用递归公式来分析。

  • （最好）如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，分区极其均衡的情况下，快排的时间复杂度是 $O(n \log n)$。

  • （最坏）比较极端的例子，如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，对于已经排好序或者接近排好序的情况，快排的时间复杂度就从 $O(n\log n)$ 退化成了 $O(n^{2})$。

  • （平均）通过递推公式求解快排的平均时间复杂度比较复杂，这里使用递归树来分析。假设每次分区操作都将区间分成大小为 9:1 的两个小区间，也就是说，每次分区都很不平均，一个分区是另一个分区的 9 倍。 把递归分解的过程画成递归树见下图：

    

    快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 $n$ 。我们现在只要求出递归树的高度 $h$，这个快排过程遍历的数据个数就是，也就是说 $n \times h$，时间复杂度就是 $O(n \times h)$。

    因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树，我们可以分开来看，快速排序结束的条件就是待排序的小区间大小为 1，也就是说叶子节点里的数据规模是 1 。从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 $\frac{1}{10}$，最长的一个路径每次都乘以 $\frac{9}{10}$ 。通过计算，我们可以得到，从根节点到叶子节点的最短路径是 $\log_{10} n$，最长路径是 $\log_{\frac{10}{9}}n$。

    所以，遍历数据的个数总和就介于 $\log_{10} n$和 $\log_{\frac{10}{9}}n$ 之间。根据复杂度的大 O 表示法，对数复杂度的底数不管是多少，我们统一写成 $\log n$，也就是说不管分区大小比例是多少，快速排序的时间复杂度都是 $O(n \log n)$。

  快速排序优势分析：

  1）从上面的分析可以看出，即便是分区大小比例偏差很大，快速排序的时间复杂度依然是 $O(n \log n)$，这意味着快速排序发生最坏的情况的可能性非常小。

  2）快速排序 $O(n \log n)$ 记号中隐含的常数因子很小，比复杂度稳定等于 $O(n \log n)$ 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

  3）快速排序的内部循环（inner loop）可以在大部分的架构上很高效地被实现出来，所以快速排序被认为是处理大数据最快的排序算法之一。

• 空间复杂度

  快速排序通过设计巧妙的原地分区函数，不需要额外空间来进行排序，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

• 稳定性

  因为快速排序的分区过程涉及交换操作，如果数组中有两个相同的元素，经过分区操作之后，两个等值元素的相对先后顺序可能会改变，所以快速排序并不是一个稳定的排序算法。

对比

归并排序和快速排序的区别：

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 $O(n\log n)$ 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

优化

快速排序有很多优化思路，下面简单讨论：

优化一：更合理 pivot 选择方式

只是简单地选择第一个或最后一个元素做 pivot 实际上并不合理，因为很容易出现最坏情况，毕竟对一个预先有一定顺序的数组做排序的需求还是很普遍的，因此需要用更合理的方式来选择 pivot。

除了固定位置选择 pivot，还有两种常用的更优的 pivot 选择方法。

随机选取：这是一种相对安全的策略。因为分区点的位置是随机的，那么产生的分区也不会总是会出现劣质的分区，实际上，随机化快速排序理论上遇到最坏情况的可能性仅为 $\frac{1}{2^n}$。所以随机选取 pivot 在大部分情况下可以达到 $O(n\log n)$的期望时间复杂度。

三数取中（midian of three）：分区的最佳的划分是将待排序的序列分成等长的子序列，如果我们能够找到待排序序列的中位数，那就容易得到合理的分区了。不过，中位数的计算相对复杂，按照定义相当于需要事先进行一半的排序来确定中位数值。也有人尝试过随机选取三个元素并用三数的中位数作为分区点，但因为随机性的存在性能没有明显提升。更为常用的做法是三数取中，即从第一项、最后一项、中间一项三个数中取中位数作为 pivot，这种方法可以减少快排大约 14% 的比较次数。当然这并不能完全避免最坏情况的发生，所以内置排序算法会采取更小心、更严谨的 pivot 选择方案（对于大数组特别重要）。比如先把大数组平均切分成左中右三个部分，每个部分用三数取中得到一个中位数，再从得到的三个中位数中找出中位数。

优化二：优化小数组排序效率

这一点与归并排序类似，规模很小的情况，快速排序的优势并不明显（可能没有优势），而递归型的算法还会带来额外的递归调用开销。于是对于这类情况可以选择非递归型的算法来替代。经验表明，在大多数情况下这个阈值设定到 5~15 之间能够取得比较好的性能，替换的算法一般是选择排序或插入排序。

优化三：双向扫描分区

通常我们是从左向右依次与 pivot 比较然后进行交换，效率偏低，比如一个数组 [2, 1, 3, 1, 3, 1, 3]，选第一个元素作为 pivot，如果按原来的方式，每次发现比 2 小的数会引起一次交换，一共三次。然而，直观来说，其实只要将第一个 3 和最后一个 1 交换就可以达到这三次交换的效果。所以更理想的分区方式是从两边向中间遍历的双向分区方式，这种方法叫双向扫描分区。

优化四：三向切分法

假如一个数组里的元素全部一样大（或者存在大量相同元素），也会令快速排序容易进入最坏情况，时间复杂度退化到 $O(n^{2})$。因为不管怎么选 pivot，都会使分区结果一边很大一边很小。解决思路还是修改分区过程，思路跟上面说的双向分区类似，但是会更复杂，我们需要小于 pivot、等于 pivot、大于 pivot 三个分区，这种方法在算法中被称为三向切分法（或三向分区法）。

三向切分快排被称为熵最优快排，所谓的 “熵最优” 是指：对于任意分布的输入，最优的基于比较的排序算法平均所需的比较次数与三向切分快排平均所需的比较次数相比，处于常数因子范围之内。当然前提是需要将数组进行随机化。三向切分快排的运行时间和输入的信息量的 N 倍成正比。对于含有大量重复元素的数组，它将快排的排序时间从线性对数级降低到线性级别。

常用的三向切分方法有：Dijkstra 三向切分及其改进版快速三向切分（J.Bently, D.McIlroy)

优化五：递归内省

理想的快速排序算法递归尝试深度会到 $\log N$ 之内，但如果递归深度达到 $2\log N$，比理想情况递归深了一倍还没有结束，那就很可能已经进入最差情况了，继续使用快速排序性能可能会很糟。所以可以用递归内省的方法进行优化，就是监控递归过程，当递归深度达到一定的阈值后（如上面提到的 $2\log N$），就可以考虑对这个分区采用其他排序算法来处理，通常会使用堆排序，因为它的平均和最差时间复杂度都是 $O(N \log N)$，这就是内省排序的思想。

优化六：尾递归

内省排序虽然会避免递归过深，但它的目的并不是为了优化递归。

在分区过程中，我们其实是把一个大的问题分解成两个小一点的问题分别处理。我们还可以进一步考虑，这两个小问题哪个更小。先处理更小规模的问题，再处理更大规模的问题，这样可以减小递归深度，节约栈开销。所以这里可以考虑用尾递归优化，即小规模的问题先递归，减少递归深度，大规模的问题直接通过尾递归优化掉，不进入递归栈。

不过并不是所有的语言都支持尾递归，比如 python 和 javascript 不支持尾递归优化，而且 Python 的递归受到栈长度限制，当递归深度超过 1000 时，会抛出异常。

关于尾递归一些参考资料：

• 什么是尾递归？
• 为什么 Python 不支持尾递归优化
• 一种巧妙的方法实现 Python 尾递归优化

优化七：并行

快速排序是典型的分治算法，分治算法的一大好处是很容易融入到各类并行框架中，快排也是如此，可以通过并行方法来实现整体排序优化，比如多进程多线程等。

参考：快速排序算法的优化思路总结

优化代码实现

下面将综合实现前四种优化，因为优化三和优化四属于并列关系，而且优化四基本包含优化三的理念，所以这里先介绍优化三的代码实现，然后综合介绍优化四以及优化一和优化二的实现。

1）双向扫描分区（对应优化三）

未优化的快排可以看做单向扫描分区，双向扫描分区与单向扫描分区类似，但左指针（i）一直往右移，直到大于中间值时停止；右指针（j）一直往左移，直到小于中间值时停止。然后左指针的值与右指针的值交换。之后左指针继续一直左移，右指针一直右移。重复执行。

2）Dijkstra 三向切分方法（优化四）+ 三数取中（优化一）+ 小规模优化（优化二）

从左到右遍历数组一次，过程如下：

• 维护指针 lt 使得 arr[left…lt-1] 中的元素均小于 pivot；
• 维护一个指针 gt 使得 arr[gt+1…right] 中的元素均大于 pivot；
• 一个指针 i 使得 arr[lt…i-1] 中的元素均等于 pivot；
• 余下 arr[i…gt] 中的元素还未扫描。

Dijkstra 三向切分快速排序 Python 实现

3）Bentley-McIlroy 快速三向切分方法（优化四）+ 三数取中（优化一）+ 小规模优化（优化二）

Dijkstra 的三分区快速排序虽然在快速排序发现不久后就提出来了，但是对于序列中重复值不多的情况下，它比传统的二分区快速排序需要更多的交换次数。

Bentley 和 D. McIlroy 在普通的三分区快速排序的基础上，对一般的快速排序进行了改进。在划分过程中，i 遇到的与 v 相等的元素交换到最左边，j 遇到的与 v 相等的元素交换到最右边，i 与 j 相遇后再把数组两端与 v 相等的元素交换到中间，通过将重复元素置于子数组两端，从而实现一个信息量最优的排序算法。这个方法不能完全满足只扫描一次的要求，但它有两个好处：首先，如果数据中没有重复的值，那么该方法几乎没有额外的开销；其次，如果有重复值，那么这些重复的值不会参与下一趟排序，减少了无用的划分。

过程如下：

• 维护指针 p 和 q 使得 arr[left…p-1] 和 arr[q+1, right] 中的元素都和 v 相等；
• 维护指针 i 和 j 使得 arr[p…i-1] 中的元素小于 v ，arr[j+1, q] 中的元素大于 v；
• 在切分循环结束后将和 v 相等的元素交换到正确的位置上。

Bentley-McIlroy 三向切分快速排序 Python 实现

参考：快速排序 C++及 Python 实现及优化

特点

• 适用场景：待排序数组规模较大时更好；
• 优点：占内存小，耗时少；
• 缺点：不稳定。

3.7.堆排序（Heap Sort）

思路

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆的数据结构需要满足两个条件：

1. 是完全二叉树的结构

   完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列；

2. 堆的基本性质

   即子结点的键值或索引总是小于等于（或者大于等于）它的父节点。

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

步骤

主要分为建堆和排序两个部分：

1. 建堆，将数组原地建成一个堆（根据升序降序需求选择大顶堆或小顶堆），就是通过比较和交换，使数组的排序满足堆的特性，这个过程叫作堆化（heapify）。

   原地建堆的思路是从最后一个非叶子节点遍历检查，把大的节点换到父节点，然后对交换后的子节点依次堆化，使当前堆满足整体堆的性质。

   整个过程数组从后向前处理，堆化还是从上到下的顺序：

   

   （注，图中为了计算理解方便，数组位置 0 处留空，代码中没有留空，所以索引计算不一样）

2. 排序

   以升序排序为例，建堆结束之后是大顶堆的结构。排序过程就是每次从堆化后的堆顶取出最大值置于数组最后面，知道数组完全有序。

   1）把堆首（最大值）和堆尾互换，那最大元素就放到了下标为 n 的位置（图中 0 位置留空），此时的最大值就作为已排好序的部分；

   2）堆的首尾互换后，需要再通过堆化的方法，将剩下的 n-1 个元素重新构建成堆；

   3）堆化完成之后，再取堆顶的元素，交换到下标是 n-1 的位置，已排序区就有了两个元素，一直重复这个过程，直到最后堆中只剩下一个元素，排序工作就完成了。

   

动图

代码

还可以使用 Python 内置堆模块实现堆排序，不过这种方法需要额外空间，代码如下：

性能

• 时间复杂度

  • 建堆过程的时间复杂度

    每个节点堆化的时间复杂度是 $O(\log n)$，那 $\frac{n}{2} + 1$个节点堆化的总时间复杂度可以大概估计是 是 $O(n \log n)$，更精确地推导，堆排序建堆过程的时间复杂度是 O(n)，推导如下：

    因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程 中，需要比较和交换的节点个数，跟这个节点的高度 $k$成正比。只需要将每个节点的高度求和，得出的就是建堆的时间复杂度。

    下图画出了每一层的节点个数和对应的高度：

    

    将每个非叶子节点的高度求和，就是下面这个公式：

    $$S_1=1 \cdot h+2^{1}\cdot(h-1)+2^{2}\cdot (h-2)+ \cdots + 2^{k}(h-k)+ \cdots + 2^{h-1} \cdot 1$$

    把公式左右都乘以 $2$，就得到另一个公式 $S_2$，将 $S_2$错位对齐，并且用 $S_2$减去 $S_1$，可以得到 $S$：

    $$S_2 = 2^{1}\cdot h + 2^{2} \cdot (h-1) + \cdots+ 2^{k} \cdot (h-k+1)+\cdots + 2^{h-1}\cdot 2+2^{h}\cdot 1$$

    $$S=S_2 – S_1 = -h+\bbox[white,5px,border:2px dotted red]{2+2^2+2^3+\cdots+2^k+\cdots+2^{h-1}}+2^h$$

    可以发现 $S$的中间部分是一个等比数列，所以最后可以用等比数列的求和公式来计算，最终的结果为：

    $$S=-h+(2^h-2)+2^h=2^{h+1}-h-2$$

    因为 $h=\log_2n$，带入公式 $S$，就能得到 $S=O(n)$，所以建堆过程的时间复杂度是 $O(n)$。

  • 排序过程的时间复杂度

    在取出堆顶点放到对应位置并把原堆的最后一个节点填充到堆顶点之后，需要对堆进行重新堆化，每次堆化意味着有一个节点出堆，所以需要将堆的容量减一。堆化 heapify() 函数的时间复杂度 $k=\log(n)$，$k$为堆的层数。所以在每次堆化时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。

    重建堆一共需要 $n-1$次循环进行堆化，每次循环的比较次数为 $\log(i)$，则相加为：

    $$\log2+\log3+…+\log(n-1)+\log(n)≈\log(n!)$$

    可以证明 $\log(n!)$和 $n\log(n)$是同阶函数：

    由：$$ (n/2)^{n/2} \leq n! \leq n^n$$

    因此：$$ n/4\log(n) = n/2\log(n^{1/2}) \leq n/2\log(n/2) \leq \log(n!) \leq n\log(n)$$

    所以排序过程的时间复杂度为 $O(n\log n)$。

  • 整体

    综上，堆排序的时间复杂度是 $O(n\log n)$，另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。所以，堆排序最好情况、最坏情况、平均情况的时间复杂度都是 $O(n\log n)$。

    从上面看出，堆排序比快速排序的时间复杂度还要稳定，但是，在实际的软件开发中，快速排序的性能要比堆排序好，原因有两个：

    第一，堆排序数据访问的方式没有快速排序友好。快速排序可以局部顺序访问，而堆排序堆化过程中数据是跳着访问的，这样对 CPU 缓存是不友好的。

    第二，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。 堆排序的比较次数只有在序列初始状态接近对的情况下才能显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。而对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。 但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有 序度降低。比如，对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。所以，大部分情况下堆排序比快速排序交换次数多。

• 空间复杂度

  堆排序可以完全通过数组内部的元素交换来实现，不需要额外空间，所以它的空间复杂度为 $O(1)$，是一个原地排序算法。

• 稳定性

  堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

特点

• 适用场景：待排序数组规模较大时更好；
• 优点：效率高；
• 缺点：不稳定，不适合较小的序列。

3.8.桶排序（Bucket Sort）

思路

桶排序，顾名思义，会用到 “桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

影响桶排序性能的两个关键因素：分桶映射函数以及桶内的排序算法。

场景

高效的桶排序其分桶映射函数需要尽量做到以下两点：

1. 在额外空间充足的情况下，尽量增大桶的数量；
2. 使用的映射函数能够将输入的 N 个数据尽可能均匀的分配到 K 个桶中。

步骤

1. 人为设置一个 BucketSize，作为每个桶所能放置多少个不同数值；

   例如当 BucketSize = 5 时，该桶可以存放 ｛1, 2, 3, 4, 5｝这几种数字，但是容量不限，即可以存放 100 个 3，实际的桶排序过程多以链表形式插入，这样可以避免动态扩容。

2. 遍历待排序数组元素，然后把数据一个一个放到对应的桶里去；

3. 对每个非空桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；

   注意，如果递归使用桶排序为各个桶排序，则当桶数量为 1 时要手动减小 BucketSize 增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

4. 把多个非桶中已排好序的数据拼接起来。

动图

性能

• 时间复杂度

  想要达到理想的效果，桶排序对数据及其分布的要求是十分苛刻的（对输入的基本假设）：

  1）要求各个桶之间是有序的，这样每个桶排好序之后，才可以直接根据桶的顺序得到最终排序；

  2）每个桶之间数据分布是平均的，如果出现上述极端情况，则时间复杂度就会退化为 O(nlogn) 了。

  • （平均）对于待排序序列大小为 $n$，共分为 $m$ 个桶。主要步骤有：

    $n$ 次循环，将每个元素装入对应的桶中；

    $m$ 次循环，对每个桶中的数据进行排序（平均每个桶有 $k = n/m$ 个元素）。

    一般使用较为快速的排序算法，若每个桶内部使用快速排序，时间复杂度为 $O(k\log k)$，$m$ 个桶排序的时间复杂度就是 $O(m \times k \times \log k)$，因为 $k=n/m$，所以 $m$个桶排序的时间复杂度就是 $O(n \times \log(n/m) )$。

    加上装桶过程，整个桶排序的时间复杂度为：

    $O(n) + O(n \times \log(n/m) )=O(n) + O(n \times (\log n – \log m) )=O(n)+O(c)= O(n \times (\log(n/m)+1))$

  • （最坏）当输入的数据被分配到了同一个桶中，复杂度会完全依赖桶内排序算法，一般较好的排序算法为 $O(n\log n)$，当然最差可以是 $O(n^2)$。

  • （最好）当桶的个数 $m$ 接近数据个数 $n$ 时，$\log(n/m)$ 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 $O(n)$。当 $n = m$ 时，复杂度为 $O(n)$。

• 空间复杂度

  分桶和最后的整理排序需要额外的空间，空间复杂度为 $O(n + m)$，所以桶排序并不是原地排序算法。

  不过桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。可以利用桶排序的思想，将海量数据进行拆分，划分到不同的桶里，每次在内存中对一个桶进行排序。如果分布不均匀，某个桶的大小超过了内存限制，无法一次性读入内存，那就继续对这个桶进行二次分桶，直到所有数据都能读入内存为止。

• 稳定性

  桶排序的稳定性取决于桶内排序使用的算法。因此，桶排序可以是稳定排序算法。

代码

特点

• 使用场景：数据能够均匀分配到 K 个区间
• 优点：稳定，速度快
• 缺点：耗空间

3.9.计数排序（Counting Sort）

思路

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如数据范围长度是 k（等于待排序数组的最大值与最小值的差加上 1），我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

场景

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

步骤

1. 找出待排序的数组中最小和最大元素，构建计数数组 C[min_value, max_value]；
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；

动图

性能

• 时间复杂度

  计数排序涉及基础的扫描遍历操作，待排序元素个数是 n，数据取值范围长度是 k，所以总的时间复杂度是 $O(n+k)$。

• 空间复杂度

  类似桶排序，计数排序的计数过程需要额外的空间，空间复杂度为 $O(k)$，不过对于维持稳定性的实现方法，为了避免污染原始数组数据，则还需要额外的等同于原数组大小的空间用来整理已排序元素，空间复杂度为 $O(n+k)$，所以计数排序并不是原地排序算法。

• 稳定性

  计数排序可以通过一些技巧实现相等元素的相对位置在排序后保持不变，所以计数排序的是一个稳定的排序算法。

代码

基础版代码（存在缺陷，更完善的代码见优化部分）

优化

基础版代码实现存在两个缺陷：

1. 存在空间浪费的问题

   基础代码中创建的计数数组是从 0 开始的，假如有一组数据是 [100, 200]范围内数字的多次重复，按照基础版代码的思路，我们需要创建一个长度为 200 的计数数组，但其实前面的 [0, 99]是完全被浪费掉的，如果数字更大些，浪费情况就更严重了。

2. 不是稳定的排序算法

   性能分析中我们讲到，计数排序是可以实现稳定排序的，但在基础版的代码实现中，数据从前到后遍历分配到计数数组中，计数数组通过值的累加来存储对应位置相同的元素，这个过程类似栈的进栈操作，所以原元素组遍历到后面的元素实际上是处于栈顶的。而整理排序的过程，在遍历各个分桶的时候，从桶顶至桶底遍历，类似于出栈操作，然后依次取值按序放入原数组，这个时候等值元素的相对位置就发生了变化，因此这种方式实现的计数排序不是一个稳定的排序。

下面通过优化代码，来解决上面两个问题。

计数排序优化版代码

特点

• 适用场景：数据范围不太大的情况，数值必须是整数；
• 优点：当数据范围小时，速度非常快；
• 缺点：需要额外内存，只能对整数排序。

3.10.基数排序（Radix sort）

思路

基数排序的基本思想就是按位排序，主要适合那些较长的编码类型的排序，可以分割出独立的 “位” 来比较，比如电话号码。基数排序也是非比较的排序算法，它的实现有两种方式：最高位优先（Most Significant Digit first，MSD）和最低位优先（Least Significant Digit first，LSD）法，不过按照我们的思维习惯，大多数是用 LSD 方法，即对每一个分割的 “位” 进行排序，从最低位开始排序，依次升维排序，直到最高位。

场景

基数排序对要排序的数据是有要求的，需要可以分割出独立的 “位” 来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 $O(n)$ 了。

另外，计数排序也并非只能用于整数，因为整数也可以表达字符串（比如名字或日期）和特定格式的浮点数。

步骤

1. 取得数组中的最大数，并取得位数；
2. arr 为原始数组，从最低位开始取每个位组成 radix 数组；
3. 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

动图

性能

• 时间复杂度

  对于每一位的排序，可以用桶排序或者计数排序（通常用计数排序），因为这两个算法的时间复杂度可以做到 $O(n)$，且数据也满足算法的基本限定。

  如果要排序的数据有 $k$ 位，划分 “位” 的基数为 r，也就意味每一位的取值范围大小为 $r$，等于本次计数排序所需分桶数（计数数组大小），所以整个过程可以理解为进行 $k$次计数排序，计数排序对应的分桶数为 $r$，因此总的时间复杂度是 $O(k(n+r))$，可以合并写为 $O(k \times n)$。当 $k$ 不大的时候，比如手机号码排序的例子，$k$ 最大就是 11，所以基数排序的时间复杂度就近似于 $O(n)$。基数排序中没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，都是 $O(k(n+r))$。

  z 注意，这里 $k$的值其实与基数 $r$的设定息息相关，以 11 位手机号为例，如果基数设为 10，则划分了 11 位，需要 11 次计数排序完成整体排序；如果基数设为 100，划分了 6 位，那么只需要 6 次计数排序，用数学表达二者关系为：

  $$ k=\lceil \log_r {\rm Max} \rceil $$

  其中 Max 表示数组中的最大值，$\lceil\; \rceil$表示向上取整。

• 空间复杂度

  每次计数排序所需计数数组额外空间为 $r$，$k$次计数排序所需空间为 $r \times k$，最后整理排序所需额外空间为 $n$，所以总的空间复杂度为 $O(r k + n)$，可以合并写为 $O(n + k)$。可以看出基数排序并不是一个原地排序算法。

• 稳定性

  基数排序内部使用计数排序或桶排序，都是稳定的排序算法，所以基数排序不改变相同元素之间的相对顺序，因此基数排序是稳定的排序算法。

代码

对比

基数排序、计数排序、桶排序三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

优化

基数排序虽然能够满足线性阶的复杂度，但在实际测试中，对于数值范围加大的数组（如 0 到 100 万），它的性能要比快速排序慢很多。必须要经过一系列优化，才能让基数排序真正地比快排快。

在性能分析中，我们可以看到影响基数排序的性能主要有三个因素：排序数组规模 n、基数 r、数组元素最大值 Max。对于一个固定的要排序的数组来说，n 和 Max 都是固定的，所以我们可以考虑对基数进行优化。

很多代码在使用基数排序的时候总是默认基数为 10，但是这样复杂度往往还是较高，我们可以根据待排序数组元素的数值范围来灵活设定基数大小，以提高性能。

另外一个优化是减少复杂的数学运算，基数排序中有一个频繁的操作是通过一个数学运算获取到当前 “位” 切分出来的数值，这个运算中用到了较为复杂的幂运算，因此如果可以确定使用的基数，在基数固定的前提下，我们可以将基数的幂运算提前计算出来，每次通过查表来快速获得，避免多次重复计算。

通常移位和乘法都比除法运算效率高，因此可以用乘法替代除法运算，在计算基础幂运算的时候直接先算好其导数，下面改为乘法即可，完整的优化代码如下所示：

我们习惯性的以 10 的幂作为基数，这与我们平时多用 10 进制运算相符合。但是，计算机是以二进制存储数据的，所以进一步优化是采用 2 的幂作为基数，这样就可以完全避免复杂的乘除法运算，包括取余操作也可得到优化。修改基数为 1024 之后，除法操作就变为了右移操作，取模操作就变成了与操作。要排序的数据范围很大，但是数据量又不足以使用计数排序时，还可以考虑采用基数为 2048 的基数排序，基数选择为 2048，则三次循环就完全覆盖了整个 int 型整数范围。

完整的优化代码如下所示：

(个人在实际测试中没有上面的优化代码性能好，原因未知)