排序算法总结：稳定与性能分析

前言：

本文对常见排序算法进行了系统总结。为了便于记忆和复习，我将这些算法划分为比较类排序和非比较类排序两大类，重点分析它们的时间复杂度、空间复杂度以及稳定性特征。

一、排序稳定性介绍

排序稳定性 (Sorting Stability) 是排序算法中一个非常重要但常被初学者忽略的概念。

简单来说，如果待排序的序列中存在两个或多个值相等的元素，在排序完成后，这些相等元素之间的相对位置（前后顺序）没有发生改变，那么这个排序算法就是稳定的；反之，如果它们的相对顺序可能发生改变，则该算法是不稳定的。

1.1 核心定义与示例

假设我们有一个数列，其中包含两个值为 5 的元素。为了区分它们，我们标记为 5A 和 5B。

• 原始输入顺序： [ 3, 5A, 2, 5B, 1 ]
  • 注意：这里 5A 在 5B 的前面。
• 排序后的结果： [ 1, 2, 3, 5A, 5B ]
  • 这是稳定排序： 因为 5A 依然排在 5B 的前面，相对位置保持不变。
• 排序后的结果： [ 1, 2, 3, 5B, 5A ]
  • 这是不稳定排序： 因为 5A 和 5B 的位置发生了交换，5B 跑到了 5A 前面。

1.2 为什么稳定性很重要？

你可能会问：“既然 5A 和 5B 的值都是 5，谁在前谁在后有什么区别吗？”

对于简单的整数数组，确实没区别。但在复杂对象排序和多条件排序中，稳定性至关重要。

示例说明： 假设你在处理一个学生成绩单，包含“班级”和“分数”两列。 1.你首先按“分数”从高到低排序。 2.接着，你按“班级”从小到大排序。 第一步：按照分数将两个班级的分数从高到底进行排序： 顺序姓名班级 (第二步的排序依据)分数 (第一步已排好)1小明1 班952小红2 班903小刚1 班854小强2 班60 第二步 ：要求按照班级从小到大进行排序 现在，算法开始根据“班级”进行排序。 对于算法来说，它只看到：

• 小明是 1
• 小刚是 1

在算法眼中，小明和小刚是“相等”的！ (因为 1 等于 1)。 算法根本不知道小明考了95分，它只知道这两个人都属于“1” 情况 A：如果是【稳定排序】 定义： 既然小明和小刚的班级是一样的（相等），算法会严格尊重他们原本的先后顺序。

• 逻辑： “原本小明在小刚前面，所以排完后，小明还得在小刚前面。”
• 结果：
  1. 小明 (1班, 95) <-- 依然在前
  2. 小刚 (1班, 85) <-- 依然在后
  3. 小红 (2班, 90)
  4. 小强 (2班, 60)
• 结论： 1班内部的分数依然是有序的。成功！

情况 B：如果是【不稳定排序】 定义： 既然小明和小刚的班级是一样的（相等），算法觉得谁在前谁在后无所谓，可能会因为交换机制，打乱他们的顺序。

• 逻辑： “这俩都是1班的，随便放吧，也许把后面的调到前面更容易处理。”
• 结果（可能变成）：
  1. 小刚 (1班, 85) <-- 跑到前面去了！
  2. 小明 (1班, 95)
  3. 小红 (2班, 90)
  4. 小强 (2班, 60)
• 结论： 虽然班级排好了（都在1班），但分数顺序乱了（85分排在了95分前面）。第一步做的“按分数排序”的工作，对于1班来说，彻底白费了（前功尽弃）。

二、比较类排序

2.1 直接插入排序

2.1.1 基本思想分析

它的基本思想是：

将数组分为已排序区间和未排序区间，逐步从未排序区间取出元素并插入到已排序区间的正确位置，直到所有元素都排序完成，像打扑克牌理牌一样，将新元素插入到已排好序的序列中。

详细讲解：排序算法指南：插入排序

2.1.2 稳定性分析

核心逻辑分析：

插入排序的工作原理是将当前的元素（记为 tmp）插入到前面已经排好序的序列中。为了找到正确的位置，通常是从后往前扫描已排序的部分.

