从算法到人工智能 · 第 8 课：排序与选择——从冒泡到快排，再到快速选择

排序，可能是你这一辈子写得最多的算法。给它排个序、给排行榜排个名、把数据从小到大理一理——无处不在。

但排序真正的价值，不是"把数字排整齐"这么简单，而是它教会我们"快"到底是怎么炼成的：同样是排序，笨办法 O(n²)，聪明办法 O(n log n)，数据一大，一个要等一天，一个一秒完事。这一课，我们从最笨的冒泡讲起，一路升级到快排，亲手摸一遍"快"的门道。

一、先立个靶子：排序到底在解决什么

排序 = 把一堆乱序的数，按从小到大（或从大到小）排好。

nums = [5, 2, 8, 1, 9, 3]
# 目标：变成 [1, 2, 3, 5, 8, 9]

看起来简单，但排序的难处在于：你没法"一眼看穿"全局顺序，只能一步步比较、交换，慢慢逼近有序。 不同算法，就是不同的"逼近策略"，策略不同，速度天差地别。

一个贯穿全程的问题："我们最少要比多少次，才能确定顺序？" 这个问题的答案——O(n log n)——是排序算法的天花板，后面我们会讲到为什么。

二、笨办法三兄弟：冒泡、选择、插入

这三个都是 O(n²)，思路朴素，适合当入门垫脚石，也适合小数据量。

1. 冒泡排序：相邻俩俩换，大的"冒"上去

思路：一遍遍扫，相邻两个比一比，谁大谁往后换。每扫一遍，最大的那个就像气泡一样"冒"到最后。

def bubble_sort(nums):
    n = len(nums)
    for i in range(n):               # 一共扫 n 遍
        swapped = False
        for j in range(n - 1 - i):   # 每次少比一个（最后已有序）
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:              # 这一遍没交换，说明已有序
            break
    return nums

print(bubble_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

2. 选择排序：每次挑最小的，放到最前面

思路：从头到尾找最小的，放到第 0 位；再找次小的，放到第 1 位……一步步"选出"正确位置的人。

def selection_sort(nums):
    n = len(nums)
    for i in range(n):
        min_idx = i                 # 假设 i 位是最小的
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j         # 找到更小的，记下来
        nums[i], nums[min_idx] = nums[min_idx], nums[i]   # 换到前面
    return nums

print(selection_sort([5, 2, 8, 1, 9, 3]))

3. 插入排序：像打牌一样，一张张插进手里

思路：想象你在理扑克牌——每次拿起一张新牌，插进手里已经排好的那部分正确位置。

def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]               # 手上这张新牌
        j = i - 1
        while j >= 0 and nums[j] > key:   # 前面比它大的，往后挪
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key           # 插到正确位置
    return nums

print(insertion_sort([5, 2, 8, 1, 9, 3]))

三兄弟的共同点：都是两层循环，最坏 O(n²)。其中插入排序有个隐藏优点——数据基本有序时几乎 O(n)，所以它常常被用在"快排递归到底层、数据已经差不多排好"的时候收尾。

三、一个重要的概念：稳定性

先记一个面试常问的词——稳定性（stable）。

如果两个相等的元素，排序前后相对顺序不变，这个排序就是稳定的。

举个例子：你有一组学生，先按成绩排了序，现在想按"班级"再排一次，且希望同班级内仍按成绩高低排列。这时你就需要稳定的排序——第二次排序不会打乱第一次已排好的相对顺序。

算法	稳定？
冒泡	✅ 稳定
插入	✅ 稳定
选择	❌ 不稳定
归并	✅ 稳定
快排	❌ 不稳定

记住：需要"多次排序、层层细化"的场景（比如先按 A 排再按 B 排，且要保留 A 的顺序），选稳定的排序。

四、聪明办法：归并排序（分治的第一次亮相）

笨办法慢，是因为它们都在"原地慢慢挪"。聪明办法换了个思路——分治（后面会专门讲）：把大问题拆成小问题，解决小问题，再合并。

归并排序三步：

分：把数组从中间切成两半。
治：分别对两半排序（递归调用自己）。
合：把两个已经排好的半段，合并成一个有序数组。

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])    # 递归排左半
    right = merge_sort(nums[mid:])   # 递归排右半
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result += a[i:]      # 把剩下的接上
    result += b[j:]
    return result

