常用排序算法介绍

1. 冒泡排序（Bubble Sort）

• 实现思想：

  重复地遍历要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

• 时间复杂度：

  • 最好情况：O(N)。当输入数组已经是有序的时，只需要进行一趟遍历，比较 N-1 次，没有交换。
  • 最坏情况：O(N^2)。当输入数组是逆序的时，需要进行 N-1 趟遍历，每趟遍历都需要进行多次比较和交换。
  • 平均情况：O(N^2)。

• 复杂度计算说明：

  • 外层循环需要执行 N-1 次（或 N 次）。
  • 内层循环在最坏情况下，第一次执行 N-1 次比较，第二次 N-2 次，...，最后一次 1 次。总比较次数约为 (N-1 + 1) * (N-1) / 2，即 N*(N-1)/2，所以是 O(N^2)。交换次数类似。

• 稳定性：稳定。

2. 选择排序（Selection Sort）

• 实现思想：

  首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 时间复杂度：

  • 最好情况、最坏情况、平均情况都是 O(N^2)。
  • 无论输入数据是什么样的，选择排序的比较次数都是固定的。

• 复杂度计算说明：

  • 外层循环需要执行 N-1 次。
  • 内层循环在第一次需要进行 N-1 次比较，第二次 N-2 次，...，最后一次 1 次。总比较次数是 N*(N-1)/2，所以是 O(N^2)。
  • 交换次数最多是 N-1 次。

• 稳定性：不稳定。（例如，序列 5 8 5 2 9，第一趟会将第一个 5 和 2 交换，导致两个 5 的相对顺序改变）

3. 插入排序（Insertion Sort）

• 实现思想：

  构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它就像我们打扑克牌时，一张一张地将新牌插入到已有序的手牌中。

• 时间复杂度：

  • 最好情况：O(N)。当输入数组已经是有序的时，每次插入都只需要比较 1 次，总共比较 N-1 次。
  • 最坏情况：O(N^2)。当输入数组是逆序的时，第 i 个元素需要与前面 i-1 个元素都进行比较和移动。
  • 平均情况：O(N^2)。

• 复杂度计算说明：

  • 外层循环从第二个元素开始，遍历到最后一个元素，共 N-1 次。
  • 内层循环在最坏情况下，第 i 个元素需要进行 i-1 次比较和移动。总操作次数约为 1 + 2 + ... + (N-1)，即 N*(N-1)/2，所以是 O(N^2)。

• 稳定性：稳定。

4. 归并排序（Merge Sort）

• 实现思想：

  采用分治（Divide and Conquer）策略。 1. 分解（Divide）：将 n 个元素分成各含 n/2 个元素的子序列。 2. 解决（Conquer）：用归并排序递归地排序两个子序列。 3. 合并（Combine）：将两个已排序的子序列合并成一个最终的排序序列。

• 时间复杂度：

  • 最好情况、最坏情况、平均情况都是 O(N log N)。

• 复杂度计算说明：

  • 分解过程：树的深度是 log N。
  • 合并过程：每一层合并时，所有元素都会被遍历一次，所以每一层的合并操作的时间复杂度是 O(N)。
  • 总时间复杂度 = 树的深度 * 每层合并的复杂度 = log N * O(N) = O(N log N)。

• 稳定性：稳定。

• 空间复杂度：O(N)，因为合并过程需要一个临时的辅助数组。

4.1 归并排序的缺点

• 额外空间开销大：

  归并排序最典型的缺点就是不是严格原地排序。标准实现通常需要一个额外的辅助数组来完成合并，所以空间复杂度一般是 O(N)。当数据量很大时，这部分额外内存开销会比较明显。

• 常数项通常比快排大：

  虽然归并排序的时间复杂度稳定在 O(N log N)，但它在每一层都要做完整的合并和数据拷贝，常数项往往比优秀实现的快速排序更大。所以在纯内存排序场景下，归并排序不一定比快排快。

• 递归实现也有函数调用开销：

  经典归并排序通常写成递归，虽然它的递归深度稳定在 O(log N)，不像快排那样容易退化到 O(N)，但仍然存在函数调用和栈帧管理的额外成本。

• 对缓存局部性不一定友好：

  归并过程中需要在多个子数组之间来回读取并写入辅助数组，实际运行时会有较多的数据搬运。在某些 CPU cache 敏感场景下，它的局部性可能不如原地分区类算法。

• 链路长、拷贝多，不适合极端内存紧张场景：

  如果系统内存非常紧，或者排序对象本身很大、拷贝成本很高，那么归并排序的辅助空间和数据搬运会成为明显负担。

4.2 如何优化归并排序

归并排序优化的核心目标，主要有 3 个：

1. 降低额外空间和拷贝成本。
2. 减少递归与小数组处理的常数开销。
3. 利用“局部已有序”这一特性减少不必要的合并。

4.2.1 优化一：小区间切换到插入排序