1. 我们将 tmp 与已排序部分的最后一个元素（记为 a[end]）进行比较。
2. 关键点： 如果 a[end]严格大于 tmp，我们将 a[end] 向后移动一位。
3. 如果 a[end]小于或等于 tmp，我们停止移动，并将 tmp 插入到 a[end] 的后面。

为什么这保证了稳定性？

当遇到两个相等的元素时（例如：已排序部分有一个 5A，当前 tmp 是 5B），算法的判断条件通常是 a[end] > tmp

• 因为 5A 不大于 5B（它们相等），循环会终止。
• 算法会将 5B 插入到 5A 的后面。
• 因此，原本在后面的 5B 依然在 5A 后面，相对顺序没有改变。

2.1.3 时间复杂度分析

最坏情况发生在输入数据是反向排序的情况下（即逆序排列）,例如数组为：[10,9,8,7,6,5,4,3,2,1] 在这种情况下，每个元素都需要与之前所有已排序的元素进行比较，因此每次插入操作的比较次数是逐步增加的。 第一个元素需要与前面0个元素比较，第二个元素需要与1个元素比较，第三个需要与2个元素比较，... ... 第n个元素需要与n-1个元素进行比较 故而需要比较的次数为T（n）= 0 + 1 + 2 + ... ... + n-1 = (n-1) * n /2 因此，总体的时间复杂度是 O(n^2)

2.1.4 空间复杂度分析

直接插入排序是原地进行排序的算法，无序额外辅助空间，故而空间复杂度为：O（N）

2.2 希尔排序

2.2.1 基本思想分析

它的基本思想是：

希尔排序通过引入增量(gap)优化了插入排序，它通过逐步减小间隔（gap），将待排序数组划分成多个小的子序列，每个子序列通过插入排序来进行排序。

由于插入排序本身对已经部分有序的数组较为高效，希尔排序通过逐步缩小间隔，使得整个数组在多轮排序中逐步趋向有序，最终gap减小至1，执行插入排序使得整个数组有序。

详细讲解：排序算法指南：希尔排序

2.2.2 稳定性分析

希尔排序的核心逻辑：

将数组按一定增量（Gap）分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

造成不稳定的根本原因：

在进行分组排序时，相同的元素可能被分到不同的组中。当其中一个元素在它自己的组内进行“长距离跳跃”交换时，它可能会跨过另一个相等的元素，从而改变它们原本的相对顺序。

图解反例证明： 为了证明其不稳定性，我们只需要找到一个反例：假设有一个序列：[3, 2a, 2b, 1] 设定增量 Gap = 2 此时数组被分为两组：

• 组 1 (索引 0, 2): [3, 2b]
• 组 2 (索引 1, 3): [2a, 1]

第一轮排序（针对各组进行插入排序）：

1. 处理组 1 [3, 2b]:
   • 3 > 2b，发生交换。
   • 组 1 变为 [2b, 3]。
   • 此时整个数组变为：[2b, 2a, 3, 1]。
   • 注意！ 此时2b 已经被换到了 2a 的前面，相对顺序已经改变。
2. 处理组 2 [2a, 1]:
   • 2a > 1，发生交换。
   • 组 2 变为 [1, 2a]。
   • 此时整个数组变为：[2b, 1, 3, 2a]。

第二轮排序（Gap = 1，即普通插入排序）： 对 [2b, 1, 3, 2a] 进行插入排序。虽然插入排序本身是稳定的，但“破坏”在上一轮已经发生。 最终排序结果将是：[1, 2b, 2a, 3] 结论：初始序列中 2a在 2b 之前，排序后 2b 跑到了 2a 之前，因此，希尔排序是不稳定的。

2.2.3 时间复杂度分析

希尔排序的时间复杂度是一个复杂的数学问题，目前尚未有定论给出所有情况下的精确公式，但在不同增量序列下有明确的界限。 时间复杂度大约为：O(n^1.3)

2.2.4 空间复杂度分析

希尔排序是原地排序算法，它只需要常数级别的额外空间来存储临时变量 空间复杂度为O(1)

