一、选择排序：每轮挑最小

思路（升序）：第 i 轮从【第 i 个到末尾】里挑最小的，跟第 i 个交换——前半段永远是【已理好的最小前缀】。

[5, 3, 8, 1, 9, 2]
第1轮：全堆里最小是 1 -> 和 5 换  [1, 3, 8, 5, 9, 2]
第2轮：剩下里最小是 2 -> 和 3 换  [1, 2, 8, 5, 9, 3]
……直到只剩一个

a = [5, 3, 8, 1, 9, 2]
for i in range(len(a) - 1):
    m = i                          # 先假设当前位置最小
    for j in range(i + 1, len(a)):
        if a[j] < a[m]:
            m = j                  # 记下更小的下标（只记不换）
    a[i], a[m] = a[m], a[i]        # 一轮只换一次
print(a)                           # [1, 2, 3, 5, 8, 9]

性格：交换次数最少（每轮最多一次）；比较次数固定 n(n-1)/2 次——数据多乱都这个量（O(n²)）。

二、插入排序：理扑克牌

思路：左边的手牌已经理好；每次从右边抓一张新牌，从后往前比、插进该插的位置。

b = [5, 3, 8, 1, 9, 2]
for i in range(1, len(b)):
    key = b[i]                     # 抓起的新牌
    j = i - 1
    while j >= 0 and b[j] > key:   # 左边比它大的都往后挪
        b[j + 1] = b[j]
        j -= 1
    b[j + 1] = key                 # 插进空出的坑
print(b)                           # [1, 2, 3, 5, 8, 9]

性格：最坏 O(n²)，但对【基本有序】的数据接近 O(n)（几乎不用挪）——这是它至今活着的理由：Timsort（Python 的 sorted 内置算法）就用插入排序处理小段与近有序段（4-13 展开）。

三、两者对比一张表

四、动手 Demo：同一副牌两种理法

def selection_sort(arr):
    a = arr.copy()
    for i in range(len(a) - 1):
        m = i
        for j in range(i + 1, len(a)):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

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

data = [5, 3, 8, 1, 9, 2]
print(selection_sort(data))    # [1, 2, 3, 5, 8, 9]
print(insertion_sort(data))    # [1, 2, 3, 5, 8, 9]
print(data)                    # [5, 3, 8, 1, 9, 2] —— 原数据没动（copy 的功劳）

看到什么算成功：两行 [1, 2, 3, 5, 8, 9] ＋ 原始乱序一行。

读结果：结果相同、路径不同——选择排序的 1 是【被挑出来换到】第一位，插入排序的 1 是【抓起后插到】第一位。算法＝目标相同、路径不同的过程，这正是比较排序思想的入口。

五、30 秒实验

拿一副真实扑克（或写下的十个数）手动理牌：你下意识用的就是插入排序（左边手牌保持有序、抓一张插一张）——30 秒亲手做一遍，比背十遍代码记得牢。

六、常见误区

1. 【O(n²) 的排序没用，直接学快排】——错。插入排序在【小规模】与【基本有序】时比快排还快（无递归开销、常数小）；Timsort 内部就用它。没有慢算法，只有用错场景的算法。
2. 【选择排序和冒泡是一回事】——错。冒泡靠【相邻交换】把大的顶到后面（交换频繁）；选择是【记录下标、每轮一次交换】——下一节专门对比。
3. 【排序函数会改原数组，无所谓】——有所谓。Python 的 list.sort() 原地改、sorted() 返回新表—— Demo 里先 copy 再排就是为了不动原数据；实际项目里改不改原数据是接口设计的一部分。

• ☐ 下一节（4-12 冒泡排序、摇晃排序）

相关笔记

• 冒泡与摇晃排序 —— 同为 O(n²) 的邻居
• 时间复杂度与大 O —— n(n-1)/2 为什么读作 O(n²)
• 数组 —— 排序的主战场
• ⌨️ 编程原理 · 索引 —— 全课路线图