和快排类似，当子数组很小时，继续递归拆分并不划算，因为：

• 递归调用本身有开销。
• 小数组上的插入排序常数项更小。
• 小数组往往已经接近有序，插入排序效率会更高。

因此很多工程实现会在区间长度小于某个阈值时，直接改用插入排序，而不是继续做归并递归。

这是一种非常经典的混合优化。

4.2.2 优化二：跳过已经有序的合并

归并排序里有一个很实用的剪枝：

• 如果左半部分的最大值 <= 右半部分的最小值
• 说明这两个有序子数组拼接起来本身就已经整体有序

这时就没必要再执行真正的 merge。

也就是说，在递归回溯时可以先判断：

if arr[mid] <= arr[mid + 1]

若条件成立，则直接跳过本次合并。

这个优化在“整体基本有序”的数据上非常有效，能显著减少不必要的数据拷贝。

4.2.3 优化三：复用辅助数组，避免重复申请内存

一个常见低级错误是：每次 merge 时都新建临时数组。

这样会带来：

• 频繁内存分配与回收
• GC 压力上升
• 常数项明显变差

更常见的工程做法是：

• 在排序开始前一次性申请好辅助数组
• 整个归并过程中反复复用这块缓冲区

这个优化不改变复杂度，但对性能和内存抖动都很有帮助。

4.2.4 优化四：自底向上的迭代归并，减少递归开销

除了“递归自顶向下”写法，还可以采用自底向上（bottom-up） 的迭代归并：

• 先把长度为 1 的相邻区间两两归并成长度为 2
• 再把长度为 2 的区间归并成长度为 4
• 然后是 8、16、32，直到覆盖整个数组

这种写法的好处是：

• 不依赖递归调用栈
• 更便于工程上做循环控制
• 在某些语言或运行时里，能减少函数调用开销

它不会改变时间复杂度，但能提升实现的可控性和稳定性。

4.2.5 优化五：外部排序与多路归并，处理超大数据集

如果数据规模大到内存放不下，归并排序反而很有优势，因为它天然适合做外部排序。

典型做法是：

1. 先把大文件切成多个能放入内存的小块。
2. 每块在内存中排序。
3. 把多个有序小文件做多路归并。

这类优化的重点不再只是 CPU，而是：

• 降低磁盘 I/O 次数
• 增加顺序读写比例
• 用多路归并减少归并轮数

所以在“海量数据排序”场景下，归并排序的工程价值通常比快排更高。

4.2.6 优化六：链表排序时优先考虑归并排序

这不算“改造算法”，但算很重要的落地优化思路。

对于链表：

• 快排不容易高效做随机访问和原地分区
• 归并排序只需要改指针，不需要像数组那样频繁搬运元素

所以链表排序的经典最优解通常就是归并排序。

这也是面试里经常会问的点：为什么链表排序更适合归并排序，而不是快速排序。

5. 快速排序（Quick Sort）

• 实现思想：

  同样采用分治策略。 1. 分解（Partition）：挑选一个元素作为“基准”（pivot），将数组分区（partition），使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。 2. 解决（Conquer）：递归地对基准左右两边的子数组进行快速排序。 3. 合并（Combine）：因为子数组是原地排序的，所以不需要合并步骤。

• 时间复杂度：

  • 最好情况：O(N log N)。当每次选取的基准都能将数组恰好平分为两半时。
  • 最坏情况：O(N^2)。当输入数组已经有序或逆序，并且每次都选择第一个或最后一个元素作为基准时，导致每次分区都极不平衡（一边是 0 个元素，另一边是 N-1 个元素），递归树退化成链表。
  • 平均情况：O(N log N)。通过随机选择基准等方法可以大概率避免最坏情况。

• 复杂度计算说明：

  • 最好和平均情况：递归树的深度是 log N。每一层的分区操作都需要遍历该层的所有元素，复杂度是 O(N)。总复杂度是 O(N log N)。
  • 最坏情况：递归树的深度是 N。分区操作的平均复杂度是 O(N)，总复杂度是 O(N^2)。

• 稳定性：不稳定。（在分区交换元素时，可能改变相等元素的相对顺序）

• 空间复杂度：O(log N) ~ O(N)，取决于递归深度。

5.1 快速排序的缺点是什么

• 最坏时间复杂度高：

  快排的平均时间复杂度是 O(N log N)，但它不是严格上界。若每次选出的基准都很差，例如总是选到当前区间的最小值或最大值，分区就会极不均衡，递归树退化成链表，最终变成 O(N^2)。

• 对基准选择敏感：

  快排性能好不好，核心看 pivot 是否能把数据分得足够均匀。对于“已经有序”“逆序”“大量重复元素”等输入，如果基准策略简单粗暴（如永远取首元素），性能波动会很大。

