w wyl123ly 的博客
MD

算法-排序

66 KB 2026.10.11 原文件

算法-排序

一句话概括

排序(Sorting) 是把一组元素按某个全序关系重新排列的过程。它是计算机科学中被研究得最透彻的问题:既有 的理论下界,又有突破下界的非比较排序,还有几十年工程打磨出的混合实现(Timsort)。

本篇覆盖:稳定性与原地性、十种排序的逐一讲解与完整 Python 实现(冒泡 / 选择 / 插入 / 希尔 / 归并 / 快速 / 堆 / 计数 / 基数 / 桶)、总对比表、比较排序下界的决策树证明、Timsort 与工程实践、用排序解决实际问题、各语言标准库 API。

每种排序不仅给代码,还会逐步展示数组状态如何变化,让你看清算法在做什么。

是什么

排序问题的定义

输入:一个序列 和一个定义在全序上的比较关系 (满足自反性、反对称性、传递性、完全性)。

输出:输入的一个重排 。

关键点:排序算法本身不关心元素是什么,它只要求「任意两个元素可以比较大小」。

两个核心概念

稳定性(Stability)

稳定性的定义

若序列中有两个相等元素 (),排序后 仍然排在 前面,则称该排序算法稳定。

若相等元素的相对次序可能被打乱,则称不稳定。

为什么重要? 因为稳定排序可以组合实现多关键字排序:

先按「次要关键字」排一次,再按「主要关键字」稳定地排一次,最终结果就是「先按主要关键字、再按次要关键字」的正确顺序。

# 需求:先按分数降序,分数相同时按年龄升序
students = [("A", 90, 25), ("B", 90, 20), ("C", 85, 30)]

# 做法:先按次要键(年龄)排,再按主要键(分数)稳定排序
students.sort(key=lambda s: s[2])              # 次要关键字:年龄升序
students.sort(key=lambda s: -s[1])             # 主要关键字:分数降序(稳定)
# [('B', 90, 20), ('A', 90, 25), ('C', 85, 30)]  ✅

Python 的 sort 是 Timsort,天然稳定,所以这个「两趟排序」技巧可以工作。

原地性(In-place)

原地排序:只使用 或 的额外空间(不含输入本身)。反之叫非原地排序,需要 辅助空间。

  • 原地:冒泡、选择、插入、希尔、堆排序
  • 非原地:归并排序()、计数/基数/桶排序()

快速排序的「原地」要打引号

快排的 partition 确实只用了 额外空间,但递归栈平均要 、最坏要 。

严格说它是「原地但非 空间」。真正 空间的比较排序只有堆排序。

十种排序一览

分类算法一句话原理
交换类冒泡排序相邻两两比较,大的往后冒
快速排序选基准划分,左右递归
选择类选择排序每轮选最小的放到已排序末尾
堆排序用堆反复取最大值放到末尾
插入类插入排序把当前元素插到前面有序部分的正确位置
希尔排序分组做插入排序,逐步缩小增量
分治类归并排序分成两半分别排序再合并
非比较类计数排序统计每个值出现次数,按值域铺开
基数排序按位从低到高逐位稳定排序
桶排序按值域分桶,桶内单独排序

为什么需要它

排序是其他算法的前置条件

依赖排序的算法/场景为什么需要有序
二分查找只有有序才能每次砍一半, →
双指针去重 / 两数之和有序后可以用左右指针 完成
贪心算法(区间调度、霍夫曼编码)必须按某个键从小到大依次决策
并查集 + Kruskal 求最小生成树必须按边权排序后贪心
数据库 ORDER BY / GROUP BY排序后相邻元素才可归并
归并连接(Merge Join)两个有序表可以线性归并,避免嵌套循环

排序是算法分析的样板

排序几乎包含了所有重要的算法思想:

思想代表排序
暴力枚举冒泡、选择
增量构造插入排序
分治(Divide and Conquer)归并、快速
数据结构驱动堆排序
空间换时间计数、基数、桶排序
随机化随机化快排
混合优化Timsort

排序无处不在

  • 数据库 90% 以上的慢查询与排序有关(缺索引导致 filesort)
  • 前端表格、地图 POI 列表、搜索结果排序
  • git log 的拓扑排序、编译器优化中的活跃变量排序

核心内容

一、冒泡排序(Bubble Sort)

思想:反复扫描数组,比较相邻两个元素,若逆序就交换。每一轮结束后,最大的元素「冒」到末尾。

状态变化示例:[5, 1, 4, 2, 8]

轮次过程数组
初始—[5,1,4,2,8]
第 1 轮5>1 换;5>4 换;5>2 换;5<8 不换[1,4,2,5,8]
第 2 轮1<4;4>2 换;4<5[1,2,4,5,8]
第 3 轮无交换(已有序)→ 提前退出[1,2,4,5,8]

优化:若某一轮没有发生任何交换,说明已经有序,可以立即退出——这使最好情况降到 。

def bubble_sort(arr):
    """冒泡排序(原地、稳定)。

    时间:最好 O(n)(已有序,靠 swapped 提前退出),最坏/平均 O(n^2)
    空间:O(1)
    """
    a = arr[:]                       # 不修改调用者的列表
    n = len(a)
    for i in range(n - 1):
        swapped = False
        # 每轮结束后末尾 i+1 个元素已就位,内层可少比较 i 次
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:      # 严格大于才交换 -> 相等元素不换 -> 稳定
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:              # 本轮无交换,说明整体已有序
            break
    return a
维度值
最好 / 平均 / 最坏 / /
空间
稳定是
适用场景教学演示;实际几乎不用

二、选择排序(Selection Sort)

思想:每轮从未排序区间中选出最小的元素,与未排序区间的第一个元素交换。

状态变化示例:[5, 1, 4, 2, 8]

轮次未排序区间最小值操作数组
1[5,1,4,2,8]1(下标 1)与下标 0 交换[1,5,4,2,8]
2[5,4,2,8]2(下标 3)与下标 1 交换[1,2,4,5,8]
3[4,5,8]4(下标 2)自己换自己[1,2,4,5,8]
4[5,8]5自己换自己[1,2,4,5,8]

特点:交换次数固定为至多 次,是所有排序中最少的。当「交换」的代价远大于「比较」时(如元素是大型结构体)有优势。

选择排序不稳定

例:[5a, 5b, 2]。第 1 轮把 2 与 5a 交换,得到 [2, 5b, 5a]——两个 5 的相对次序被打乱了。

def selection_sort(arr):
    """选择排序(原地、不稳定)。

    时间:无论输入如何都是 O(n^2)(比较次数固定为 n(n-1)/2)
    空间:O(1)
    优点:交换次数最少(<= n-1 次)
    """
    a = arr[:]
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:    # 严格小于:找到更小的才更新
                min_idx = j
        if min_idx != i:             # 省掉一次自交换
            a[i], a[min_idx] = a[min_idx], a[i]
    return a
维度值
最好 / 平均 / 最坏 / /
空间
稳定否
适用场景交换代价高、 很小的场景

三、插入排序(Insertion Sort)

思想:把数组看成「已排序前缀 + 未排序后缀」。每次取后缀的第一个元素,在已排序前缀中从后往前找位置插入。

类比:整理扑克牌——摸一张新牌,从右往左找到位置插进去。

状态变化示例:[5, 1, 4, 2, 8]

