Hello 算法排序算法详解：评价维度、核心实现与选型指南

排序算法是数据结构与算法课程中最基础、应用面最广的一类算法。本篇以《Hello 算法》（hello-algo）仓库中的排序章导读文档 sorting_algorithm.md 为主体，完整梳理排序算法的定义、数据类型与判断规则、五大评价维度（运行效率、就地性、稳定性、自适应性、是否基于比较）以及"理想排序算法"的讨论，并结合仓库 codes/ 目录下多语言可运行的参考实现，逐算法剖析这些评价维度在真实代码中是如何体现的，帮助读者建立起"按维度选型"的排序算法知识框架。

一、排序算法概述

**排序算法（sorting algorithm）**用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理——例如二分查找的前提就是数据有序，这也是排序与搜索算法紧密关联的原因。

两点关键认知：

1. 数据类型不限。排序算法中的数据类型可以是整数、浮点数、字符或字符串等，只要是可比较的元素皆可参与排序。
2. 判断规则可定制。排序的比较规则可根据需求设定，如数字大小、字符 ASCII 码顺序或自定义规则（如按学生年龄排序时比较的是 age 字段而非姓名）。

从实现层面看，仓库为排序算法提供了覆盖 14 种语言、每章 9 个算法的统一实现目录，例如 Python 版 codes/python/chapter_sorting/ 中包含 bubble_sort.py、insertion_sort.py、selection_sort.py、merge_sort.py、quick_sort.py、heap_sort.py、bucket_sort.py、counting_sort.py、radix_sort.py 九个文件，与 C++、Java、Go、Rust、Swift 等语言目录一一对应（如 codes/cpp/chapter_sorting/），可直接运行验证。

二、排序算法的五大评价维度

同一类问题存在多种解法，如何评判其优劣？原文档给出了五个评价维度。下面逐一展开，并给出仓库源码中的对应证据。

2.1 运行效率

我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（即时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。

常数项差异在源码中直观可见：同样是最坏 $O(n^2)$ 的冒泡排序与选择排序（bubble_sort.py、selection_sort.py），冒泡排序每轮最多执行 $O(n)$ 次"比较 + 交换"，而选择排序每轮只做 1 次交换（先扫描找最小值索引 k，再执行一次 nums[i], nums[k] = nums[k], nums[i]）。当数据元素较大（如结构体、对象）时，选择排序的数据搬运成本明显更低——这正是"常数项"差异的实际含义。

2.2 就地性

原地排序（in-place sorting）通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。

从源码结构看，评价一个排序是否"原地"，关键看它是否申请了与 $n$ 成比例的辅助存储：

• 冒泡、选择、插入、快速、堆排序都是原地排序。例如插入排序 insertion_sort.py 仅使用 base、j 两个变量，原地移动元素完成插入；
• 归并排序则不是。merge_sort.py 中 merge() 会创建临时数组 tmp = [0] * (right - left + 1) 存放合并结果，因此数组版归并的空间复杂度为 $O(n)$（对链表版归并，该开销可优化至 $O(1)$，见 merge_sort.md）。

2.3 稳定性

稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。稳定排序是多级排序场景的必要条件。

以原文档给出的学生信息表格为例：第 1 列和第 2 列分别是姓名和年龄，输入数据已按姓名排好序。若使用非稳定排序算法按年龄排序，结果中 ('D', 19) 和 ('A', 19) 的相对位置可能改变，输入数据按姓名排序的性质随之丢失：

# 输入数据是按照姓名排序好的
# (name, age)
  ('A', 19)
  ('B', 18)
  ('C', 21)
  ('D', 19)
  ('E', 23)

# 假设使用非稳定排序算法按年龄排序列表，
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变，
# 输入数据按姓名排序的性质丢失
  ('B', 18)
  ('D', 19)
  ('A', 19)
  ('C', 21)
  ('E', 23)

稳定性是否由算法的"交换方式"决定？仓库练习 exercises.md 用数组 $[2_a, 2_b, 1]$ 给出了一个可手工验证的例子：

• 选择排序不稳定：第一轮选出最小元素 1 并与首位 $2_a$ 直接交换，得到 $[1,2_b,2_a]$，相等元素次序被改变。这与 selection_sort.py 中"找到最小索引 k 后无条件 nums[i], nums[k] = nums[k], nums[i]"的实现一致；
• 冒泡排序稳定：相邻元素仅在 nums[j] > nums[j + 1] 时交换，相等元素之间不交换，因此保持原有次序，对应 bubble_sort.py 中严格大于才交换的条件。

2.4 自适应性

自适应排序能够利用输入数据"已有的顺序信息"来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。

仓库中自适应性的最典型证据是冒泡排序的"标志位优化"。bubble_sort.py 提供了两个版本：