• 不稳定：

  分区过程通常依赖交换。即使两个元素值相等，它们的相对顺序也可能被打乱，所以快排默认不是稳定排序。如果业务要求“按次关键字排完后，再按主关键字稳定排序”，快排就不合适。

• 递归实现有栈深风险：

  快排通常写成递归。平均情况下递归深度是 O(log N)，但在极端不平衡分区下可能达到 O(N)，这会带来额外栈空间消耗，严重时甚至可能栈溢出。

• 重复元素很多时，经典二路划分效果不佳：

  如果数组中大量元素都等于基准，传统的“左边小于、右边大于”二路划分会让很多“等于基准”的元素被反复参与递归，导致划分不够高效，常数项明显变差。

5.2 如何优化快速排序

快排优化的目标，本质上是 3 件事：

1. 让分区尽量均衡，避免退化到 O(N^2)。
2. 减少递归和交换开销，降低常数项。
3. 在特殊输入下保持更稳定的表现。

5.2.1 优化一：改进基准选择，降低最坏情况概率

• 随机选择基准：

  每次从当前区间随机选一个元素作为 pivot，而不是固定取第一个或最后一个。这样可以显著降低“特定输入把快排卡成最坏情况”的概率，是最常见、最实用的优化。

• 三数取中（Median of Three）：

  从区间的左端点、中点、右端点三个元素里取中位数作为基准。它不能彻底消灭最坏情况，但对近乎有序数组通常比“固定取头/尾”稳定得多。

5.2.2 优化二：三路快排，专门处理大量重复元素

经典二路划分一般把数组分成两部分：

• 小于 pivot
• 大于等于 pivot

或：

• 小于等于 pivot
• 大于 pivot

当重复元素很多时，这种划分会让“等于 pivot”的元素继续递归，造成额外开销。三路快排会直接分成三段：

• 小于 pivot
• 等于 pivot
• 大于 pivot

这样“等于 pivot”的那一段不再递归，尤其适合：

• 数据值域小、重复值多。
• 业务数据有明显热点值。

它的核心收益不是改变平均复杂度阶数，而是 显著改善重复元素场景下的实际性能。

5.2.3 优化三：小区间切换到插入排序

当子数组规模很小时，继续递归快排并不划算，因为：

• 递归调用本身有开销。
• 小数组上，插入排序常数项更小。
• 小数组往往已经接近有序，插入排序会很快。

因此很多工程实现会在区间长度小于某个阈值（例如 8、16、32）时，不再继续快排，而改用插入排序。

这是一个非常经典的工程优化。它不改变大 O 复杂度，但通常能明显提升实际运行速度。

5.2.4 优化四：控制递归深度，避免栈过深

常见做法有两类：

• 总是先递归较小区间：

  每次分区后，优先递归较短的一侧，较长的一侧改成循环继续处理。这样可以把递归栈深控制在 O(log N) 量级。

• 改写成非递归版本：

  用显式栈模拟递归过程，避免依赖语言运行时调用栈。

这类优化主要解决的是 空间与健壮性问题，特别是在数据规模大、语言栈深有限时更重要。

5.2.5 优化五：递归过深时切换为堆排序，形成 Introsort

如果想同时兼顾：

• 快排平均情况下的高性能。
• 堆排序最坏情况下的 O(N log N) 上界。

可以采用 Introspective Sort（Introsort） 思想：

• 默认使用快排。
• 一旦递归深度超过阈值（通常与 log N 相关），说明分区质量持续较差。
• 此时切换到堆排序，兜住最坏情况。

它的核心价值是：

• 平均情况下像快排一样快。
• 最坏情况下不会退化到 O(N^2)。

很多标准库排序的核心思想都接近这一类“混合排序”。

6. 堆排序（Heap Sort）

• 实现思想：

  利用堆（Heap）这种数据结构。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 1. 建堆：将无序序列构建成一个大顶堆（或小顶堆）。 2. 排序：将堆顶元素（最大值或最小值）与末尾元素交换，然后将剩余的 N-1 个元素重新调整成一个堆，重复此过程，直到所有元素排序完毕。

• 时间复杂度：

  • 最好情况、最坏情况、平均情况都是 O(N log N)。

• 复杂度计算说明：

  • 建堆过程：时间复杂度是 O(N)。
  • 调整堆过程：需要进行 N-1 次循环，每次循环都需要进行一次堆顶元素下沉的调整，这个调整操作的时间复杂度是 O(log N)（与堆的高度相关）。
  • 总时间复杂度 = O(N) + (N-1) * O(log N) = O(N log N)。

• 稳定性：不稳定。

• 空间复杂度：O(1)，因为是原地排序。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
插入排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
归并排序	O(N log N)	O(N log N)	O(N log N)	O(N)	稳定
快速排序	O(N log N)	O(N log N)	O(N^2)	O(log N)~O(N)	不稳定
堆排序	O(N log N)	O(N log N)	O(N log N)	O(1)	不稳定