print(merge_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

复杂度怎么算：每层递归，所有元素都被"合并"一次，是 O(n)。一共会切出 log n 层（每次砍半）。所以 O(n log n)。这就是从 O(n²) 到 O(n log n) 的第一次跨越。

代价：归并需要额外的空间来装合并结果，是 O(n) 的辅助空间——"用空间换时间"的典型。

五、聪明办法的巅峰：快速排序

快排，业界公认"平均最快"的排序，Python 的 sort() 和很多语言底层都在用它（或其变体）。

快排的核心思想还是分治，但换了个切法——选一个"基准"（pivot），把比它小的放左边，比它大的放右边，然后左右各自递归。

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]        # 选中间那个当基准
    left  = [x for x in nums if x < pivot]
    mid   = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

print(quick_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

这段代码清晰得感人，但它是"用额外数组"的简化版。真正的工程实现是原地分区（省内存）。原地分区的核心就一段：把比基准小的往左边赶。

复杂度：平均 O(n log n)——每次基准把数组砍成两半，砍 log n 层，每层 O(n)。

但快排有个著名的坑：如果每次选的基准都"倒霉"到是最大或最小，数组就只被切成"1 个 + 剩下的 n-1 个"，退化成了 O(n²)。所以工程上会用"三数取中""随机基准"来躲开这个坑。

六、为什么排序的"下界"是 O(n log n)？

这是排序里最有意思的一问：能不能发明一个 O(n) 的排序？

答案：基于"比较"的排序，做不到比 O(n log n) 更快。

直觉是这样：排序的本质，是把 n 个元素所有可能的排列（一共 n! 种）确定成一种。每比一次，你最多排除一半的可能（就像猜数字"大了还是小了"）。所以要确定到底哪一种，至少要比 log₂(n!) 次。

而数学上有条斯特林公式告诉你：log₂(n!) ≈ n log n。

所以 O(n log n) 是"比较排序"的理论下限，不是我们不够聪明，是天花板就在这。快排、归并、堆排序都已经摸到这个天花板了。

那有没有 O(n) 的排序？有——但它们是"不比较"的，比如计数排序、桶排序，靠"数一数每个值出现几次"来排。它们快，但对数据有要求（值域不能太大）。Python 处理"全是小整数"时可以用 sorted 或特定场景用计数排序。

七、复杂度与特性一览

算法	平均	最坏	空间	稳定
冒泡	O(n²)	O(n²)	O(1)	✅
选择	O(n²)	O(n²)	O(1)	❌
插入	O(n²)	O(n²)	O(1)	✅
归并	O(n log n)	O(n log n)	O(n)	✅
快排	O(n log n)	O(n²)	O(log n)	❌

选型口诀：小数据、要稳定、图省事 → 插入/冒泡；要稳定、不怕费点内存 → 归并；要最快、平均性能最好 → 快排。

八、突破下界：非比较排序 + 快速选择

上一节说排序下界是 O(n log n)，但那是"靠两两比较"才有的限制。如果不比较，而是利用数据本身的特性，能更快。

1. 计数排序：数一数有几个

前提：数据是有限范围内的整数。思路简单到不像算法——数每个值出现了几次，再按次数"铺"出来：

def counting_sort(a):
    m = max(a)
    count = [0] * (m + 1)
    for x in a:
        count[x] += 1
    out = []
    for v in range(m + 1):
        out += [v] * count[v]   # 值 v 出现几次就铺几次
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))   # [1, 2, 2, 3, 3, 4, 8]

复杂度 O(n + m)，m 是值域大小。值域不大时（分数 0~100、年龄 0~150），它碾压所有比较排序。

2. 桶排序 / 基数排序

桶排序：把数据分到几个"桶"里，桶内再排序。数据分布均匀时接近 O(n)。
基数排序：按"位数"从低位到高位，每一轮用稳定的计数排序排一遍。排整数、日期、IP 都很高效，O(d·n)，d 是位数。

它们和计数排序一样，都不靠两两比较，所以绕开了 O(n log n) 的下界。

3. 快速选择：不用全排，也能找"第 k 小"

