排序算法速记手册 —— 面试手写代码必备-极简笔记

排序算法速记手册 —— 面试手写代码必备

本教程覆盖 8 种经典排序算法，每种算法提供：核心思想、手写模板代码（Python）、复杂度分析、记忆口诀，以及常见面试陷阱。建议按顺序阅读，最后用"总览对照表"做复习。

一、总览对照表（先背这张表）

算法	平均时间	最坏时间	最好时间	空间	稳定性	一句话记忆
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定	大的往后冒泡
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	每次选最小放前面
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定	像整理扑克牌
希尔排序	O(n^1.3)	O(n²)	O(n)	O(1)	不稳定	分组插入排序
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	分治 + 合并
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定	选基准 + 分区
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	建堆 + 取堆顶
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定	数每个值出现几次

稳定性的记忆口诀：“快选堆希不稳定”（快速、选择、堆、希尔），其余稳定。

二、基础排序（O(n²) 级别）

2.1 冒泡排序（Bubble Sort）

核心思想：每一轮从头到尾两两比较，把当前最大值"冒泡"到末尾。如果某一轮没有发生任何交换，说明数组已有序，可以提前退出。

记忆画面：想象一锅水烧开，气泡一个个从底部浮到水面——每轮最大的元素像气泡一样浮到末尾。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # 优化：本轮无交换则提前退出
        for j in range(n - 1 - i):  # 每轮结束，末尾 i 个已就位
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

手写要点：

内层循环上界是 n - 1 - i，不是 n - 1，因为末尾 i 个元素已经排好
swapped 标志位是面试加分项，别忘了写
最好情况（已排序）只需 O(n)

复杂度：平均 O(n²)，最坏 O(n²)，最好 O(n)，空间 O(1)，稳定

2.2 选择排序（Selection Sort）

核心思想：每次从未排序部分中找到最小值，放到已排序部分的末尾。

记忆画面：你站在一排书前面，每次从中挑出最矮的一本，按顺序摆在左边。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i  # 假定当前位置是最小值
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 一轮只交换一次
    return arr

手写要点：

每轮只交换一次（和冒泡不同！）
记录 min_idx 而不是值本身
无论数组是否有序，都必须遍历完，所以最好情况也是 O(n²)
不稳定：交换可能跳过相等元素（如 [5, 5, 2]，第一轮两个5的相对顺序被打破）

复杂度：平均 O(n²)，最坏 O(n²)，最好 O(n²)，空间 O(1)，不稳定

2.3 插入排序（Insertion Sort）

核心思想：从第二个元素开始，依次把当前元素"插入"到前面已排序部分的正确位置。

记忆画面：打扑克牌时，每摸一张新牌，从左到右找到合适的位置插进去。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]      # 当前要插入的牌
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 比 key 大的元素右移
            j -= 1
        arr[j + 1] = key  # 找到位置，插入
    return arr

手写要点：

先把 arr[i] 存到 key，然后用 while 循环后移元素（不是交换！）
while 条件有两个：j >= 0 和 arr[j] > key，缺一不可
插入位置是 j + 1（循环退出时 j 指向最后一个 ≥ key 的元素的前一个）
对于近乎有序的数组非常高效，接近 O(n)

复杂度：平均 O(n²)，最坏 O(n²)，最好 O(n)，空间 O(1)，稳定

三、进阶排序（O(n log n) 级别）

3.1 归并排序（Merge Sort）

核心思想：分治法。把数组不断对半拆分，直到每个子数组只有一个元素（天然有序），然后两两合并成有序数组。

记忆口诀：“先拆后合，一分为二，合二为一”。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 1. 拆分
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 2. 合并两个有序数组
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= 保证稳定性
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 把剩余部分接上
    result.extend(left[i:])
    result.extend(right[j:])
    return result

面试常考变体：原地归并（不使用额外数组）

面试中可能会要求在原数组上操作。核心思路是用索引代替切片：

def merge_sort_inplace(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left >= right:
        return
    mid = (left + right) // 2
    merge_sort_inplace(arr, left, mid)
    merge_sort_inplace(arr, mid + 1, right)
    merge_inplace(arr, left, mid, right)

def merge_inplace(arr, left, mid, right):
    temp = arr[left:right + 1]  # 拷贝当前段
    i, j, k = 0, mid - left + 1, left
    while i <= mid - left and j <= right - left:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            i += 1
        else:
            arr[k] = temp[j]
            j += 1
        k += 1
    while i <= mid - left:
        arr[k] = temp[i]
        i += 1
        k += 1

手写要点：

<= 而非 < 是保证稳定性的关键
extend 或手动拷贝剩余元素，别忘了
归并排序是唯一一个各情况都是 O(n log n) 的排序算法

复杂度：所有情况 O(n log n)，空间 O(n)，稳定

3.2 快速排序（Quick Sort）—— 面试最高频

核心思想：选一个基准值（pivot），把数组分成两部分——小于基准的放左边，大于基准的放右边——然后递归排序两部分。

记忆口诀：“选基准，做分区，左小右大递归去”。

版本一：简洁易懂版（适合理解思路）

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选中间元素作基准
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

版本二：原址分区版（面试手写推荐）

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)

