选择类排序

概念

选择类排序（selection sort）的思路是：每一趟从"未排序区"里挑出最值，与"已排序区"的边界元素交换。已排序区逐趟扩大一个元素。

• 简单选择排序：每趟线性扫描未排序区找最小值。
• 堆排序（heap sort）：把未排序区维护成堆，让"找最值"从扫描 O(n) 变成读堆顶 O(1)、维护堆 O(log n)。

两者的差别只在"怎么找最值"这一件事上，而这一个差别直接把时间复杂度从 O(n²) 拉到了 O(n log n)。

一句话记忆：选择类排序的字典里没有"逆序对"这个词——它每趟只做一次交换（堆排序也只在交换堆顶时动元素），所以它的代价主要由比较决定，而比较次数与初始序列几乎无关。

原理

一、简单选择排序

   第 1 趟：在 a[1..n] 中找最小 → 与 a[1] 交换
   第 2 趟：在 a[2..n] 中找最小 → 与 a[2] 交换
   ...
   第 n-1 趟：在 a[n-1..n] 中找最小 → 与 a[n-1] 交换

比较次数与初始序列完全无关，恒为：

$$\sum _{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$$

交换（移动）次数与初始序列有关：最好情况（已经有序）交换 0 次；最坏情况每趟都交换，每次交换涉及 3 次移动，共 $3(n-1)$ 次。

指标	值
时间复杂度	O(n²)，最好/最坏/平均都一样
比较次数	恒为 ${\displaystyle \frac{n(n-1)}{2}}$
移动次数	最好 0，最坏 $3(n-1)$
空间	O(1)
稳定性	不稳定

为什么不稳定：交换是"远距离"的。设序列 2A, 2B, 1，第 1 趟把最小的 1 与 2A 交换，得到 1, 2B, 2A——2A 被扔到了 2B 后面。

二、堆排序（站在"选择"的视角看）

堆排序把"每趟扫描找最小"替换成"用堆序性直接拿到最值"：

1. 建堆：把 $n$ 个元素整理成大根堆，堆顶 $a[1]$ 就是全局最大值。这一步是 $O(n)$。
2. 每趟选择：把堆顶 $a[1]$ 与当前堆的最后一个元素交换（最大值归位到尾部），堆长度减 1，再对 $a[1]$ 做一次向下调整（sift down）恢复堆序。单趟 $O(\log n)$。
3. 重复 $n-1$ 趟，序列升序。

   选择类排序的两种"找最值"方式对比

   简单选择：  在 a[i..n] 里扫一遍   →  每趟 O(n)  →  总计 O(n²)
   堆排序：    读 a[1] 拿最值 +
               一次下滤恢复堆序      →  每趟 O(log n) → 总计 O(n log n)

指标	堆排序
时间复杂度	O(n log n)，最好/最坏/平均都一样
空间	O(1)（原地，无需额外数组）
稳定性	不稳定
比较次数	与初始状态有关，但不超过 $2n\lceil {\log }_{2}n\rceil$

堆的编号约定、向下/向上调整的完整推导、$O(n)$ 建堆的级数证明，见 堆与优先队列。本篇只从"选择类排序"的角度归纳结论。

堆排序的两个工程劣势：① 数组元素是跳跃访问（$a[i]$ 与 $a[2i]$ 相隔很远），对 CPU 缓存不友好，实测常数比快排大；② 不稳定。它的优势是最坏也是 O(n log n) 且空间 O(1)——这是快排做不到的。

示例

例 1：简单选择排序逐趟推演

对 49, 38, 65, 97, 76, 13, 27, 49* 做简单选择排序。

趟次	未排序区	本轮最小值	交换对象	结果
初始	49 38 65 97 76 13 27 49*	—	—	49 38 65 97 76 13 27 49*
1	38 65 97 76 13 27 49*	13	49 ↔ 13	13 38 65 97 76 49 27 49*
2	65 97 76 49 27 49*	27	38 ↔ 27	13 27 65 97 76 49 38 49*
3	97 76 49 38 49*	38	65 ↔ 38	13 27 38 97 76 49 65 49*
4	76 49 65 49*	49（第一个 49）	97 ↔ 49	13 27 38 49 76 97 65 49*
5	76 97 65 49*	49*	76 ↔ 49*	13 27 38 49 49* 97 65 76
6	97 65 76	65	97 ↔ 65	13 27 38 49 49* 65 97 76
7	97 76	76	97 ↔ 76	13 27 38 49 49* 65 76 97

统计：比较次数恒为 ${\displaystyle \frac{8\times 7}{2}}=28$ 次；本序列共交换 7 次，移动 $7\times 3=21$ 次。

注意第 4 趟：未排序区里有两个相等的 49（下标 4 与 8）。算法找到第一个最小值（下标 4 的 49），把它与 97 交换。这一步看起来"无害"，但如果最小值恰好在更靠后的位置，就会发生例 2 里那种跨过相等元素的搬运——这就是不稳定性的来源。

例 2：简单选择排序的不稳定反例

序列 2A, 2B, 1 做简单选择排序。

趟次	动作	结果
初始	—	2A 2B 1
1	扫描得最小值为 1（下标 3），与 a[1] = 2A 交换	1 2B 2A

第 1 趟结束时 2A 已经跑到 2B 后面，排序完成时仍是 1, 2B, 2A——不稳定。原因很简单：交换的跨度可以是整个未排序区，一次交换就可能把某个元素甩到它的"同值伙伴"之后。

例 3：堆排序逐趟推演

对 46, 79, 56, 38, 40, 84, 12（n = 7，1-indexed）建大根堆并做堆排序。

第一步，建堆（从 $i=\lfloor 7/2\rfloor =3$ 往前逐个下滤）：

步骤	处理结点	动作	序列
初始	—	—	46 79 56 38 40 84 12
①	i=3（56）	孩子 84、12，取大者 84 > 56 → 上移	46 79 84 38 40 56 12
②	i=2（79）	孩子 38、40，均 < 79 → 不动	46 79 84 38 40 56 12
③	i=1（46）	孩子 79、84，取 84 上移；空位落到 3，其孩子 56、12 中 56 > 46 → 继续上移；空位落到 6，46 落位	84 79 56 38 40 46 12

大根堆建成：

              84
          /        \
        79          56
       /  \        /  \
     38    40     46   12

第二步，堆排序逐趟（交换堆顶与末尾 → 堆长减 1 → 对 $a[1]$ 下滤）：

趟次	交换	下滤后堆区	已归位尾部
1	84 ↔ 12	79 40 56 38 12 46	84
2	79 ↔ 46	56 40 46 38 12	79 84
3	56 ↔ 12	46 40 12 38	56 79 84
4	46 ↔ 38	40 38 12	46 56 79 84
5	40 ↔ 12	38 12	40 46 56 79 84
6	38 ↔ 12	12	38 40 46 56 79 84

最终升序序列：12 38 40 46 56 79 84

结论：大根堆 → 升序。每趟只做 1 次交换（3 次移动），所以堆排序的移动次数很少，主要开销在比较上。

C 语言：两种选择类排序

#include <stdio.h>

/* ---------- 简单选择排序 ---------- */
void selectSort(int a[], int n) {
    for (int i = 1; i <= n - 1; i++) {
        int k = i;                              /* k 记录本趟最小值下标 */
        for (int j = i + 1; j <= n; j++)
            if (a[j] < a[k]) k = j;             /* 严格小于：取最先出现的最小值 */
        if (k != i) {                           /* 只有需要时才交换 */
            int t = a[i]; a[i] = a[k]; a[k] = t;
        }
    }
}

/* ---------- 堆排序（下标从 1 开始，a[0] 空置） ---------- */
void siftDown(int a[], int low, int high) {
    int i = low, j = 2 * i, tmp = a[i];
    while (j <= high) {
        if (j + 1 <= high && a[j + 1] > a[j]) j++;   /* 取较大的孩子 */
        if (a[j] <= tmp) break;
        a[i] = a[j];  i = j;  j = 2 * i;
    }
    a[i] = tmp;
}

void heapSort(int a[], int n) {
    for (int i = n / 2; i >= 1; i--) siftDown(a, i, n);   /* 建堆 O(n) */
    for (int i = n; i > 1; i--) {
        int t = a[1]; a[1] = a[i]; a[i] = t;              /* 堆顶归位到末尾 */
        siftDown(a, 1, i - 1);                            /* 恢复堆序 O(log n) */
    }
}

int main(void) {
    int s[9] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    int h[8] = {0, 46, 79, 56, 38, 40, 84, 12};

    selectSort(s, 8);
    heapSort(h, 7);

    printf("简单选择: "); for (int i = 1; i <= 8; i++) printf("%d ", s[i]); printf("\n");
    printf("堆排序:   "); for (int i = 1; i <= 7; i++) printf("%d ", h[i]); printf("\n");
    /* 简单选择: 13 27 38 49 49 65 76 97
       堆排序:   12 38 40 46 56 79 84 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

def select_sort(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):
            if a[j] < a[k]:
                k = j
        if k != i:
            a[i], a[k] = a[k], a[i]
    return a

def sift_down(a, low, high):
    """a 为 1-indexed（a[0] 占位）"""
    i, j, tmp = low, 2 * low, a[low]
    while j <= high:
        if j + 1 <= high and a[j + 1] > a[j]:
            j += 1
        if a[j] <= tmp:
            break
        a[i] = a[j]
        i, j = j, 2 * j
    a[i] = tmp

def heap_sort(a, n):
    for i in range(n // 2, 0, -1):      # 建堆 O(n)
        sift_down(a, i, n)
    for i in range(n, 1, -1):           # n-1 趟选择
        a[1], a[i] = a[i], a[1]
        sift_down(a, 1, i - 1)

src = [49, 38, 65, 97, 76, 13, 27, 49]
print("简单选择:", select_sort(src))

h = [0, 46, 79, 56, 38, 40, 84, 12]
heap_sort(h, 7)
print("堆排序:  ", h[1:])                # [12, 38, 40, 46, 56, 79, 84]

# —— 简单选择的不稳定反例（用二元组观察）——
t = [(2, 'A'), (2, 'B'), (1, '')]
n = len(t)
for i in range(n - 1):
    k = i
    for j in range(i + 1, n):
        if t[j][0] < t[k][0]:
            k = j
    if k != i:
        t[i], t[k] = t[k], t[i]
print("两个 2 的顺序:", [(v, tag) for v, tag in t if v == 2])   # B 在前，A 在后 → 不稳定

# —— 对比：Python 内置排序是稳定的 Timsort ——
print("sorted 结果:", sorted([(2, 'A'), (2, 'B'), (1, '')]))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

算法	比较次数	移动次数	时间（最好/最坏/平均）	空间	稳定
简单选择	恒为 ${\displaystyle \frac{n(n-1)}{2}}$	最好 0，最坏 $3(n-1)$	全为 O(n²)	O(1)	不稳定
堆排序	与初始状态有关，$\le 2n{\log }_{2}n$	每趟至多 3 次	全为 O(n log n)	O(1)	不稳定

• 简单选择排序的比较次数与初始序列无关——这是它最常考的一句判断。原因：无论数据怎么排，"在 $n-i+1$ 个元素里找最小"都要扫这么多下。
• 简单选择排序在"记录占空间大、移动代价高"时反而有优势：它每趟至多交换一次，移动次数是 O(n) 级别，而插入排序的移动是 O(n²)。这是 408 选择题里很爱设置的一个对比点。
• 堆排序的最坏也是 O(n log n)，且空间 O(1)；快排最坏 O(n²)、归并空间 O(n)。三者各有长短，这个三角对比是高频考点。

2. 手算套路

• 简单选择逐趟：只画一个数组 + 一条竖线（左边已排序、右边未排序），每趟圈一下未排序区的最小值，写一次交换即可。
• 手算堆排序：不要试图在树上操作。写成数组，每趟写三行—— 交换后：... | 已归位部分、下滤后：... | 已归位部分，比画图快且不易错。
• 题目问"第 k 趟后的序列"：尾部已经有 k 个（简单选择是 k 个）元素归位且不再变动，只看头部。

3. 易错点

• "选择排序比较次数与初始序列无关" 只对简单选择成立。堆排序的比较次数与初始序列有关（不同初始堆的建堆与下滤路径不同），只是都落在 O(n log n)。
• 简单选择排序不是"移动次数最少"的排序：论最少移动，插入排序在正序时是 0 次移动。正确的说法是"简单选择的移动次数较少（O(n) 量级）"，而不是最少。
• 堆排序稳定性的反例：序列 1A, 1B，建堆不动，第一趟把 1A 换到末尾、末尾元素顶上来，然后再下滤——1B 会排到 1A 前面。建堆本身就可能打乱相等元素的次序。
• 大根堆出升序、小根堆出降序，别记反。记忆："大根堆每次把最大的扔到最后 → 从小到大排列"。
• 堆排序不适合在链表上实现：需要按下标跳跃访问，链式存储做不了随机存取（这点与希尔排序相同）。
• "堆排序是原地排序"要加限定：它的数据是原地的（O(1) 辅助空间），但递归不涉及；它本身是迭代实现，所以空间确实是 O(1)。而快排的空间 O(log n) 是栈，不是数据副本——两者别混。
• 建立初始堆的时间是 O(n)，不是 O(n log n)；只有"逐个插入"的建堆才是 O(n log n)。这个区别在 16 篇已用级数证明过，考试中常以判断形式出现。

小结

• 选择类排序的共同动作：每趟挑出最值，放到已排序区边界。区别只在"怎么找最值"。
• 简单选择：比较次数恒为 $n(n-1)/2$（与初始序列无关），移动次数 O(n) 级别，不稳定，总时间 O(n²)。
• 堆排序：用堆把"找最值"从 O(n) 降到 O(log n)，得到恒定 O(n log n) + O(1) 空间，代价是不稳定且缓存不友好。
• 不稳定性的根源是远距离交换——这正是它和"相邻交换"的冒泡（稳定）的分水岭。
• 下一步：最后一类基于比较的排序——归并排序，以及唯一不基于比较的基数排序。

下一篇：归并排序与基数排序