轮次待插入过程数组
初始—认为 [5] 已排序`[5\1,4,2,8]`
111<5,5 后移,1 放到位置 0`[1,5\4,2,8]`
244<5,5 后移;4>1,停在位置 1`[1,4,5\2,8]`
322<5、2<4 依次后移;2>1,插入位置 1`[1,2,4,5\8]`
488>5,不需要移动`[1,2,4,5,8\]`

关键性质:对近乎有序的数据极快(内层 while 几乎不执行),最好情况 。这是它在 Timsort 中作为小区间排序器被保留的原因。

def insertion_sort(arr):
    """插入排序(原地、稳定)。

    时间:最好 O(n)(已有序),最坏/平均 O(n^2)
    空间:O(1)
    """
    a = arr[:]
    for i in range(1, len(a)):
        key = a[i]                   # 待插入的元素,先存起来(否则会被覆盖)
        j = i - 1
        # 从右往左找位置:比 key 大的元素统统右移一格
        while j >= 0 and a[j] > key: # 严格大于才右移 -> 相等元素不跨越 -> 稳定
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key               # 空出来的位置放 key
    return a
维度值
最好 / 平均 / 最坏 / /
空间
稳定是
适用场景小数组()的首选、近乎有序的数据、在线排序(边接收边排)

插入排序的隐藏优势:在线算法

插入排序可以在数据边到达边排序(online),不需要看到全部数据。冒泡和选择都做不到。

这个性质使它在流式场景中不可替代。

四、希尔排序(Shell Sort)

思想:插入排序在「小规模」或「近乎有序」时快。希尔排序先用较大的增量(gap)把数组分成若干子序列分别做插入排序,让元素一次能跨越很远,快速接近有序;再逐步缩小 gap,最后 gap=1 时做一次普通插入排序即可收尾。

关键洞察:插入排序慢是因为元素一次只能移动一格。用 gap 分组后,一个元素一次能移动 gap 格,先把「逆序程度」大幅降低,最后一步的小 gap 插入排序就非常快。

状态变化示例:[8, 5, 3, 9, 1, 7],取 gap 序列 [3, 1]

阶段gap分组(同色为一组)组内插入排序后
初始—[8,5,3,9,1,7][8,5,3,9,1,7]
13(8,9)、(5,1)、(3,7)[8,1,3,9,5,7]
21整体一组[1,3,5,7,8,9]

增量序列的选择:没有公认最优解。常见有:

增量序列最坏复杂度说明
最简单,Hibbard 之前常用
Hibbard:常用
Sedgewick:实践中很快
Knuth:《算法》教材推荐
def shell_sort(arr, gaps=None):
    """希尔排序(原地、不稳定)。

    时间:取决于增量序列,Knuth 序列约 O(n^1.5),最好 O(n log n)
    空间:O(1)
    不稳定原因:相同元素可能被分到不同组,跨组交换会改变相对次序
    """
    a = arr[:]
    n = len(a)
    if gaps is None:
        # Knuth 序列 1, 4, 13, 40, ...,先算到不超过 n 的最大值再递减
        gaps, h = [], 1
        while h < n:
            gaps.append(h)
            h = 3 * h + 1
        gaps.reverse()

    for gap in gaps:
        # 对每个以 gap 为间隔的子序列做插入排序
        for i in range(gap, n):
            key = a[i]
            j = i - gap
            while j >= 0 and a[j] > key:
                a[j + gap] = a[j]           # 一次跨越 gap 格,这是提速关键
                j -= gap
            a[j + gap] = key
    return a
维度值
最好 / 平均 / 最坏 / 取决于增量 / (Knuth 序列)
空间
稳定否
适用场景中等规模()、内存受限、要求原地

五、归并排序(Merge Sort)

思想:典型的分治(Divide and Conquer)。

  1. 分(Divide):把数组从中间切成两半
  2. 治(Conquer):递归地对两半排序
  3. 合(Combine):把两个有序子数组合并成一个有序数组(双指针线性归并)

合并过程示例:合并 [1, 5] 与 [2, 4]

步骤左指针右指针比较取谁结果
1121 < 2左 1[1]
2525 > 2右 2[1,2]
3545 > 4右 4[1,2,4]
45越界—左 5[1,2,4,5]

递推式:

用主定理验证:,,,,属情况 2,故 (详见 算法-复杂度分析)。

关键优势:

  • 复杂度稳定:无论什么输入都是 ,没有快排的最坏情况
  • 天然稳定:合并时若左右相等,优先取左边的即可
  • 适合链表:链表归并只需 额外空间
  • 适合外部排序:数据大到内存装不下时,归并可以分块读入
def merge_sort(arr):
    """归并排序(非原地、稳定)。

    时间:任何情况都是 O(n log n)
    空间:O(n)(合并时的辅助数组)+ O(log n)(递归栈)
    递推式:T(n) = 2T(n/2) + O(n) = O(n log n)
    """
    a = arr[:]
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])        # 递归排左半
    right = merge_sort(a[mid:])       # 递归排右半
    return _merge(left, right)


def _merge(left, right):
    """把两个有序数组合并成一个有序数组。"""
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        # 用 <= 而不是 <:左右相等时先取左边,从而保持稳定
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])           # 收尾:把剩余部分整体接上
    merged.extend(right[j:])
    return merged


def merge_sort_inplace(arr):
    """归并排序的原地版本(只用一个辅助数组,节省反复分配的开销)。"""
    a = arr[:]
    aux = [0] * len(a)

    def sort(lo, hi):
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid, hi)
        if a[mid - 1] <= a[mid]:
            return                    # 已天然有序(Timsort 也用了这个优化)
        i, j, k = lo, mid, lo
        while i < mid and j < hi:
            if a[i] <= a[j]:
                aux[k] = a[i]; i += 1
            else:
                aux[k] = a[j]; j += 1
            k += 1
        while i < mid:
            aux[k] = a[i]; i += 1; k += 1
        while j < hi:
            aux[k] = a[j]; j += 1; k += 1
        a[lo:hi] = aux[lo:hi]         # 拷回原数组

    sort(0, len(a))
    return a
维度值
最好 / 平均 / 最坏 / /
空间
稳定是
适用场景要求稳定性、数据规模大、链表排序、外部排序

六、快速排序(Quick Sort)

思想:选一个基准(pivot),把数组划分成「小于等于基准」和「大于基准」两部分(partition),再递归处理两部分。

为什么它最快? 因为 partition 的访存模式对 CPU 缓存极友好(顺序扫描 + 就地交换),而归并需要额外的 拷贝。同为 ,快排的常数因子小得多。

partition 的两种写法
Lomuto 划分(单指针,易懂)

选定末尾元素作基准,用一个指针 i 维护「小于等于区」的右边界。

示例:[3, 7, 1, 5],pivot = 5(末尾)

ja[j]a[j] <= 5?操作数组
03是i=0→1[3,7,1,5]
17否不动[3,7,1,5]
21是交换 a[1],a[2],i=1→2[3,1,7,5]
———交换 a[2],a[3](pivot 归位)[3,1,5,7]

结果:pivot 5 落在下标 2,左边 [3,1] 都 ,右边 [7] 都 。

Hoare 划分(双指针,交换次数少)

左右两个指针向中间靠拢,左指针找「不小于 pivot」的,右指针找「不大于 pivot」的,交换后继续。

示例:[3, 7, 1, 5],pivot = a[0] = 3

