考研 408 · 排序核心知识点

考研 408 · 排序核心知识点

排序是 408 高频选择题 + 偶尔大题：背总表、会手推过程、能判断稳定性。

1. 总表（必背）

记忆点：稳定的只有 直接插入 / 冒泡 / 归并 / 基数；快排最坏 O(n²)；归并空间 O(n)。

2. 插入类

直接插入

初始: [3] 1 4 2
第1趟: [1 3] 4 2
第2趟: [1 3 4] 2
第3趟: [1 2 3 4]

思想：把待排元素插入已有序前缀的合适位置。

希尔排序

按增量 d 分组做直接插入，增量逐步缩小到 1（最后一次就是直接插入）。
例：d=2 时分成奇偶两组分别插入排序。

3. 交换类

冒泡

第1趟: 3 1 4 2 → 1 3 2 [4]（4 冒到末尾）
第2趟: 1 3 2 → 1 2 [3] 4
第3趟: 1 [2] 3 4

无交换可提前结束，最好 O(n)。

快速排序（分治）

选基准（通常首元素）→ 一趟划分：左小右大 → 递归两侧
例 [4 2 5 1 3] 以 4 为基准一趟后：[1 2 3] 4 [5]

int partition(int a[], int low, int high) {
    int pivot = a[low];
    while (low < high) {
        while (low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

快排平均 O(n log n)；若每次划分极不平衡（已有序）最坏 O(n²)。

4. 选择类

简单选择

每趟选剩余最小元素与当前位置交换：
[1] 3 4 2 → 1 [2] 4 3 → 1 2 [3] 4

比较次数固定 n(n−1)/2，与初始状态无关。

堆排序

建大根堆 → 堆顶与末尾交换 → 下沉调整
[4 3 2 1] 交换 1： [1 3 2] 4 → 下沉 → [3 1 2] 4 → 交换 → [2 1] 3 4 → ...

大根堆：parent ≥ children；调整（sift down）O(log n)
建堆 O(n)；排序 O(n log n)

5. 归并排序（二路）

分：数组二分到底；治：两两有序合并
[4 2 5 1] → [4 2][5 1] → [2 4][1 5] → [1 2 4 5]

void merge(int a[], int low, int mid, int high) {
    // 复制到临时数组，双指针比较归并
}
void mergeSort(int a[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

稳定、O(n log n)、空间 O(n)；适合外部排序基础。

6. 基数排序

按"位"分配-收集：个位 → 十位 → 百位…
例 [12, 3, 45]：
  个位收集：3(03) 12 45 → 十位收集：3 12 45
复杂度 O(d(n+r))，d 位数、r 基数（十进制 10）

7. 408 高频结论

8. 外部排序（了解）

归并段（run）→ 败者树多路归并 → 置换选择排序生成更长段
总代价 ≈ 内部归并 + I/O 次数；I/O 次数 = 2×趟数×块数
增加归并路数、减少初始段数可减少 I/O

9. 例题速览

例 1：[1, 3, 2, 5, 4] 用直接插入排序第 2 趟结果。

第1趟: [1 3] 2 5 4
第2趟: [1 2 3] 5 4

例 2：下列哪个排序是稳定的？直接插入 / 快排 / 堆排 / 希尔。

答案：直接插入

上一篇：图

Read Also

• 考研 408 · 图核心知识点