如果只是想找"第 k 小的数"，根本不用把整个数组排完——快排的分区思想就够了：每次选一个基准，比它小的放左边、大的放右边，然后只往目标那一边继续找。

def quickselect(a, k):          # 找第 k 小（k 从 0 数）
    if len(a) == 1:
        return a[0]
    p = a[0]
    lo = [x for x in a if x < p]
    eq = [x for x in a if x == p]
    hi = [x for x in a if x > p]
    if k < len(lo):
        return quickselect(lo, k)              # 在左边找
    if k < len(lo) + len(eq):
        return p                                # 正好是基准
    return quickselect(hi, k - len(lo) - len(eq))

a = [5, 1, 8, 3, 9, 2, 7]
print(quickselect(a, 2))   # 3（排序后 [1,2,3,5,7,8,9] 的第 3 小）

平均 O(n)，比"先全排再取"（O(n log n)）快。这是"topK 问题"的标准答案之一，后面讲堆时我们还会用堆再解一次。

记住：比较排序被 O(n log n) 卡死，但利用数据特性（范围小、是整数、只需第 k 小），就能更快——这就是"针对问题特点设计算法"的力量。

九、动手时间 🎯

实验 1：亲眼看看 O(n²) 和 O(n log n) 差多少

import time, random

n = 5000
nums = [random.randint(0, 100000) for _ in range(n)]

# 冒泡（O(n²)）
arr = nums[:]
start = time.time()
bubble_sort(arr)
print("冒泡耗时:", round(time.time() - start, 3), "秒")

# 快排（O(n log n)）
arr = nums[:]
start = time.time()
quick_sort(arr)
print("快排耗时:", round(time.time() - start, 3), "秒")

# Python 内置（C 实现的 Timsort，也是 O(n log n)）
arr = nums[:]
start = time.time()
arr.sort()
print("内置 sort 耗时:", round(time.time() - start, 3), "秒")

你会看到：冒泡要等好几秒，快排和内置 sort 几乎瞬间。这就是 O(n²) 和 O(n log n) 的天壤之别。

实验 2：把 n 翻倍，观察时间怎么涨

把 n = 5000 改成 n = 10000 再跑：

冒泡时间大概翻 4 倍（O(n²)）
快排时间大概翻 2 倍多一点（O(n log n)）

实验 3：验证稳定性

# 元组：(班级, 成绩)。先按成绩排，再按班级排（稳定排序应保留成绩顺序）
students = [(2, 90), (1, 85), (2, 75), (1, 95)]
# 先按成绩（第二个元素）排
by_score = sorted(students, key=lambda x: x[1], reverse=True)
print("按成绩排:", by_score)
# 再按班级（第一个元素）稳定排
by_class = sorted(by_score, key=lambda x: x[0])
print("按班级稳定排:", by_class)   # 同班级内，成绩高的仍在前

sorted 和 list.sort() 都是稳定的，放心用。

实验 4（挑战）：不用 sorted，手写"找出第 k 小的数"

思路：借用快排的"分区"思想，不用全排完，只要定位到第 k 小就停。

def kth_smallest(nums, k):
    if len(nums) == 1:
        return nums[0]
    pivot = nums[len(nums) // 2]
    left = [x for x in nums if x < pivot]
    mid = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    if k < len(left):
        return kth_smallest(left, k)
    elif k < len(left) + len(mid):
        return pivot
    else:
        return kth_smallest(right, k - len(left) - len(mid))

print(kth_smallest([5, 2, 8, 1, 9, 3], 2))   # 第 2 小（下标2）= 3

思考：这个办法为什么平均只需 O(n)，比"全排序再取第 k 个"（O(n log n)）更快？

十、小结

排序是"逼近有序"的策略游戏——冒泡/选择/插入是 O(n²) 的笨办法，归并/快排靠"分治"把复杂度砍到 O(n log n)。
比较排序的理论下限是 O(n log n)——因为要确定 n! 种排列，至少比 log₂(n!) ≈ n log n 次，这是天花板不是我们的无能。
选排序看场景——要稳定选归并/插入，要平均最快选快排，数据基本有序时插入排序近乎 O(n)。

先别急着往后翻，把这四个实验敲熟，"排序快慢"的手感就长在你脑子里了。