步骤ij说明数组
初始03左找 ≥3,右找 ≤3[3,7,1,5]
10→13→2a[1]=7≥3 停;a[2]=1≤3 停—
2——交换 a[1],a[2][3,1,7,5]
31→22→1i=2 与 j=1 交错,结束—
4——交换 a[0],a[1](pivot 归位)[1,3,7,5]
"""快速排序的多种实现:Lomuto、Hoare、随机化、三路划分。"""
import random


def quicksort_lomuto(arr):
    """快排 + Lomuto 划分(取末尾元素作基准)。原地、不稳定。

    时间:平均 O(n log n),最坏 O(n^2)(已排序数组 + 固定基准)
    空间:O(log n) 平均递归栈,最坏 O(n)
    """
    a = arr[:]

    def sort(lo, hi):
        if lo >= hi:
            return
        p = partition_lomuto(a, lo, hi)
        sort(lo, p - 1)          # 基准已在最终位置,不再参与
        sort(p + 1, hi)

    sort(0, len(a) - 1)
    return a


def partition_lomuto(a, lo, hi):
    """Lomuto 划分:返回基准的最终下标。"""
    pivot = a[hi]                    # 取末尾元素作基准
    i = lo                           # i 指向"小于等于区"的下一个空位
    for j in range(lo, hi):
        if a[j] <= pivot:            # <= 保证与 pivot 相等的元素留在左侧
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]        # 把基准放到分界点
    return i


def quicksort_hoare(arr, lo=0, hi=None):
    """快排 + Hoare 划分:交换次数更少,实际更快。原地、不稳定。"""
    a = arr[:] if hi is None else arr
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    p = partition_hoare(a, lo, hi)
    quicksort_hoare(a, lo, p)        # Hoare 划分返回的是分界,不是基准下标
    quicksort_hoare(a, p + 1, hi)
    return a


def partition_hoare(a, lo, hi):
    """Hoare 划分:返回右半区的起始下标 j(a[lo..j] <= a[j+1..hi])。"""
    pivot = a[(lo + hi) // 2]        # 取中间元素作基准,天然抗有序输入
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            return j                 # 两指针交错,划分完成
        a[i], a[j] = a[j], a[i]


def quicksort_random(arr):
    """随机化快排:每轮随机选基准,避免被有序输入或恶意输入打成 O(n^2)。"""
    a = arr[:]

    def sort(lo, hi):
        if lo >= hi:
            return
        r = random.randint(lo, hi)   # 随机挑一个位置与末尾交换,复用 Lomuto
        a[r], a[hi] = a[hi], a[r]
        p = partition_lomuto(a, lo, hi)
        sort(lo, p - 1)
        sort(p + 1, hi)

    sort(0, len(a) - 1)
    return a


def quicksort_3way(arr):
    """三路快排(荷兰国旗问题):把数组分成 <pivot / ==pivot / >pivot 三块。

    对"大量重复元素"的输入有巨大优势:重复元素一次全部归位,不再递归。
    这就是为什么工程实现(如 Java 的 DualPivotQuicksort)要特判重复值。
    """
    a = arr[:]

    def sort(lo, hi):
        if lo >= hi:
            return
        pivot = a[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi       # [lo,lt) < p, [lt,i) == p, (gt,hi] > p
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1              # 换过来的元素还没检查,i 不动
            else:
                i += 1
        sort(lo, lt - 1)             # 相等区 [lt, gt] 已完成,跳过
        sort(gt + 1, hi)

    sort(0, len(a) - 1)
    return a
基准选择策略
策略说明效果
固定取首/尾实现最简单有序输入退化 ,不可用于生产
随机取每轮 random 选一个期望 ,抗恶意输入
三数取中取首、中、尾的中位数抗有序输入,无随机开销
中位数的中位数(BFPRT)严格 选出中位数保证最坏 ,但常数大,实践不用
三路划分额外处理「等于基准」大量重复元素时从 降到

快排最坏情况与随机化的作用

若每次划分都分成 与 :。

随机化后,划分结果成为随机变量,任何固定输入都无法保证每次都划分不均,

期望复杂度为 ,退化概率随 指数级下降。

维度值
最好 / 平均 / 最坏 / /
空间 平均 / 最坏(递归栈)
稳定否(划分时远距离交换会打乱相等元素)
适用场景通用内存排序的默认选择,尤其大数组

七、堆排序(Heap Sort)

思想:把数组看成一棵完全二叉树(下标 的孩子是 与 )。先建大顶堆(父节点 子节点),然后反复把堆顶(最大值)与末尾交换,堆大小减一,再下沉修复堆。

堆的两个核心操作:

  • 下沉(sift down / heapify):节点与较大的孩子交换,直到满足堆性质。
  • 建堆(build heap):从最后一个非叶节点开始依次下沉。虽然单次是 ,但整体只需 (因为大部分节点都在底层,下沉距离很短)

状态变化示例:[4, 10, 3, 5, 1]

阶段操作数组
建堆从下标 1 开始下沉:10>4 换[10,5,3,4,1]
取最大堆顶 10 与末尾 1 交换,堆缩小`[1,5,3,4\10]`
修复1 下沉:与 5 换,再与 4 换`[5,4,3,1\10]`
取最大5 与 1 交换`[1,4,3\5,10]`
修复1 与 4 换`[4,1,3\5,10]`
取最大4 与 3 交换`[3,1\4,5,10]`
修复3 不需要下沉`[3,1\4,5,10]`
取最大3 与 1 交换`[1\3,4,5,10]`
完成—[1,3,4,5,10]
def heap_sort(arr):
    """堆排序(原地、不稳定)。

    时间:任何情况都是 O(n log n) —— 这是它相对快排的最大优势
    空间:O(1) —— 所有比较排序里空间最优,不需要递归栈
    """
    a = arr[:]
    n = len(a)

    def sift_down(i, size):
        """把下标 i 的节点下沉到合适位置,维持大顶堆性质。"""
        while True:
            largest = i
            l, r = 2 * i + 1, 2 * i + 2
            if l < size and a[l] > a[largest]:
                largest = l
            if r < size and a[r] > a[largest]:
                largest = r
            if largest == i:              # 已满足堆性质,停止
                return
            a[i], a[largest] = a[largest], a[i]
            i = largest                   # 继续往下检查

    # 第 1 步:建堆。从最后一个非叶节点 n//2 - 1 逆序下沉,整体 O(n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n)

    # 第 2 步:反复取堆顶(当前最大值)放到末尾,堆区间逐步缩小
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]       # 最大值归位
        sift_down(0, end)                 # 修复剩余部分的堆性质
    return a


def heap_sort_with_local_heap(arr, k):
    """堆排序的实用变体:求前 k 大(用大小为 k 的小顶堆),复杂度 O(n log k)。

    这是一个非常高频的面试题:n=10^7、k=10 时,比完整排序快几个数量级。
    """
    import heapq
    a = arr[:]
    if k <= 0:
        return []
    heap = a[:k]                          # 先放前 k 个
    heapq.heapify(heap)                   # 小顶堆:堆顶是这 k 个里最小的
    for x in a[k:]:
        if x > heap[0]:                   # 比当前门槛大才可能进前 k
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)
维度值
最好 / 平均 / 最坏 / /
空间
稳定否
适用场景需要保证最坏 且空间受限(嵌入式、实时系统);Top-K 问题

八、计数排序(Counting Sort)

思想:如果元素是小范围整数,可以直接统计每个值出现了几次,然后按值从小到大铺开——完全不需要比较。

步骤:

  1. 找出最大值 max_val 与最小值 min_val
  2. 开一个大小为 max_val - min_val + 1 的计数数组
  3. 遍历输入,count[a[i] - min_val] += 1
  4. 按值从小到大,把 count[v] 个 v + min_val 依次写回

