9.1 初级排序：冒泡、选择、插入

第 9 章 · 基础排序｜前置：数组、循环与函数｜下一篇：希尔与归并。本页用同一接口比较冒泡、选择与插入排序，重点观察移动方式、逆序对和稳定性。

三种不同的移动方式

三种办法都很朴素：

• 冒泡排序比较相邻元素，让较大的编号像气泡一样向右浮。
• 选择排序每轮找出键最小的元素，放到待排序区最前面。
• 插入排序像整理扑克牌，把新牌插进左侧已经排好的牌组。

它们的最坏时间都是 Θ(n²)，但工作方式不同。先看过程，再背表格。

统一代码合同

下面三个函数都接受任意 iterable，返回新列表，不修改输入。key 对每个元素只计算一次：先把每项装饰为 [排序键, 原位置, 原值]，排序过程只移动记录，最后取回原值。比较只读取排序键，原位置并不参与平局处理，因此它不会自动让选择排序稳定。输入迭代器会被消耗，原对象只复制引用。键必须能一致地比较，且不含 NaN 等无序值；以下复杂度把求 key 和比较视为常数成本。

包装层同时需要 Θ(n) 装饰记录作为辅助空间，以及 Θ(n) 返回列表作为输出空间。后文表格中的“算法辅助空间”只计算排序核心：若直接在调用者列表上运行，三个核心都可做到 O(1) 额外空间。

def _decorate(values, key):
    key_function = (lambda item: item) if key is None else key
    return [
        [key_function(item), index, item]
        for index, item in enumerate(values)
    ]

def _values(records):
    return [record[2] for record in records]

def selection_sort(values, key=None):
    """返回选择排序结果；标准跨位交换版本不稳定。"""
    records = _decorate(values, key)
    n = len(records)
    for left in range(n - 1):
        minimum = left
        for candidate in range(left + 1, n):
            if records[candidate][0] < records[minimum][0]:
                minimum = candidate
        if minimum != left:
            records[left], records[minimum] = records[minimum], records[left]
    return _values(records)

def bubble_sort(values, key=None):
    """返回带提前终止的稳定冒泡排序结果。"""
    records = _decorate(values, key)
    n = len(records)
    for end in range(n - 1, 0, -1):
        swapped = False
        for index in range(end):
            if records[index][0] > records[index + 1][0]:
                records[index], records[index + 1] = (
                    records[index + 1],
                    records[index],
                )
                swapped = True
        if not swapped:
            break
    return _values(records)

def insertion_sort(values, key=None):
    """返回稳定插入排序结果。"""
    records = _decorate(values, key)
    for index in range(1, len(records)):
        current = records[index]
        hole = index
        while hole > 0 and records[hole - 1][0] > current[0]:
            records[hole] = records[hole - 1]
            hole -= 1
        records[hole] = current
    return _values(records)

if __name__ == "__main__":
    data = [5, 3, 8, 1]
    print("selection:", selection_sort(data))
    print("bubble:   ", bubble_sort(data))
    print("insertion:", insertion_sort(data))
    print("original: ", data)

运行：

selection: [1, 3, 5, 8]
bubble:    [1, 3, 5, 8]
insertion: [1, 3, 5, 8]
original:  [5, 3, 8, 1]

冒泡排序：相邻交换

对 [5, 3, 8, 1] 做第一轮：

[5, 3, 8, 1]  比较 5 与 3，交换
[3, 5, 8, 1]  比较 5 与 8，不动
[3, 5, 8, 1]  比较 8 与 1，交换
[3, 5, 1, 8]  本轮结束，8 已到最终位置

下一轮只需扫描到倒数第二位，因为右端的 8 不再参与。若某一整轮没有交换，swapped 仍为 False，输入已经有序，可以结束。

复杂度：

• 已有序输入只检查一轮，时间 Θ(n)。
• 逆序输入需要 Θ(n²) 次比较与 Θ(n²) 次交换。
• 核心算法辅助空间 O(1)。
• 代码只在左键严格大于右键时交换；相等记录保持先后次序，因此稳定。