def partition(arr, low, high):
    pivot = arr[high]  # 选最后一个元素作基准
    i = low - 1        # i 是"小于区"的右边界
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 把基准放到正确位置
    return i + 1

分区过程图解（以 [3, 6, 8, 10, 1, 2, 1] 为例，pivot=1）：

初始: [3, 6, 8, 10, 1, 2, |1]   pivot = arr[high] = 1, i = -1

j=0: arr[0]=3 > 1, 不交换
j=1: arr[1]=6 > 1, 不交换
j=2: arr[2]=8 > 1, 不交换
j=3: arr[3]=10 > 1, 不交换
j=4: arr[4]=1 = 1, 不交换（注意是 < 不是 <=）
j=5: arr[5]=2 > 1, 不交换

最后: arr[i+1] 与 arr[high] 交换 → 1 放到位置 0
结果: [1, 6, 8, 10, 1, 2, 3]   返回 pivot_idx = 0

手写要点：

i = low - 1，不是 i = 0！很多人这里写错
循环范围是 range(low, high)，不包含 high
最后一步交换 arr[i+1] 和 arr[high] 是关键，把基准归位
返回的是 i + 1，递归时左边到 pivot_idx - 1，右边从 pivot_idx + 1 开始

如何避免最坏情况 O(n²)：

随机选基准：pivot_idx = random.randint(low, high)，然后与 arr[high] 交换
三数取中：取 low、mid、high 三个位置的中位数作为基准

import random

def partition_random(arr, low, high):
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return partition(arr, low, high)  # 调用标准 partition

复杂度：平均 O(n log n)，最坏 O(n²)（已排序数组 + 固定选最后元素），空间 O(log n)（递归栈），不稳定

3.3 堆排序（Heap Sort）

核心思想：利用"最大堆"的性质——堆顶永远是最大值。先建堆，然后反复把堆顶（最大值）与末尾交换，缩小堆范围，重新调整。

记忆口诀：“建大堆，顶最大，换末尾，堆缩小，向下沉”。

堆的本质：用数组表示的完全二叉树。对于节点 i：

左子节点：2*i + 1
右子节点：2*i + 2
父节点：(i-1) // 2

def heap_sort(arr):
    n = len(arr)

    # 第一步：建堆（从最后一个非叶节点开始下沉）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 第二步：逐个取堆顶（最大值）放到末尾
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 堆顶与末尾交换
        heapify(arr, i, 0)               # 在缩小的堆中重新下沉
    return arr

def heapify(arr, heap_size, root):
    """下沉操作：把 root 节点调整到正确位置"""
    largest = root
    left = 2 * root + 1
    right = 2 * root + 2

    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, heap_size, largest)  # 递归下沉

手写要点：

建堆从 n // 2 - 1 开始（最后一个非叶节点），不是从 n - 1 开始
heapify 中用 heap_size 参数控制堆的范围，而不是 len(arr)
下沉操作用 while 循环写也可以（非递归版本）：

def heapify_iterative(arr, heap_size, root):
    while True:
        largest = root
        left = 2 * root + 1
        right = 2 * root + 2
        if left < heap_size and arr[left] > arr[largest]:
            largest = left
        if right < heap_size and arr[right] > arr[largest]:
            largest = right
        if largest == root:
            break
        arr[root], arr[largest] = arr[largest], arr[root]
        root = largest

复杂度：所有情况 O(n log n)，空间 O(1)（原地排序），不稳定

四、特殊排序

4.1 希尔排序（Shell Sort）

核心思想：插入排序的优化。先按较大间隔（gap）分组做插入排序，逐步缩小间隔，最后 gap=1 时就是标准插入排序。由于前面已经"大致有序"，最后一步非常快。

记忆口诀：“大步分组插排，逐步缩小步伐”。

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始间隔

    while gap > 0:
        # 对每个间隔做插入排序
        for i in range(gap, n):
            key = arr[i]
            j = i
            while j >= gap and arr[j - gap] > key:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = key
        gap //= 2  # 缩小间隔
    return arr

手写要点：

本质就是把插入排序中的"步长1"替换为"步长gap"
间隔序列不唯一：n/2, n/4, ..., 1 是最简单的，还有 Hibbard 序列 2^k - 1 等
面试中出现频率不高，但了解它"让插入排序更快"的思想很重要

复杂度：取决于间隔序列，通常 O(n^1.3) 到 O(n²)，空间 O(1)，不稳定

4.2 计数排序（Counting Sort）

核心思想：不比较元素大小，而是统计每个值出现的次数，然后按顺序输出。

适用条件：数据范围不大（如成绩 0-100，年龄 0-200）。