状态变化示例:[4, 1, 4, 2, 1, 4]()

步骤计数数组(下标 1..4)
统计完成[2, 1, 0, 3](1 出现 2 次、2 出现 1 次、4 出现 3 次)
按值铺开[1,1,2,4,4,4]

稳定性:上面的朴素写法不稳定。要稳定,需要改成前缀和 + 从右往左回填(这是基数排序能用它的前提):

def counting_sort(arr):
    """计数排序(非原地、稳定)。

    时间:O(n + k),k 为值域大小
    空间:O(n + k)
    限制:只适用于整数(或可映射为紧凑整数)的数据
    """
    if not arr:
        return []
    lo, hi = min(arr), max(arr)
    k = hi - lo + 1
    count = [0] * k
    for x in arr:                        # 第 1 遍:统计频次
        count[x - lo] += 1

    # 前缀和:count[i] 变成"值 <= i + lo 的元素个数"
    for i in range(1, k):
        count[i] += count[i - 1]

    out = [0] * len(arr)
    # 从右往左回填,这样相等元素中后出现的排在后 -> 稳定
    for x in reversed(arr):
        count[x - lo] -= 1
        out[count[x - lo]] = x
    return out
维度值
最好 / 平均 / 最坏 / /
空间
稳定是(用前缀和 + 逆序回填的实现)
适用场景值域小的整数,如年龄(0-150)、分数(0-100)、字符(0-255)

计数排序不适合值域大的数据

若数据是 [1, 10^9] 中的两个数,,光开计数数组就要几 GB 内存。

这时应该用基数排序或普通比较排序。

九、基数排序(Radix Sort)

思想:把整数按位(digit)拆开,从最低位到最高位(LSD)依次用稳定排序(通常是计数排序)排一遍。因为每轮都是稳定的,高位排序不会破坏低位已建立的次序。

为什么必须稳定? 举例:[13, 21, 12]

轮次排序键结果
第 1 轮个位[21, 12, 13](个位 1,2,3)
第 2 轮十位[12, 13, 21] ✅

第 2 轮按十位排时,21 的十位是 2,12 和 13 的十位都是 1。若十位相同时不保持第 1 轮的相对次序(12 在 13 前),结果就会错。

复杂度:设最大数有 位,每位的值域为 (十进制 ):

状态变化示例:[170, 45, 75, 90, 802, 24, 2, 66]

轮次按个位排按十位排按百位排
结果[170,90,802,2,24,45,75,66][802,2,24,45,66,170,75,90][2,24,45,66,75,90,170,802]
def radix_sort(arr, base=10):
    """基数排序 LSD(非原地、稳定)。

    时间:O(d * (n + base)),d 为最大数的位数
    空间:O(n + base)
    限制:元素必须是非负整数(负数可先分离再翻转)
    """
    if not arr:
        return []
    a = arr[:]
    max_val = max(a)
    exp = 1                                  # 当前处理的位:1=个位,10=十位,...
    while max_val // exp > 0:
        a = _counting_sort_by_digit(a, exp, base)
        exp *= base
    return a