“冒泡总是最慢”不是可移植的复杂度结论。具体时间受实现和输入影响。更稳妥的判断是：它在逆序数据上进行大量相邻交换，没有已知理由时，业务代码宜从标准库排序开始。

选择排序：扫描多，交换少

手推 [29, 10, 14, 37, 13]：

初始     [29, 10, 14, 37, 13]
第 1 轮  最小 10，与 29 交换 -> [10, 29, 14, 37, 13]
第 2 轮  最小 13，与 29 交换 -> [10, 13, 14, 37, 29]
第 3 轮  14 已在当前位置    -> [10, 13, 14, 37, 29]
第 4 轮  最小 29，与 37 交换 -> [10, 13, 14, 29, 37]

不论输入是否已有序，它都会检查

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

对元素比较。因此最好、平均、最坏都是 Θ(n²)。每轮最多做一次外层交换，总数不超过 n - 1。

标准选择排序不稳定。给记录加上标签：

输入：[(2, "a"), (2, "b"), (1, "x")]
第一轮把 (1, "x") 与 (2, "a") 交换
结果：[(1, "x"), (2, "b"), (2, "a")]

两个键为 2 的记录次序反了。稳定性讨论必须保留记录身份；只看 [2, 2, 1] 看不出这个变化。

插入排序：移动逆序项

整理 [12, 11, 13, 5, 6]：

取 11  [11, 12, 13, 5, 6]
取 13  [11, 12, 13, 5, 6]
取 5   [5, 11, 12, 13, 6]
取 6   [5, 6, 11, 12, 13]

左侧始终是已排序区。取出 current 后，程序把更大的记录向右移，空出的洞最终由 current 填上。相等键不会右移，所以算法稳定。

插入排序的工作量与逆序对数量 I 紧密相关。逆序对是一对位置 i < j，却满足 a[i] > a[j] 的元素：

• 已有序数组 I = 0，时间 Θ(n)。
• 互异键严格逆序时 I = n(n-1)/2，时间 Θ(n²)。
• 向右移动旧记录的次数恰好是 I；加上每轮的取出、放回与停止检查，总工作为 Θ(n+I)。

这也解释了插入排序为何常用于小数组或已有顺序的短 run：移动距离短，控制流程也简单。别把这句话扩展成“任意近似有序数据都该手写插入排序”；业务代码通常先调用语言的标准排序。

稳定性在真实记录上有什么用

假设名单先按学号排好，再按分数排序：

[(88, "S01"), (95, "S02"), (88, "S03")]

稳定排序按分数得到：

[(88, "S01"), (88, "S03"), (95, "S02")]

两名 88 分学生仍按原学号顺序出现。Python 文档保证 list.sort() 与 sorted() 稳定，也说明可以利用稳定性做多级排序：Python Sorting HOWTO。

专业速查

算法	最好	平均	最坏	算法辅助空间	稳定	输入特征
冒泡（提前终止）	Θ(n)	Θ(n²)	Θ(n²)	O(1)	是	教学、检测已有序
选择	Θ(n²)	Θ(n²)	Θ(n²)	O(1)	否	比较多，外层交换至多 n-1 次
插入	Θ(n)	Θ(n²)	Θ(n²)	O(1)	是	小规模、逆序对少

“平均”假定互异键的排列等概率出现；大量重复键或特定输入分布可能改变平均成本。表中的空间只指排序核心，本页包装还使用 Θ(n) 辅助记录和 Θ(n) 输出列表。空输入返回新空列表，成本为常数。Princeton 的基础排序资料给出了插入、选择与 Shell 的推导和练习：Elementary Sorts。

练习顺序

1. 用纸手推三个示例，圈出每次比较的两个位置。
2. 给数据加标签，验证稳定与不稳定。
3. 把 > 改成 >=，观察冒泡和插入为何失去稳定性。
4. 统计插入排序的移动次数，并与逆序对数量核对。

比较移动方式与稳定性

冒泡通过相邻交换把较大元素推向右端；选择每轮扫描剩余区，只做至多一次外层交换；插入则利用左侧已有顺序，移动量和逆序对数量直接相关。稳定性必须放在带身份的记录上检查，只看重复数字看不出先后是否颠倒。

下一篇让元素走得更远，进入 希尔排序与归并排序。