def counting_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    min_val = min(arr)
    count = [0] * (max_val - min_val + 1)

    # 统计每个值出现的次数
    for num in arr:
        count[num - min_val] += 1

    # 按顺序重建数组
    idx = 0
    for val, cnt in enumerate(count):
        for _ in range(cnt):
            arr[idx] = val + min_val
            idx += 1
    return arr

手写要点：

减去 min_val 是为了处理负数和节省空间
计数排序是稳定的（在重建数组时保持原顺序），但上面这个简洁版本未体现稳定性
如果要求稳定性（如作为基数排序的子过程），需要用"前缀和"版本：

def counting_sort_stable(arr):
    """稳定版本：使用前缀和确定每个元素的最终位置"""
    if not arr:
        return arr
    max_val, min_val = max(arr), min(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1

    # 计算前缀和
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 从后往前遍历保证稳定性
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        idx = arr[i] - min_val
        output[count[idx] - 1] = arr[i]
        count[idx] -= 1
    return output

复杂度：O(n + k)，其中 k 是数据范围。空间 O(k)。稳定（前缀和版本）。

五、面试高频题型与陷阱

5.1 “请手写快速排序”

这是面试中出现频率最高的排序题。要点：

先写递归框架 if low < high
再写 partition 函数
如果面试官问"如何优化"，答：随机化基准 + 小数组切换插入排序

5.2 “归并排序和快速排序的区别？”

维度	归并排序	快速排序
分割策略	从中间分	按基准值分
工作在哪一步	合并时	分区时
稳定性	稳定	不稳定
空间	O(n)	O(log n)（递归栈）
最坏情况	始终 O(n log n)	O(n²)

一句话总结：归并"先分后合"（工作在合并），快排"先分后不管"（工作在分区）。

5.3 “堆排序 vs 快速排序，哪个更快？”

实际应用中快速排序更快（常数因子小、缓存友好）。但堆排序的优势是：

空间 O(1)，快排递归栈 O(log n)
最坏情况稳定 O(n log n)
适合"Top K 问题"（维护大小为 K 的堆）

5.4 “什么时候用插入排序？”

数组很小（< 50 个元素）或近乎有序时，插入排序反而比 O(n log n) 算法更快。这也是为什么很多语言的标准库排序（如 Timsort、Introsort）会在小数组时切换到插入排序。

5.5 “Top K 问题”

面试常考：找数组中第 K 大/小的元素。

方法一：排序后取第 K 个，O(n log n)
方法二：快速选择（QuickSelect），平均 O(n)
方法三：维护大小为 K 的堆，O(n log K)

def quick_select(arr, k):
    """找第 k 小的元素（0-indexed）"""
    import random
    low, high = 0, len(arr) - 1
    while low < high:
        # 随机分区
        pivot_idx = random.randint(low, high)
        arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
        # 标准 partition
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        pivot_idx = i + 1

        if pivot_idx == k:
            return arr[k]
        elif pivot_idx < k:
            low = pivot_idx + 1
        else:
            high = pivot_idx - 1
    return arr[low]

六、终极记忆清单

面试前一晚，按这个顺序过一遍：

第一步：背复杂度表（见第一节总览表）

第二步：默写三个最重要的算法

快速排序（原址分区版）—— 出现频率最高
归并排序（分治合并版）—— 第二高频
堆排序（建堆 + 下沉）—— 与 Top K 问题关联

第三步：记住细节差异

冒泡内层是 n-1-i，有 swapped 优化
选择排序每轮只交换一次
插入排序用 key + while 后移，不是交换
归并排序用 <= 保证稳定
快排的 i = low - 1，最后交换 arr[i+1] 和 arr[high]
堆排序建堆从 n//2 - 1 开始

第四步：能回答这些追问

“快排最坏情况怎么避免？” → 随机化基准
“归并能不能原地？” → 理论上可以但很复杂，实际不推荐
“哪些排序是稳定的？” → "快选堆希"不稳定
“Top K 用什么算法？” → 堆 or QuickSelect

附录：Python 测试代码

用以下代码验证所有排序算法的正确性：

import random

def test_all_sorts():
    sorts = {
        'bubble': bubble_sort,
        'selection': selection_sort,
        'insertion': insertion_sort,
        'shell': shell_sort,
        'merge': lambda a: merge_sort(a),
        'quick': lambda a: quick_sort(a),
        'heap': lambda a: heap_sort(a[:]),  # heap_sort 是原地修改
        'counting': counting_sort,
    }
    for _ in range(100):
        arr = [random.randint(-50, 100) for _ in range(random.randint(0, 50))]
        expected = sorted(arr)
        for name, fn in sorts.items():
            result = fn(arr[:])
            assert result == expected, f"{name} failed: {arr} -> {result}, expected {expected}"
    print("All 100 random tests passed for all algorithms!")

# test_all_sorts()

目录CONTENT

排序算法速记手册 —— 面试手写代码必备