def _counting_sort_by_digit(a, exp, base):
    """按 (x // exp) % base 这一位做稳定计数排序。"""
    count = [0] * base
    for x in a:
        count[(x // exp) % base] += 1
    for i in range(1, base):
        count[i] += count[i - 1]             # 前缀和 -> 定位置
    out = [0] * len(a)
    for x in reversed(a):                    # 逆序回填 = 稳定
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out


def radix_sort_with_negatives(arr, base=10):
    """支持负数的基数排序:负数取绝对值排好序后翻转再拼接。"""
    neg = [-x for x in arr if x < 0]
    pos = [x for x in arr if x >= 0]
    return [-x for x in reversed(radix_sort(neg, base))] + radix_sort(pos, base)
维度值
最好 / 平均 / 最坏 / 同 / 同
空间
稳定是
适用场景位数少的大量整数(如手机号、身份证、IP 地址);字符串排序(按字符位)

十、桶排序(Bucket Sort)

思想:把值域均匀划分成若干个桶,每个元素按值放进对应桶;桶内单独排序(常用插入排序);最后按桶顺序拼接。

前提:输入数据大致均匀分布。否则所有元素挤进一个桶,退化成对 个元素做插入排序,。

状态变化示例:[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68],分 10 个桶

桶号元素桶内排序后
1[0.17, 0.12][0.12, 0.17]
2[0.26, 0.21, 0.23][0.21, 0.23, 0.26]
3[0.39][0.39]
6[0.68][0.68]
7[0.78, 0.72][0.72, 0.78]
9[0.94][0.94]

拼接结果:[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

def bucket_sort(arr, bucket_count=None):
    """桶排序(非原地、稳定取决于桶内排序)。

    时间:平均 O(n + k)(均匀分布),最坏 O(n^2)(全部落进同一个桶)
    空间:O(n + k)
    """
    if not arr:
        return []
    n = len(arr)
    if bucket_count is None:
        bucket_count = n
    lo, hi = min(arr), max(arr)
    if hi == lo:                             # 所有元素相同,直接返回
        return arr[:]
    span = (hi - lo) / bucket_count

    buckets = [[] for _ in range(bucket_count)]
    for x in arr:
        # 计算桶号;用 min 防止 x == hi 时下标越界
        idx = min(int((x - lo) / span), bucket_count - 1)
        buckets[idx].append(x)

    out = []
    for b in buckets:
        out.extend(insertion_sort(b))        # 桶内用插入排序(小数组最快)
    return out
维度值
最好 / 平均 / 最坏 / /
空间
稳定取决于桶内排序(用插入排序则稳定)
适用场景数据均匀分布的浮点数(如 0-1 之间的随机数)

总对比表

算法最好平均最坏空间稳定原地适用场景
冒泡排序✅✅教学演示
选择排序❌✅交换代价高、 极小
插入排序✅✅小数组()、近乎有序、在线
希尔排序依赖增量❌✅中等规模、内存受限
归并排序✅❌要求稳定、链表、外部排序
快速排序❌✅通用内存排序的默认选择
堆排序❌✅需保证最坏性能、空间受限、Top-K
计数排序✅❌值域小的整数
基数排序✅❌位数少的大量整数/字符串
桶排序✅❌均匀分布的浮点数

一张表记住怎么选

- 通用默认 → 快速排序(或直接用标准库的 Timsort / introsort)

- 要稳定 → 归并排序 / Timsort

- 空间极紧 → 堆排序

- 要保证最坏 → 堆排序 / 归并排序

- 小数组() → 插入排序

- 值域小的整数 → 计数排序

- Top-K → 大小为 的堆,

比较类排序的下界:

定理

任何只依赖元素两两比较的排序算法,最坏情况下至少需要 次比较。

决策树证明思路:

第 1 步:把算法建模成一棵决策树。

算法的每一次「比较 与 」是一个内部节点,有两个分支( 和 )。到达叶子时算法必须已经确定整个排列。

第 2 步:数叶子数。

个元素有 种可能的初始排列,每种都必须被引导到不同的叶子(否则算法会对两种不同输入给出同一个输出,必然有一个是错的)。所以决策树至少要有 个叶子。

第 3 步:二叉树高度与叶子数的关系。

高度为 的二叉树最多有 个叶子,因此

第 4 步:用 Stirling 公式估计 。

(更精确地用 Stirling 公式:。)

第 5 步:结论。 决策树高度 就是该算法的最坏比较次数,所以

这解释了为什么归并排序和堆排序是「最优」的比较排序——它们达到了这个下界。

下界只针对「比较类」排序

下界依赖「只能通过比较获取信息」这个前提。计数/基数/桶排序通过直接访问元素的值(数组下标索引)绕过了比较,

因此可以突破 。它们被称为非比较排序。

非比较排序的适用条件

条件说明反例
元素可映射为有限的整数键计数/基数需要按下标索引任意精度实数、复杂对象
值域 与 同阶 才有意义 但值域
基数排序需要位可分解整数、定长字符串变长字符串(需先补齐)
桶排序需要分布均匀否则退化 幂律分布的数据
需要额外空间 内存受限时不行嵌入式环境

Timsort 与工程实践

为什么标准库不用「纯快排」或「纯归并」

Python 的 list.sort()、Java 对象排序、Android 都使用 Timsort(Tim Peters 于 2002 年为 Python 设计)。

它是归并 + 插入的混合算法,核心洞察是:真实数据往往已经部分有序。

Timsort 的四个关键机制:

机制作用
run(自然有序段)检测扫描出已经升序(或严格降序,就地反转)的连续片段,长度记作 run
minrun 扩展若 run 长度 (32~64),用插入排序把它补到 minrun 长
归并栈把 run 压栈,按不变式(类似斐波那契)合并相邻 run,保证
galloping(飞奔模式)合并时若一方连续多次胜出,改用二分跳转代替逐个比较,处理部分有序数据极快

复杂度:

情况复杂度说明
最好数据已完全有序,只有一个 run
平均 / 最坏有严格证明
空间归并需要临时缓冲
稳定性稳定这是标准库选择它的重要原因

其他语言的工程选择:

语言算法原因
Python(list.sort)Timsort稳定 + 对真实数据快
Java(对象数组)Timsort稳定是规范要求
Java(基本类型数组)Dual-Pivot Quicksort基本类型不需要稳定性,快排更快
C++(std::sort)Introsort(快排 + 堆排 + 插入)快排为主,深度超限切堆排保证
C++(std::stable_sort)Timsort 类归并显式要求稳定
C#(Array.Sort)Introsort不稳定;OrderBy 用稳定归并
Go(slices.Sort)pdqsort(模式破除快排)抗恶意输入

工程启示

生产级排序都是混合算法:

① 小区间用插入排序(减少递归开销);

② 主体用快排或归并(保证 );

③ 加随机化或 introsort 的深度限制(防止最坏情况);

④ 针对重复值做三路划分;

⑤ 特殊检测已有序段(利用真实数据的局部性)。

单纯实现「教科书快排」在生产环境是不够的。

用排序解决实际问题

应用 1:合并区间(LeetCode 56)

思路:按区间起点排序后,能合并的区间一定相邻。

def merge_intervals(intervals):
    """合并所有重叠区间。时间 O(n log n)(瓶颈在排序),空间 O(n)。"""
    if not intervals:
        return []
    # 按起点升序排序:排序后重叠区间必然相邻,一趟扫描即可
    intervals = sorted(intervals, key=lambda x: x[0])
    merged = [list(intervals[0])]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:           # 与上一个区间重叠或相接
            merged[-1][1] = max(merged[-1][1], end)   # 只扩展右端点
        else:
            merged.append([start, end])      # 不重叠,开启新区间
    return [tuple(x) for x in merged]


if __name__ == "__main__":
    print(merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]))
    # [(1, 6), (8, 10), (15, 18)]
应用 2:自定义排序与比较器
"""自定义排序的三种写法(Python 生态里 key 优先,cmp_to_key 是兜底)。"""
from functools import cmp_to_key


def sort_by_key():
    """① key 函数:最推荐,O(n log n) 且每次比较不重复计算键。"""
    words = ["banana", "apple", "cherry", "date"]
    # 先按长度升序,长度相同按字典序
    return sorted(words, key=lambda w: (len(w), w))
    # ['date', 'apple', 'banana', 'cherry']


def sort_numeric_string():
    """② 混合类型排序:把数字字符串按数值排(否则 '10' < '9')。"""
    nums = ["10", "9", "100", "1"]
    return sorted(nums, key=int)          # ['1', '9', '10', '100']


def sort_with_cmp():
    """③ cmp 比较器:只在 key 表达不出来时用(Python 3 需 cmp_to_key 包装)。"""

    def cmp(a, b):
        # 规则:先比长度,短的在前;长度相同按字典序倒序
        if len(a) != len(b):
            return -1 if len(a) < len(b) else 1
        if a == b:
            return 0
        return -1 if a > b else 1

    words = ["bb", "a", "cc", "dd"]
    return sorted(words, key=cmp_to_key(cmp))


def multi_key_mixed_order():
    """④ 多关键字、方向不同:用元组 + 负号(数值)或分两趟稳定排序(字符串)。"""
    students = [("Alice", 90, 25), ("Bob", 90, 20), ("Cara", 85, 30)]
    # 分数降序、年龄升序:数值可以直接取负
    by_num = sorted(students, key=lambda s: (-s[1], s[2]))
    # 字符串无法取负:先按次要键排,再按主要键稳定排序
    by_str = sorted(students, key=lambda s: s[2])
    by_str.sort(key=lambda s: s[0], reverse=True)   # Timsort 稳定,保住上一步顺序
    return by_num, by_str


if __name__ == "__main__":
    print(sort_by_key())
    print(sort_numeric_string())
    print(sort_with_cmp())
    print(multi_key_mixed_order()[0])
应用 3:多关键字排序(基数思想)
def sort_records(records):
    """按 (优先级降序, 时间升序, 名称升序) 三关键字排序。

    如果 key 元组能表达(数值可取负),直接用 key 最清晰;
    如果某些键的方向无法用取负表达(如字符串降序),用"逐趟稳定排序"。
    """
    # 趟 1:最次要的关键字
    records = sorted(records, key=lambda r: r["name"])
    # 趟 2:次关键字(时间升序)
    records = sorted(records, key=lambda r: r["time"])
    # 趟 3:最主要的关键字(优先级降序,必须用稳定排序保住前两趟结果)
    records = sorted(records, key=lambda r: r["priority"], reverse=True)
    return records


if __name__ == "__main__":
    data = [
        {"name": "b", "time": 2, "priority": 1},
        {"name": "a", "time": 1, "priority": 2},
        {"name": "c", "time": 1, "priority": 1},
    ]
    for r in sort_records(data):
        print(r)
    # priority=2 的 a 最先;priority=1 里 time=1 的 c 在 time=2 的 b 之前
应用 4:Top-K 与前 K 个高频元素
import heapq
from collections import Counter


def top_k_frequent(nums, k):
    """返回出现频率最高的 k 个元素。时间 O(n log k),优于完整排序的 O(n log n)。"""
    freq = Counter(nums)                     # 第 1 步:计数 O(n)
    # 第 2 步:维护大小为 k 的小顶堆,堆顶是"当前第 k 名"
    return [x for x, _ in heapq.nlargest(k, freq.items(), key=lambda kv: kv[1])]


def kth_largest(nums, k):
    """第 k 大的元素:用快速选择(Quickselect),平均 O(n)。

    思路与快排一致,但每次只递归包含目标的那一半,因此
    T(n) = T(n/2) + O(n) = O(n)(几何级数收敛)。
    """
    import random
    a = nums[:]
    lo, hi = 0, len(a) - 1
    target = len(a) - k                      # 第 k 大 = 升序的第 len-k 个
    while True:
        r = random.randint(lo, hi)
        a[r], a[hi] = a[hi], a[r]
        p = partition_lomuto_local(a, lo, hi)
        if p == target:
            return a[p]
        if p < target:
            lo = p + 1                       # 目标在右半,丢弃左半
        else:
            hi = p - 1


def partition_lomuto_local(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i


if __name__ == "__main__":
    print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))   # [1, 2]
    print(kth_largest([3, 2, 1, 5, 6, 4], 2))      # 5