2.3 选择排序

2.3.1 基本思想分析

它的基本思想是：

在每一轮遍历中，从剩余未排序元素中选出最小（或最大）值，并将其放置在已排序序列的末端。

详细讲解：排序算法指南：选择排序

2.3.2 稳定性分析

选择排序的基本思想是：每一轮在未排序区域找到最小（或最大）的元素，然后将其与未排序区域的第一个元素进行交换。

正是这个 “交换” 操作导致了不稳定性，当我们将最小元素与当前位置的元素交换时，当前位置的元素可能会被交换到与其相等的另一个元素的后面。

具体的反例演示： 假设我们要对数组 [5A, 8, 5B, 2, 9] 进行升序排序。为了区分两个 5，我们将第一个记为 5A，第二个记为 5B。 第一轮排序： ①在整个数组中寻找最小值，找到 2（索引为 3）。 ②将 2 与当前未排序部分的第一个元素（即 5A ）进行交换。 交换后的状态： [2, 8 , 5B , 5A , 9] 问题出现： 注意这里，5A被交换到了 5B的后面。在后续的排序过程中（8, 5B, 5A, 9 之间比较），这两个 5 的相对位置保持不变（因为它们相等，不会发生交换）。 最终状态：[2，5B，5A，8，9]

2.3.3 时间复杂度分析

简单推导如下：最坏情况下数组为逆序时 第 1 趟：从 n 个元素里找最小值，要比较 n−1次 第 2 趟：从剩下的 n-1 个元素里找最小值，要比较 n−2次 … 第 n-1 趟：比较 1 次 比较总次数为：(n−1) + (n−2) + ⋯ + 2 + 1 = ( n - 1 ) * n / 2 故而时间复杂度为O(n^2)

2.3.4 空间复杂度分析

选择排序是原地排序，只需要常数个辅助变量（如保存当前最小值下标等），不需要额外开辟与 n 成比例的空间。 因此空间复杂度为：O(1)

2.4 堆排序

2.4.1 基本思想分析

它的基本思想是：

堆排序是一种基于二叉堆 数据结构的比较排序算法。它的核心思想利用了堆这种数据结构“能快速找到最大值（或最小值）”的特性。

详细讲解：排序算法指南：堆排序

2.4.2 稳定性分析

堆排序的不稳定性主要源于其核心操作：交换。

堆排序分为两个阶段：

1. 建堆： 将无序数组构造成一个大顶堆（或小顶堆）。
2. 排序： 不断将堆顶元素（最大值）与堆尾元素进行交换，然后调整堆结构。

根本原因： 在“排序”阶段，我们将堆顶元素（当前最大值）与数组末尾的元素交换时，执行的是一种跨距离的交换。这个操作很有可能把前面的元素“踢”到后面去，从而跨过了一些原本在它后面但值相等的元素，破坏了相对顺序。

具体的反例演示 假设我们需要进行升序排序，使用大顶堆，待排序数组为： [2A, 2B, 1] 第一步：建堆 在这个简单的例子中，[2A, 2B, 1] 实际上已经满足大顶堆的性质

• 根节点：2A
• 左孩子：2B
• 右孩子：1

第二步：排序过程

1. 第一次交换：
   • 将堆顶元素 2A 与堆尾元素 1 交换。
   • 数组变为：[1, 2B, 2A]
   • 此时，最大的 2A 被固定在数组末尾。
   • 注意：此时原本在 2B 前面的 2A，被换到了 2A 的后面。稳定性在这一步已经被破坏了。
2. 调整堆（Heapify）：
   • 剩余未排序部分为 [1, 2B]。
   • 根节点 1 小于左孩子 2B，需要交换。
   • 数组变为：[2B, 1, 2A]。此时堆顶是 2A。
3. 第二次交换：
   • 将堆顶元素 2B 与当前未排序部分的末尾元素 1 交换。
   • 数组变为：[1, 2B, 2A]。
4. 最终结果：
   • 排序结束，数组状态为 [1, 2B, 2A]。

2.4.3 时间复杂度分析

