算法通关训练营 · 排序篇（从 O(n²) 到 O(n log n) 的跃迁）

课程简介

这是必学必会「算法」科目的排序专题课，对应缺口体系 B 系列（排序与选择）。从最朴素的插入、选择、冒泡三种平方级排序讲起，带你亲手写下每一行代码、用循环不变量证明正确性，再一路跃迁到归并、堆、快排等 O(n log n) 经典算法，最后理解比较排序下界与现代标准库为何采用混合排序。每一节都配知识单元 + 实战题。

学习目标

能手写并证明三种 O(n²) 排序的正确性
理解"稳定性""原地性""逆序对"等核心概念及其工程含义
掌握分治排序（归并）与堆结构（堆排序）如何将复杂度压到 O(n log n)
说清快速排序的平均/最坏表现，以及现代混合排序的设计动机

章节概览

第1节插入/选择/冒泡排序（本节，缺口 B1）
第2节归并排序 Merge Sort（缺口 B2）
第3节堆与堆排序 Heap Sort（缺口 B4）
第4节快速排序 Quick Sort（缺口 B3）
第5节线性时间排序与比较下界（缺口 B5 / B7）
第6节中位数、选择与现代混合排序（缺口 B6 / 工程综合）

---

图：算法通关训练营·排序篇的章节递进路线

参考代码（Python）

本章核心三种排序的完整可运行实现，建议对照正文在本地跑一遍、打印每趟中间结果：

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = key
    return a

def selection_sort(a):
    n = len(a)
    for i in range(n):
        m = min(range(i, n), key=lambda k: a[k])
        a[i], a[m] = a[m], a[i]
    return a

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        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 这里用内置 min 示意"找最小"，工程实现应手写扫描以保证是纯 O(n²) 原地版。