应用 5:数逆序对(归并排序的副产品)
def count_inversions(arr):
    """统计逆序对数量(i < j 但 a[i] > a[j]),用归并排序,O(n log n)。

    为什么归并能数逆序对?合并左右两个有序数组时,
    每当从右半取一个元素,就说明它比左半剩下的所有元素都小
    -> 一次性贡献 len(left) - i 个逆序对。
    """
    a = arr[:]
    aux = [0] * len(a)

    def sort(lo, hi):
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        cnt = sort(lo, mid) + sort(mid, hi)
        i, j, k = lo, mid, lo
        while i < mid and j < hi:
            if a[i] <= a[j]:
                aux[k] = a[i]; i += 1
            else:
                aux[k] = a[j]; j += 1
                cnt += mid - i           # 关键:左半剩余元素都与 a[j] 构成逆序
            k += 1
        while i < mid:
            aux[k] = a[i]; i += 1; k += 1
        while j < hi:
            aux[k] = a[j]; j += 1; k += 1
        a[lo:hi] = aux[lo:hi]
        return cnt

    return sort(0, len(a))


if __name__ == "__main__":
    print(count_inversions([2, 4, 1, 3, 5]))   # 3: (2,1),(4,1),(4,3)

各语言标准库排序 API

Python
data = [3, 1, 2]

data.sort()                                  # 原地排序(Timsort,稳定),返回 None
new = sorted(data, reverse=True)             # 返回新列表
out = sorted(data, key=lambda x: -x)         # key 函数(推荐)
out = sorted(words, key=str.lower)           # 忽略大小写
out = sorted(rows, key=lambda r: (r[0], -r[1]))   # 多关键字

# 注意事项
# 1) list.sort() 返回 None,不是列表!写 x = data.sort() 会得到 None
# 2) key 只对每个元素计算一次(Schwartzian transform),比 cmp 快得多
# 3) sorted 是稳定排序,可安全用于"多趟排序"技巧
# 4) heapq.nlargest/nsmallest 在有 k << n 时优于完整排序
JavaScript
const data = [3, 1, 2];

data.sort();                                 // ⚠️ 默认按 UTF-16 字符串排序!
[10, 9, 1].sort();                           // [1, 10, 9]  ← 不是数值序

data.sort((a, b) => a - b);                  // 数值升序(必须给比较器)
data.sort((a, b) => b - a);                  // 数值降序
rows.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name));

// ES2019 起保证稳定(V8 用 Timsort)
// 注意:sort 原地修改数组,需要副本用 [...data].sort(...)
// Array.prototype.toSorted()(ES2023)返回新数组
Java
int[] a = {3, 1, 2};
Arrays.sort(a);                              // 基本类型:双轴快排,不稳定

Integer[] b = {3, 1, 2};
Arrays.sort(b, Comparator.reverseOrder());   // 对象:Timsort,稳定

List<Person> people = ...;
people.sort(Comparator.comparingInt(Person::getAge)     // 主键
                      .thenComparing(Person::getName)); // 次键
// 注意:Arrays.sort(int[]) 是不稳定的,需要稳定性时先装箱成 Integer[]
C#
int[] a = { 3, 1, 2 };
Array.Sort(a);                                          // Introsort,不稳定
Array.Sort(a, (x, y) => y.CompareTo(x));                // 降序

var sorted = people.OrderBy(p => p.Age)                 // OrderBy 稳定(LINQ)
                   .ThenByDescending(p => p.Name)
                   .ToList();
C++
#include <algorithm>
std::vector<int> v{3, 1, 2};
std::sort(v.begin(), v.end());                          // Introsort,不稳定,O(n log n)
std::stable_sort(v.begin(), v.end());                   // 稳定归并
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });   // 降序
// 注意:比较器必须满足严格弱序(strict weak ordering),
// 写成 <= 会导致未定义行为与段错误!必须用 <

各语言 API 的三大坑

① JS 默认字典序:[10,9,1].sort() 得到 [1,10,9],必须传比较器。

② C++ 比较器必须是严格弱序:用 <= 而不是 < 会让 std::sort 越界崩溃。

③ Python sort() 返回 None:x = lst.sort() 是新手最常见的 bug 之一。

怎么用

选择排序算法的决策流程

数据是什么类型?
├── 整数且值域小(如 0-1000)
│   └── 计数排序 O(n+k)
├── 整数且位数少(如手机号、ID)
│   └── 基数排序 O(d(n+k))
├── 浮点数且分布均匀(如 0-1 之间)
│   └── 桶排序 O(n+k)
└── 一般可比较对象
    ├── 需要稳定?
    │   ├── 是 → 归并排序 / Timsort O(n log n)
    │   └── 否 → 快速排序 O(n log n) 平均
    ├── 需要保证最坏 O(n log n)?
    │   └── 堆排序(且 O(1) 空间)
    └── n 很小(<= 16)?
        └── 插入排序

用实验验证复杂度

"""实测各排序算法的耗时,验证理论复杂度。"""
import random
import time

ALGOS = {
    "bubble": bubble_sort,
    "selection": selection_sort,
    "insertion": insertion_sort,
    "shell": shell_sort,
    "merge": merge_sort,
    "quick(random)": quicksort_random,
    "heap": heap_sort,
    "counting": counting_sort,
    "radix": radix_sort,
    "bucket": bucket_sort,
}


def bench(sizes=(200, 400, 800), repeat=3):
    """对每个规模、每个算法测最快一次耗时。"""
    print(f"{'算法':16s}" + "".join(f"{'n=' + str(s):>12s}" for s in sizes))
    for name, fn in ALGOS.items():
        row = f"{name:16s}"
        for s in sizes:
            data = [random.randint(0, 10_000) for _ in range(s)]
            best = float("inf")
            for _ in range(repeat):
                t0 = time.perf_counter()
                out = fn(data)
                best = min(best, time.perf_counter() - t0)
            # 顺便验证正确性
            assert out == sorted(data), f"{name} 在 n={s} 时结果错误"
            row += f"{best*1000:11.2f}ms"
        print(row)
    # 观察:n 翻倍时,O(n^2) 类的耗时约 4 倍,O(n log n) 类约 2.2 倍


def bench_worst_case(n=1500):
    """最坏情况对比:已排序输入对固定基准快排是致命的。"""
    data = list(range(n))
    for name, fn in (("quick(random)", quicksort_random), ("merge", merge_sort), ("heap", heap_sort)):
        t0 = time.perf_counter()
        fn(data)
        print(f"{name:16s} 已排序 n={n}: {time.perf_counter()-t0:.4f}s")


if __name__ == "__main__":
    bench()
    bench_worst_case()

实测的注意事项

① 用 time.perf_counter() 而不是 time.time()(后者精度低且受系统时钟调整影响);

② 多次运行取最小值(减少 GC 与系统调度噪声);

③ 一定要在计时外验证结果正确性,否则可能测的是「快速但错误」的算法;

