核心思想#

• 在未排序区间 [i, n-1] 中找到最小元素的下标 min
• 将 a[min] 与 a[i] 交换，a[i] 到达最终位置
• 每轮确定一个元素，共需 n-1 轮

代码实现#

1
void SelectionSort(int a[], int n) {
2
    for (int i = 0; i < n - 1; i++) {
3
        int min = i;
4
        for (int j = i + 1; j < n; j++)
5
            if (a[j] < a[min]) min = j;
6
        if (min != i) {
7
            int tmp = a[i];
8
            a[i] = a[min];
9
            a[min] = tmp;
10
        }
11
    }
12
}

复杂度#

⚠️ 易错：简单选择排序是不稳定的。反例 {5a, 5b, 3}，第一趟选出 3 与 5a 交换 → {3, 5b, 5a}，相对顺序颠倒。

⚠️ 易错：比较次数始终为 n(n-1)/2，与初始序列无关。408 常考”以下哪种排序的比较次数与初始序列无关”。

与冒泡排序对比#

O(1) 空间的 O(n log n) 排序#

堆排序只用 O(1) 额外空间就能保证最坏 O(n log n)——快排做不到。但 cache 不友好，实际速度常输给快排。

堆的概念#

堆是一棵完全二叉树：

• 大顶堆（最大堆）：每个结点 ≥ 其左右孩子 A[i] ≥ A[2i+1] 且 A[i] ≥ A[2i+2]
• 小顶堆（最小堆）：每个结点 ≤ 其左右孩子 A[i] ≤ A[2i+1] 且 A[i] ≤ A[2i+2]

下标关系（数组从 0 开始）：

建堆过程#

自底向上的向下调整（sift-down）：从最后一个非叶子结点（下标 n/2-1）开始，依次向前对每个结点执行 sift-down。

1
void SiftDown(int A[], int n, int i) {
2
    int largest = i;
3
    int left = 2 * i + 1;
4
    int right = 2 * i + 2;
5
    if (left < n && A[left] > A[largest]) largest = left;
6
    if (right < n && A[right] > A[largest]) largest = right;
7
    if (largest != i) {
8
        swap(A[i], A[largest]);
9
        SiftDown(A, n, largest);
10
    }
11
}
12

13
void BuildMaxHeap(int A[], int n) {
14
    for (int i = n / 2 - 1; i >= 0; i--)
15
        SiftDown(A, n, i);
16
}

⚠️ 易错：建堆的时间复杂度是 O(n)，不是 O(n log n)。大部分结点位于底层，调整距离短，总和为 O(n)。

排序过程#

1
void HeapSort(int A[], int n) {
2
    BuildMaxHeap(A, n);
3
    for (int i = n - 1; i > 0; i--) {
4
        swap(A[0], A[i]);       // 堆顶与末尾交换
5
        SiftDown(A, i, 0);     // 调整堆顶，堆规模减 1
6
    }
7
}

堆的插入与删除#

⚠️ 注意：用 sift-up 逐个插入建堆的时间复杂度为 O(n log n)，不如自底向上 sift-down 的 O(n)。

复杂度#

Top-K 问题#

从 n 个元素中选出前 K 大/小：

• 建一个大小为 K 的小顶堆（求前 K 大）或大顶堆（求前 K 小）
• 扫描剩余元素，比堆顶大则替换并调整
• 时间复杂度：O(n log K)

简单选择排序#

• ⭐ 比较次数始终为 n(n-1)/2，与初始序列无关
• ⭐ 不稳定排序，反例 {2, 2, 1}
• ⭐ 时间复杂度始终 O(n²)

堆排序#

• ⭐ 建堆复杂度 O(n) 而非 O(n log n)（高频陷阱）
• ⭐ 不稳定排序
• ⭐ 空间复杂度 O(1)，原地排序
• ⭐ 父子结点下标关系（从 0 / 从 1 开始）
• ⭐ Top-K 问题的堆解法
• 给定序列判断是否为堆 / 画出建堆中间过程
• 堆排序 vs 快排 vs 归并的综合比较