在最好、最坏和平均情况下都保持稳定的性能表现，该算法的时间复杂度始终为O(n log n)。 具体来说，构建堆的过程耗时O(n)，而排序阶段需要遍历n个元素，每次堆调整操作的时间复杂度为O(log n)。

2.4.4 空间复杂度分析

该算法具有O(1)的空间复杂度，作为原地排序算法，它无需额外的存储空间。

2.5 冒泡排序

2.5.1 基本思想分析

其核心原理是：

通过相邻元素的反复比较和交换，使较大元素逐渐"上浮"到序列末端，较小元素自然"下沉"到前端，最终实现整个序列的有序排列 。

详细讲解：排序算法指南：冒泡排序

2.5.2 稳定性分析

冒泡排序是一种稳定的排序算法，因为元素无法“跳跃”式移动，只能一步步挪动，且遇到相等的元素时不发生跨越，所以相对顺序永远不会被改变。

举例说明 假设我们有数组： [2A, 2B, 1] 排序过程中的关键步骤： ①第一轮排序： 2A与2B比较，不进行交换 2B与1比较，由于2 > 1 ，交换 此时数组为：[2A，1，2B] ， 相对顺序没有改变 ②第二轮排序： 2A与1比较，由于2 > 1 ，交换 此时数组为：[1，2A，2B]，相对顺序依旧没有改变 最终数组为：[1,2A,2B]

2.5.3 时间复杂度

在最坏的情况下（例如，输入数组是完全逆序的），此时冒泡排序会进行 n-1 趟排序。 第 1 轮遍历：需要比较和交换 n-1 次 第 2 轮遍历：需要比较和交换 n-2 次 ... 第 n-1 轮遍历：需要比较和交换 1 次 因此，总的比较次数为（等差数列求和）：(n−1) + (n−2) + ⋯ + 2 + 1 = (1 + n - 1 ) * (n - 1) / 2 最坏情况时间复杂度：O(n²)

2.5.4 空间复杂度

冒泡排序是 原地排序 算法，它只在原数组上进行操作，且只使用了常量级的额外空间，所以空间复杂度为O(1)。

2.6 快速排序

2.6.1 基本思想分析

它的基本思想是：

一、选定基准值 选定一个基准值，根据基准值将数组分为两个子数组使得： [ left , keyi - 1 ] keyi [ keyi + 1 , right] ①所有小于基准的元素在基准左侧 ②所有大于基准的元素在基准右侧 ③基准元素在到达其最终排序位置后，将保持固定不再移动 二、递归左子数组和右子数组 递归的思路为： ①左子数组 (不包含基准值) 重复上述操作，选定一个基准值，使得基准元素达到其最终位置 ②右子数组 (不包含基准值) 重复上述操作，选定一个基准值，使得基准元素达到其最终位置 ③递归的边界条件：直到数组不可再进行分为左右子数组，即数组只含有一个元素。

详细讲解：排序算法指南：快速排序

2.6.2 稳定性分析

造成不稳定的根本原因：

快速排序的核心操作是 Partition（分区），在分区的过程中，为了将元素放到基准值（Pivot）的左边或右边，往往需要进行长距离的交换（Swap），正是这种长距离交换，可能会越过数值相同的元素，从而破坏相对顺序。

具体的反例推演 假设我们使用最经典的快速排序实现：选择数组的第一个元素作为基准值（Pivot）。 待排序数组：[ 5A, 3, 5B, 1 ] 第一轮 Partition 过程： ①选取基准： 选定 5A 为 Pivot。 ②指针移动： 右指针（Right）从右向左找比 5 小的数，找到了 1。 左指针（Left）从左向右找比 5 大的数，没有找到，和右指针相遇，最终停留在 1 （或者根据实现不同，直接交换）。 ③交换结果 5A 与 1 交换。 数组变为：[ 1, 3, 5B, 5A ] ④分析结果：在原数组中，5A 在 5B的前面，而在第一轮分区结束后，5A跑到了5B 的后面。 结论：相对顺序被改变，因此是不稳定的。

2.6.3 时间复杂度