④ 数据用随机生成,并单独测一次「已排序输入」——很多排序的最坏情况就藏在这里。

注意事项与常见坑

坑 1:Python list.sort() 返回 None

```python

a = [3, 1, 2]

b = a.sort() # ❌ b 是 None!sort 是原地操作

c = sorted(a) # ✅ 返回新列表

```

这是 Python 新手最高频的错误之一。

坑 2:sort 的 key 在排序期间被修改

如果 key 函数依赖可变状态,或者排序过程中修改了列表长度,会导致

ValueError: list modified during sort。key 函数必须是纯函数。

坑 3:混淆「稳定」与「有序」

稳定性说的是相等元素的相对次序,与元素本身是否有序无关。

只有「排序键相同但需要保留原顺序的其他字段」时,稳定性才有意义。

坑 4:快排固定取首元素作基准

在生产代码中直接写 pivot = a[lo] 是危险的:用户输入常常已经有序(如按时间导出的日志),

这会精确命中 最坏情况。必须随机化或三数取中。

坑 5:计数排序忘记处理负数和偏移

数组下标不能为负。必须先求 min,用 x - min 作为下标,回填时再加回 min。

若直接开 max + 1 大小的数组,负数会索引到列表末尾,静默出错。

坑 6:基数排序用了不稳定的一趟

若某一位的排序不稳定,之前低位建立好的次序就会被破坏,结果完全错误。

这就是为什么基数排序内部必须用计数排序这种稳定排序,而不能用快排。

坑 7:桶排序桶数设置不当

桶数太少 → 桶内元素太多,退化成 插入排序;

桶数太多 → 大量空桶,遍历开销与内存浪费。

经验值:桶数 ,且必须假设数据分布近似均匀。

坑 8:用比较排序给自定义对象排序却忘了实现比较

Python 中若对象没有 __lt__,sorted() 会抛 TypeError: '<' not supported between instances of ...。

解决:用 key= 提取可比较字段(推荐),或 functools.total_ordering / dataclass(order=True)。

坑 9:认为「快排总是最快的」

在 大量重复元素 的数据上,两路快排会把等于基准的元素分到同一侧,反复递归同一批相等元素,

退化为 (如全 0 数组)。必须用三路划分或随机化 + 双轴。

实测:100 万个相同元素,两路快排在部分实现下需要数十秒,三路快排 0.2 秒。

坑 10:大数组用递归实现导致栈溢出

归并排序和快排的递归深度是 (平均),但快排最坏是 。

的已排序输入会让朴素快排递归 层,直接 RecursionError。

缓解:随机化基准 + 优先递归较小的一半(保证栈深 )。

练习题

题 1(基础)判断稳定性

以下数组序列分别用冒泡、选择、插入、归并、快速、堆排序,判断结果是否稳定。请用 [(2,'a'), (1,'x'), (2,'b'), (1,'y')] 手工推演选择排序与归并排序。

<details>

<summary>参考答案</summary>

稳定:冒泡、插入、归并、计数、基数、桶(桶内插入排序)。

不稳定:选择、希尔、快速、堆。

选择排序推演 [(2,a), (1,x), (2,b), (1,y)]:

轮次最小值下标交换数组
11(值 1,'x')与下标 0 交换[(1,x), (2,a), (2,b), (1,y)]
23(值 1,'y')与下标 1 交换[(1,x), (1,y), (2,b), (2,a)]

结果中 (2,b) 跑到了 (2,a) 前面 → 不稳定。

归并排序推演:

  • 分成 [(2,a),(1,x)] 与 [(2,b),(1,y)]
  • 左半归并:1 < 2 取 (1,x);再取 (2,a) → [(1,x),(2,a)]
  • 右半归并:同理得 [(1,y),(2,b)]
  • 总归并:比较 (1,x) 与 (1,y),相等取左 → (1,x);再取 (1,y);然后比较 (2,a) 与 (2,b),相等取左 → (2,a),再 (2,b)
  • 结果 [(1,x),(1,y),(2,a),(2,b)] → 所有相等元素保序 → 稳定 ✅

</details>

题 2(基础)手算快排的一轮划分

对 [3, 8, 2, 5, 1, 4, 7, 6] 用 Lomuto 划分(末尾元素 6 作基准),写出每一步的数组状态与 i、j 的值。

<details>

<summary>参考答案</summary>

pivot = a[7] = 6,i = 0。

ja[j]a[j] <= 6?操作后数组i
03是[3,8,2,5,1,4,7,6](自己换自己)1
18否不变1
22是[3,2,8,5,1,4,7,6]2
35是[3,2,5,8,1,4,7,6]3
41是[3,2,5,1,8,4,7,6]4
54是[3,2,5,1,4,8,7,6]5
67否不变5
———交换 a[5] 与 a[7]—

最终 [3,2,5,1,4,6,7,8],基准 6 落在下标 5,左半 [3,2,5,1,4] 全部 ,右半 [7,8] 全部 。✅

</details>

题 3(中等)三路快排处理重复元素

数组 [2, 0, 2, 1, 1, 0](只有 0、1、2 三种值),手工推演三路快排的划分过程。

<details>

<summary>参考答案</summary>

取 pivot 为随机元素,假设取到 1。初始 lt = 0,i = 0,gt = 5。

步骤ia[i]比较操作数组ltgt
102> 1换 a[0],a[5],gt=4[0,0,2,1,1,2]04
200< 1换 a[0],a[0],lt=1,i=1[0,0,2,1,1,2]14
310< 1换 a[0],a[1],lt=2,i=2[0,0,2,1,1,2]24
422> 1换 a[2],a[4],gt=3[0,0,1,1,2,2]23
521== 1i=3不变23
631== 1i=4 > gt=3循环结束23

划分完成:[0,0] | [1,1] | [2,2]。相等区 [lt, gt] = [2,3] 已就位,不再递归,只需递归 <1 的 [0,1] 和 >1 的空区间。

结论:三路快排在 内处理完这种输入,而两路快排会递归 层。

</details>

题 4(中等)用归并排序统计逆序对

数组 [5, 4, 3, 2, 1] 有多少个逆序对?用归并过程逐步说明。

完整分步解答:

第 1 步:定义与手算。 逆序对是满足 且 的 数量。

对完全逆序的 5 元素数组,任意两个元素都构成逆序对:

第 2 步:递归分解。

                [5,4,3,2,1]
               /            \
          [5,4]              [3,2,1]
         /     \            /       \
      [5]     [4]        [3]      [2,1]
                                  /    \
                                [2]    [1]

第 3 步:自底向上归并并计数。

归并操作过程新增逆序对累计
[2] + [1]2 > 1,取出 1,左半剩 1 个元素+11
[3] + [1,2]3>1 取 1(+1);3>2 取 2(+1);取 3+23
[5] + [4]5 > 4,取出 4,左半剩 1 个+14
[4,5] + [1,2,3]见下表+610

最后一轮归并 left=[4,5]、right=[1,2,3] 的详细过程:

比较取值左半剩余元素数新增逆序对
4 > 1取 12(是 4、5)+2
4 > 2取 22+2
4 > 3取 32+2
右半空取 4、5—0

合计 。

第 4 步:验证。

与手算的 一致。

第 5 步:复杂度。 归并排序 ,计数只是在合并时加一行 cnt += mid - i,不增加渐进复杂度。空间 。

代码见上文「应用 5:数逆序对」。

</details>

题 5(进阶)外部排序