def bubble_sort_with_flag(nums: list[int]):
    """冒泡排序（标志优化）"""
    n = len(nums)
    for i in range(n - 1, 0, -1):
        flag = False  # 初始化标志位
        for j in range(i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 记录交换元素
        if not flag:
            break  # 此轮"冒泡"未交换任何元素，直接跳出

基本版冒泡排序无论输入是否有序都要跑满 $n-1$ 轮；而标志位版本一旦检测到某轮"零交换"即判定数组已有序并提前返回，把最佳时间复杂度从 $O(n^2)$ 优化到 $O(n)$——这正是"利用输入已有顺序信息"的自适应行为。类似地，插入排序在输入基本有序时内层 while 几乎不执行，也是自适应的；而选择排序无论输入如何都固定执行 $O(n^2)$ 次比较，完全不具自适应性。

2.5 是否基于比较

• 基于比较的排序依赖比较运算符（$<$、$=$、$>$）来判断元素的相对顺序，从而排序整个数组。可以证明，其最坏时间复杂度的下界为 $\Omega(n \log n)$。
• 非比较排序不使用比较运算符，时间复杂度可达 $O(n)$，但其通用性相对较差（通常要求数据能转换为整数等特定形式）。

仓库中的划分也印证了这一分类：bubble_sort.py、insertion_sort.py、selection_sort.py、merge_sort.py、quick_sort.py、heap_sort.py 的核心循环都建立在各语言的大小比较之上；而 bucket_sort.py、counting_sort.py、radix_sort.py 则利用"元素值 → 数组下标"的映射绕开比较。以 counting_sort.py 为例，其"完整实现"利用前缀和把"出现次数"转换为"尾索引"，再倒序遍历原数组将元素直接放入结果数组 res[counter[num] - 1]，全程没有任何元素间的大小比较，且倒序填充保证了稳定性。

三、理想排序算法

理想排序算法应当满足：运行快、原地、稳定、自适应、通用性好。显然，迄今为止尚未发现兼具以上所有特性的排序算法。

这一结论可以从源码实现中逐一验证：归并排序稳定且高效但非原地；快速排序原地且快速但非稳定且最坏退化；堆排序原地、最坏仍是 $O(n \log n)$ 但非稳定；冒泡/插入排序原地、稳定、自适应但 $O(n^2)$；计数排序 $O(n+k)$ 但要求数据为有界非负整数。因此，在选择排序算法时，需要根据具体的数据特点和问题需求来决定，而不是寻找"万能排序"。

四、比较排序算法的源码解析

4.1 插入排序：小数据量场景的常用选择

insertion_sort.py 的实现展示了"已排序区间 + 插入"的经典结构：

def insertion_sort(nums: list[int]):
    """插入排序"""
    # 外循环：已排序区间为 [0, i-1]
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        # 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  # 将 nums[j] 向右移动一位
            j -= 1
        nums[j + 1] = base  # 将 base 赋值到正确位置

虽然插入排序的时间复杂度为 $O(n^2)$，但其单元操作相对较少（移动赋值而非成对交换），因此在小数据量的排序任务中非常受欢迎——这也是许多语言标准库对短数组回退到插入排序的原因。

4.2 快速排序：三种优化的演进

quick_sort.py 一次性给出了三个版本，正好对应 quick_sort.md 中讨论的优化路线：

1. 基础版 QuickSort：partition() 以 nums[left] 为基准数，"从右向左找首个小于基准数的元素"与"从左向右找首个大于基准数的元素"交错扫描并交换，最后将基准数交换到分界线。注意源码注释强调"从右往左查找"必须先于"从左往右查找"——summary.md 的 Q&A 解释了原因：最后一步交换要求 nums[left] >= nums[i]，若顺序颠倒，对 [0, 0, 0, 0, 1] 这样的输入会产生错误结果 [1, 0, 0, 0, 0]。
2. 中位基准数优化 QuickSortMedian：median_three() 从 left/mid/right 三个候选元素中选取中位数并交换至最左端，降低"每次选到最差基准数"导致 $O(n^2)$ 退化的概率。
3. 递归深度优化 QuickSortTailCall：对较短子数组递归、较长子数组改用循环迭代：

    def quick_sort(self, nums: list[int], left: int, right: int):
        """快速排序（递归深度优化）"""
        while left < right:
            pivot = self.partition(nums, left, right)
            # 对两个子数组中较短的那个执行快速排序
            if pivot - left < right - pivot:
                self.quick_sort(nums, left, pivot - 1)
                left = pivot + 1
            else:
                self.quick_sort(nums, pivot + 1, right)
                right = pivot - 1

从源码结构看，每轮划分后向下递归的子数组长度最大为原区间长度的一半，因此递归深度不超过 $\log n$，将空间复杂度从最坏 $O(n)$ 优化到 $O(\log n)$。

4.3 归并排序：分治策略的典型体现

merge_sort.py 的 merge_sort() 严格遵循"划分—递归—合并"流程：mid = (left + right) // 2 中点划分，递归排序左右两半后调用 merge() 合并。merge() 用双指针 i, j 依次比较左右子数组元素，将较小者复制到临时数组，最后整体写回原数组区间。合并时 if nums[i] <= nums[j] 中的 <=（相等时优先取左元素）正是其稳定性的代码保证。时间复杂度恒为 $O(n \log n)$，但需要 $O(n)$ 辅助空间（数组版）。

4.4 堆排序：借助堆结构的最坏稳定保证

heap_sort.py 分两步：先自底向上建堆（for i in range(len(nums) // 2 - 1, -1, -1): sift_down(...)，只堆化除叶节点外的节点），然后每轮把堆顶最大元素与尾部交换、以缩短后的堆长重新 sift_down()。堆排序在原地排序的前提下保证了最坏 $O(n \log n)$，但元素交换方式可能打乱相等元素的相对次序，因此是非稳定排序。

五、非比较排序算法：突破 $\Omega(n \log n)$ 下界

基于比较的排序受 $\Omega(n \log n)$ 下界约束，而非比较排序通过"值 → 下标"的映射绕开比较，代价是通用性受限。

• 计数排序（counting_sort.py）：桶排序的特例，通过统计各数值出现次数实现排序，适用于数据量大但取值范围有限且数据可转换为正整数的场景。源码特意区分了两个版本：counting_sort_naive() 简单直接但无法保持对象次序；counting_sort() 通过前缀和 + 倒序填充实现稳定计数排序。
• 桶排序（bucket_sort.py）：分桶 → 桶内排序 → 合并三步，体现分治策略，适用于数据体量很大的情况；关键在于数据平均分配到各桶，最差情况下所有元素落入同一桶、时间复杂度可退化至 $O(n^2)$。
• 基数排序（radix_sort.py）：按位数从低到高逐轮做稳定的桶分配，要求数据能表示为固定位数的数字。例如对 8 位学号，基数排序只需 8 轮、每轮仅按 0~9 分组；若直接整体用计数排序，则要为 $10^8$ 量级的取值预留计数数组，大量位置恒为 0（参见 exercises.md 中的学号例题）。

六、主流排序算法对比与选型

下图汇总了各算法在效率、稳定性、就地性、自适应性上的对比（来自排序章小结 summary.md）：

结合上述源码分析，可将结论整理为选型参考（各算法复杂度结论与仓库文档 summary.md 一致）：

算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	自适应性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$（标志位优化）	$O(1)$	稳定	是
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	否
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	是
快速排序	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(\log n)$（递归深度优化后）	不稳定	否
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$（数组版）	稳定	否
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳定	否
计数排序	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(k)$	稳定（完整版）	不适用
桶排序	$O(n + k)$	$O(n^2)$	$O(n + k)$	$O(n + k)$	取决于桶内排序	不适用
基数排序	$O(d(n + k))$	$O(d(n + k))$	$O(d(n + k))$	$O(n + k)$	稳定	不适用

其中 $k$ 为数据取值范围，$d$ 为数据位数。表中"最好时间复杂度"一列的 $O(n)$ 项依赖标志位/提前终止等优化，且以输入已（或近乎）有序为前提。

选型时可以按维度组合收敛候选：需要稳定且数据有界 → 计数/基数排序；内存紧张且要求最坏保证 → 堆排序；通用高性能场景 → 快速排序（带中位数与递归深度优化）；需要稳定 + 确定性 $O(n \log n)$ 且内存宽裕 → 归并排序；小数据量或近乎有序 → 插入/冒泡排序。

七、典型问题思考

排序章小结（summary.md）给出了几个值得深入思考的问题，此处摘录两点并给出要点：

Q1：排序算法稳定性在什么情况下是必需的？

多级排序场景下。例如学生有姓名和身高两个属性，先按姓名排序得到 (A, 180) (B, 185) (C, 170) (D, 170) 后再按身高排序：不稳定排序可能得到 (D, 170) (C, 170) (A, 180) (B, 185)，学生 D 和 C 的位置发生交换，姓名的有序性被破坏。

Q2：当数组中所有元素都相等时，快速排序的时间复杂度是 $O(n^2)$ 吗？

是的。处理这种退化情况的思路是将哨兵划分扩展为三段（小于、等于、大于基准数），仅递归"小于"和"大于"两部分——此时全相等输入仅一轮划分即可完成排序。

Q3：哨兵划分中查找方向可以交换吗？

不可以。以最左端元素为基准数时，必须"从右往左"再"从左往右"，否则在 i == j 跳出循环时可能出现 nums[j] > nums[left]，导致最后一步交换把比基准数大的元素放到最左端，划分失败（反例：[0, 0, 0, 0, 1]）。若以 nums[right] 为基准数，则结论正好反过来。

八、动手验证：运行与练习

仓库中每个算法文件都自带 __main__ 驱动代码，可直接运行观察排序结果，例如：

python codes/python/chapter_sorting/quick_sort.py
# 输出示例：快速排序完成后 nums = [0, 1, 2, 3, 4, 5]

如需系统性验证，Python 端提供了统一测试入口 test_all.py，JavaScript 端对应 test_all.js。想进一步巩固时，建议完成排序章的练习 exercises.md：手工模拟选择/冒泡排序的前几轮数组状态、用 $[2_a, 2_b, 1]$ 验证稳定性差异、比较计数排序与基数排序对固定位学号的适用性，并动手实现归并排序与计数排序——这些练习恰好覆盖了本文讨论的全部评价维度。