由于每趟进行分区需要用双指针遍历整个数组，故而一趟排序需要O(N)的时间复杂度 需要进行递归 log₂n 层 故而时间复杂度近乎为：O(n log n)

2.6.4 空间复杂度

递归调用需要进行开辟栈帧，由于需要进行递归 log₂n 层 故而空间复杂度为：O(log n)

2.7 归并排序

2.7.1 基本思想分析

它的基本思想是：

分（Divide）: 将待排序的数组（或列表）不断地分成两个子数组，直到每个子数组只包含一个元素（单个元素被认为是天然有序的）。 治（Conquer）: 对每个只含一个元素的子数组进行排序（实际上它们已经是有序的） 合（Merge）: 将两个已排序的子数组归并成一个更大的有序数组，重复这个过程，直到所有子数组都归并成一个完整的有序数组。

详细讲解：排序算法指南：归并排序

2.7.2 稳定性分析

归并排序是稳定的排序，因为在合并两个有序子数组时，如果遇到两个相等的元素（一个在左边子数组，一个在右边子数组），标准实现会优先取左边子数组的元素放入结果集。

举例说明 假设我们要排序数组：[2A, 2B, 1]

1. 分解 (Divide):
   • 左边：[2A]
   • 右边：[2B, 1] -> 分解为 [2B] 和 [1]
2. 合并右边 (Conquer):
   • [2B] 和 [1] 合并 -> 结果是 [1, 2B]
3. 最后合并 (Merge):
   • 现在合并左子数组 [2A] 和右子数组 [1, 2B]。
   • 比较 2 A(左) 和 1 (右)：取 1。结果：[1]。
   • 比较 2A(左) 和 2B (右)：
     • 数值相等。
     • 根据 left <= right 逻辑，优先取左边的 2A。
     • 结果：[1, 2A]。
   • 最后剩下 2B，放入结果。
   • 最终结果： [1, 2A, 2B]。

可以看到，2 A依然在 2B 之前，相对位置没有改变，因此是稳定的。

2.7.3 时间复杂度

纵向（树高）：每次对半切分，直到子数组大小为 1，则其复杂度为：log₂n。 横向（每层工作量）：每一层都需要将所有元素进行一次合并操作，需要遍历一遍整个数组，则其复杂度为：O(n)。 故而时间复杂度为O（n * logn）

2.7.4 空间复杂度

1. 辅助数组空间（主导因素）：需开辟临时辅助数组（通常命名为 tmp ），用于暂存合并后的有序元素，避免直接修改原数组导致数据混乱。 必须开辟与原数组大小相等的临时空间，空间复杂度为 O（n），这是归并排序空间开销的核心来源 2. 递归栈空间：归并排序基于分治法，通过递归调用将数组不断拆分为子数组，递归过程中需使用栈存储函数调用栈帧 递归树高度为log₂n ，所以需要O(log n)的空间，远小于辅助数组的 O（n），通常可忽略其对整体空间复杂度的影响。 故而空间复杂度为O(n)

三、非比较类排序

3.1计数排序

3.1.1基本思想分析

它的基本思想是：

计数排序适用于整数数据，且这些整数的范围不宜过大，它的基本步骤如下： ①找出范围：确定输入数组中最大值（max）和最小值（min），从而确定数据的范围 range：max-min+1 ②创建计数数组：创建一个长度为 range 的计数数组 count，用于存储输入数组 a 中每个元素的出现次数。 ③统计次数：遍历输入数组 a，将每个元素的值作为索引，在计数数组 count 对应位置进行计数

详细讲解：排序算法指南：计数排序

3.1.2时间复杂度分析

计数排序主要分 3 步： 1. 找最小值与最大值： 遍历一遍数组 O(n) 2. 建计数数组并统计每个数字出现次数 ：遍历一次数组 O(n) 3.导出排序结果：最坏情况下 O(n + range) 其中备注： 最大值为：max 最小值为：min range：max-min+1

3.1.3空间复杂度分析

开辟一个大小为range的数组，空间复杂度为O（range）

四、八大排序算法图表

既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。