内存只有 1 GB,要排序 100 GB 的文件。设计一个方案。

<details>

<summary>参考答案</summary>

核心思路:分块排序 + 多路归并(external merge sort)。

阶段步骤
① 分块把 100 GB 文件顺序读入,每次填满约 800 MB 内存(留余量),用一个 chunk
② 块内排序对每个 chunk 用 Timsort(充分利用内存内的 排序)
③ 写回把排好序的 chunk 写到磁盘,得到约 125 个有序临时文件
④ 多路归并用大小为 的最小堆同时归并 个文件( 受文件句柄限制,通常 16~64),每轮把 路合并成 1 路,重复 轮
⑤ 清理删除临时文件

复杂度:读文件 2 遍(1 遍读 + 1 遍归并写),I/O 是瓶颈,时间复杂度 ,其中 是数据量、 是内存、 是块大小。

关键细节:

  • 块内用稳定排序,多路归并用「相等时优先取编号小的流」也能保持稳定;
  • 用置换选择(replacement selection)可以把平均块长从 提高到 ,减少归并轮数;
  • 数据库的 ORDER BY 在内存不足时正是这么做的(MySQL 的 filesort + merge)。

</details>

题 6(进阶)实现带稳定性保证的 LSD 基数排序

给定一组长度为 3 的字符串(只含小写字母),按字典序排序,不使用比较排序。

<details>

<summary>参考答案</summary>

字符可以直接映射为数字:ord(c) - ord('a'),值域 ,位数 。

必须从最后一位(最低位)开始,即第 3 位 → 第 2 位 → 第 1 位(LSD),每轮用稳定的计数排序。

def radix_sort_fixed_strings(words, length=3, alphabet=26):
    """按字典序排序等长小写字母字符串,O(d * (n + alphabet))。"""
    a = words[:]
    for pos in range(length - 1, -1, -1):        # 从最低位到最高位
        count = [0] * alphabet
        for w in a:
            count[ord(w[pos]) - 97] += 1
        for i in range(1, alphabet):
            count[i] += count[i - 1]
        out = [""] * len(a)
        for w in reversed(a):                    # 逆序回填保证稳定
            d = ord(w[pos]) - 97
            count[d] -= 1
            out[count[d]] = w
        a = out
    return a


if __name__ == "__main__":
    print(radix_sort_fixed_strings(["bca", "abc", "aaa", "baa", "aab"]))
    # ['aaa', 'aab', 'abc', 'baa', 'bca']

为什么必须先低位后高位? 因为低位排序会被后续的高位排序覆盖。

LSD 从低位开始,每一轮都是稳定排序,高位相同时低位建立的次序得以保留,最终结果就是完整字典序。

反之(MSD 从高位开始)需要递归分组,实现更复杂,但适合变长字符串与流式场景。

</details>

常见问题 FAQ

Q1:为什么 Python 的 sorted() 比我自己写的快排快得多?

四个原因:① Timsort 利用数据已有的有序段(真实数据常常部分有序),最好情况 ;

② C 实现 vs Python 字节码,每次比较的开销差几十倍;

③ key 函数只对每个元素计算一次(Schwartzian transform),而手写 cmp_to_key 每次比较都要调 Python 函数;

④ 深度工程优化(galloping、内存预分配、避免边界检查)。

结论:生产代码永远用标准库排序。

Q2:为什么归并排序空间是 ,快排是 ,但大家还嫌快排「费内存」?

这是一种误传。快排的额外数组空间确实是 ,但递归栈要 。

相比之下堆排序是真正的 空间(迭代实现,无递归)。

更准确的说法是:归并要额外的 堆内存(大数组时可能是几百 MB),而快排的 栈可以忽略。

在内存受限场景(嵌入式、GPU),堆排序才是首选。

Q3:既然有 的计数排序,为什么还要用 的快排?

因为计数排序的 里 是值域,不是数据量。三个限制:

① 只支持整数(或能映射为紧凑整数);

② 必须与 同阶,否则 会爆炸(n=100, 值域=10^9 时需要 4 GB 计数数组);

③ 额外 空间。

比较排序对任意可比较类型都适用,不依赖值的分布,泛用性强得多。

Q4:为什么 std::sort 是不稳定的,而 std::stable_sort 存在?我该用哪个?

因为稳定性有代价(需要 额外空间或额外的指针操作)。C++ 把选择权交给用户:

- std::sort:Introsort,不稳定,但更快、内存更省( 栈)

- std::stable_sort:归并类,稳定,但需要 额外空间

选择原则:只有当「排序键相等但元素的相对次序有意义」时才需要 stable_sort。

如果排序键是元素的全部可比信息,用 std::sort 就够了。

Q5:面试里常说的「手写快排」应该写成什么样?

建议准备随机化基准 + Lomuto 划分的版本(最易写对),并能口头说明:

① 为什么需要随机化(避免有序输入退化);

② 最坏 的触发条件与递推式;

③ 为什么不稳定(远距离交换);

④ 小区间切换插入排序的优化();

⑤ 三路划分如何解决重复元素问题。

如果面试官追问,能写出 Hoare 划分(交换次数更少)会加分。

Q6:如何排序一个 10 GB 的日志文件,机器只有 16 GB 内存?

先估算: 约 行,每行 100 字节。若能在内存里装下(16 GB > 10 GB),

直接用 sorted(),但要注意 Python 对象的开销——一个 100 字节的字符串在 CPython 里约占 150 字节(含头部),

加上 list 指针,10 GB 文本对应约 20~25 GB 内存,装不下。

所以要么用外部排序(见题 5),要么改用 numpy / pandas 的定长 dtype,

要么用 Unix 工具链:sort -S 8G --parallel=4 bigfile.log > sorted.log(GNU sort 自带外部排序)。

相关笔记

  • 算法-复杂度分析:本篇所有 记号、递推式与 下界的理论基础
  • 数据结构-树与堆:堆排序与 Top-K 依赖的完全二叉树与优先队列
  • 算法-查找与分治:分治思想、二分查找与快速选择的进一步展开
  • 算法-动态规划与贪心:Kruskal 等贪心算法以排序作为第一步
  • 数据结构-线性结构:数组与链表是排序算法的底层容器
  • Python-02-内置数据结构:Python 列表排序 API 与内置容器的配合
  • 00-索引:全库笔记导航
  • 学习路线图:按阶段的学习顺序建议

参考来源

  • OI Wiki 排序基础:https://oi-wiki.org/basic/sort/
  • OI Wiki 基数排序:https://oi-wiki.org/basic/radix-sort/
  • Python 官方文档 sorted:https://docs.python.org/3/library/functions.html#sorted
  • Python 官方文档 Sorting HOW TO(含 key 与稳定性说明):https://docs.python.org/3/howto/sorting.html
  • Python 官方文档 functools.cmp_to_key:https://docs.python.org/3/library/functools.html#functools.cmp_to_key
  • CPython 源码 listsort.txt(Timsort 设计文档,Tim Peters 著):https://github.com/python/cpython/blob/main/Objects/listsort.txt
  • VisuAlgo 排序可视化:https://visualgo.net/en/sorting
  • MIT OCW 6.006 Introduction to Algorithms:https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
  • MDN Array.prototype.sort:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
  • cppreference std::sort:https://en.cppreference.com/w/cpp/algorithm/sort
  • Java Arrays.sort 文档:https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D)
  • C# Array.Sort 文档:https://learn.microsoft.com/en-us/dotnet/api/system.array.sort