简单选择排序

2026 大纲 七（五）简单选择排序（也称直接选择排序）。

只比较，不搬运

简单选择排序的动作很直白：在未排序区扫一遍，找出最小的那个，与未排序区的第一个位置交换。做 $n-1$ 趟就完了。

一趟之后的不变量是：

前 $k$ 个位置是全局最小的 $k$ 个元素，已升序且永不再动；后 $n-k$ 个内部次序任意。

注意"全局最小的 $k$ 个"这个措辞——它和直接插入排序的"前缀有序但未必就位"是两回事，这也是区分插入类与选择类的判据。

它真正的特点藏在一个反直觉的地方：

🔴 它遍历时不动数据，找到目标后只做一次集中交换。 每趟最多 1 次交换（3 条赋值），总移动次数 $\le 3(n-1)$ ——是 $O(n)$，不是 $O(n^2)$。

而其他三个 $O(n^2)$ 算法（冒泡、直接插入、快速排序最坏时）都在比较的过程中就伴随移动，因而被推到 $O(n^2)$ 的移动量级。

先动手看一眼

加载可视化中...

代码与四处细节

void SelectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {      // 共 n-1 趟，最后一个元素自动就位
        int k = i;                          // k 指向本趟见过的最小元素
        for (int j = i + 1; j < n; j++) {   // 扫遍未排序区 [i+1, n-1]
            if (a[j] < a[k])                // 严格小于才更新，相等时保留靠前的那个
                k = j;
        }
        if (k != i) {                       // 已在位就不做无谓的交换
            int tmp = a[i];
            a[i] = a[k];
            a[k] = tmp;                     // 一次交换 = 3 条赋值
        }
    }
}

第一，外层只到 n - 2。 前 $n-1$ 个位置都确定后，剩下的那一个必然是最大值，无须再选。边界上 n <= 1 时外层循环不执行，安全。

第二，if (k != i) 只省移动、不省比较。 内层循环的执行次数完全由下标决定、与元素取值无关——这正是下一节"比较次数恒定"的根源。

第三，内层用 < 而不是 <=。 相等时不更新 k，本趟选中的是最靠前的那个最小值。这一条减少了不稳定发生的机会，但并不能消除它。

第四，判别"就位"的机械方法：把前缀里的最大值与后缀里的最小值比一下——前者不大于后者就是"已就位"（选择类），否则只是"局部有序"（插入类）。这两行就是由中间状态反推排序算法区分两类的全部依据。

全章唯一"三种情况完全一样"的比较类算法

比较次数恒定。 第 $i$ 趟（$i$ 从 0 计）内层循环从 $j=i+1$ 走到 $j=n-1$，执行 $n-1-i$ 次比较。这个次数只由下标决定——循环边界里没有任何元素的取值参与，所以不管输入是正序、逆序还是随机，执行次数一模一样：

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

🔴 最好、最坏、平均全部是 $\mathrm{\Theta }(n^2)$，不存在"已有序就变快"这回事。 这与冒泡（有序时 1 趟终止）、直接插入（有序时 $n-1$ 次比较）完全不同。

移动次数只有 $O(n)$，而且与输入无关。 已有序时每趟 k == i、0 次移动；最坏 $n-1$ 次交换、$3(n-1)$ 次移动。

对比项	简单选择排序	冒泡排序	直接插入排序
比较次数	恒 $n(n-1)/2$	最好 $n-1$，最坏 $n(n-1)/2$	最好 $n-1$，最坏约 $n^2/2$
移动次数	最多 $3(n-1)$	最坏 $3n(n-1)/2$	最坏约 $n^2/2$
对输入是否敏感	否	是	是
稳定性	不稳定	稳定	稳定
何时该选它	记录很大、移动代价高	输入基本有序且要求稳定	输入基本有序

由此得到它唯一但不可替代的优势：

🔴 最坏情况下元素移动最少的就是它。 记录很大时搬一条记录远贵于比一次关键字——直接插入要移动约 $n^2/4$ 次、冒泡约 $3n^2/4$ 次、快排最坏 $O(n^2)$ 次，而它最多 $3(n-1)$ 次。

⚠️ 反过来也要说准："直接插入排序比它快"只体现在比较次数上，移动次数上简单选择反而更稳（详见直接插入排序里那张三条理由的辨析表）。

存储结构：只需顺序扫描找最小值，顺序表、链表都能用。

不稳定：远距离交换跨过了相等元素

最小反例 {2a, 2b, 1}：

趟	操作	结果
初始	—	2a 2b 1
1	未排序区 [0,2] 的最小值是 a[2] = 1，交换 a[0] ↔ a[2]	1 2b 2a
2	未排序区 [1,2] 的最小值是 a[1] = 2b，k == i，不交换	1 2b 2a

2b 排到了 2a 前面。

根源：a[i] 与 a[k] 的交换是远距离的——a[i] 被直接甩到下标 k 处，中间凡是与它关键字相等的元素都被它一次性跨了过去。这与冒泡排序形成鲜明对照：冒泡只交换相邻元素，一个元素想越过另一个必须先与它直接比较一次，而相等时那次比较不触发交换，所以永远越不过去。

一条值得知道的分界：教材指出"就选择排序方法本身来讲，它是一种稳定的排序方法……不稳定现象是因为上述实现选择排序的算法采用'交换记录'的策略所造成的"。也就是说，不稳定来自"交换"这个实现手法，而不是"选择"这个思想。

408 语境下的"简单选择排序"默认就是交换实现，所以结论按 不稳定 记；这段只是让你明白来源，不是让你改答案。

它为什么能被改进成 $O(n\log n)$

简单选择排序每一趟都把未排序区从头扫到尾，上一趟辛苦比出来的大小关系一点没用上——这才是 $n(n-1)/2$ 次比较的来源。

在 $n$ 个关键字中选出最小值至少要 $n-1$ 次比较（每个非最小元素至少要输一次）；但选次小值并不需要再做 $n-2$ 次比较，因为次小值只可能出现在"直接输给最小值的那些元素"里。

把这个信息用一棵树保存下来，每次只需沿一条路径调整，每趟比较次数就从 $O(n)$ 降到 $O({\log }_{2}n)$，总复杂度变成 $O(n{\log }_{2}n)$——这就是堆排序的由来。

逐趟推演与执行流程图（第一次学、或想手动模拟就展开）

以 {49, 38, 65, 97, 49*, 13, 27, 76} 为例（49* 是第二个 49），括号内为已就位部分：

趟	未排序区	选出的最小值	交换	本趟结果
初始	—	—	—	49 38 65 97 49* 13 27 76
1	[0,7]	a[5] = 13	a[0] ↔ a[5]	(13) 38 65 97 49* 49 27 76
2	[1,7]	a[6] = 27	a[1] ↔ a[6]	(13 27) 65 97 49* 49 38 76
3	[2,7]	a[6] = 38	a[2] ↔ a[6]	(13 27 38) 97 49* 49 65 76
4	[3,7]	a[4] = 49*	a[3] ↔ a[4]	(13 27 38 49*) 97 49 65 76
5	[4,7]	a[5] = 49	a[4] ↔ a[5]	(13 27 38 49* 49) 97 65 76
6	[5,7]	a[6] = 65	a[5] ↔ a[6]	(13 27 38 49* 49 65) 97 76
7	[6,7]	a[7] = 76	a[6] ↔ a[7]	(13 27 38 49* 49 65 76) 97

第 1 趟就把不稳定演出来了：13 与 a[0] = 49 交换，49 被一脚踢到下标 5，而 49* 原本在下标 4——两个相等元素的先后关系当场翻转。

把它改成稳定的：代价是什么（想知道为什么没人这么用就展开）

既然不稳定来自"交换"，那就把交换换掉：找到最小者 a[k] 后，把 a[i..k-1] 整体后移一位，再把最小者放到 a[i]——这样最小者是"插"进去的，不会跨越任何元素。

void StableSelectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int k = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[k]) k = j;          // 仍取最靠前的最小值
        int t = a[k];
        for (int j = k; j > i; j--)
            a[j] = a[j - 1];                 // a[i..k-1] 整体后移一位
        a[i] = t;                            // 最小者插到最前
    }
}

验证：{2a, 2b, 1} $\to$ {1, 2a, 2b}，{49, 38, 65, 97, 49*, 13, 27, 76} $\to$ 13 27 38 49 49* 65 76 97——两组相等元素的相对次序都保住了。但代价很重：后移次数与"最小者离目标位置多远"成正比，最坏每趟要搬 $O(n)$ 次，总移动次数退回 $\mathrm{\Theta }(n^2)$：

$n$（逆序输入）	10	50	100
移动式（稳定）的移动次数	63	1 323	5 148
交换式（不稳定）的移动次数 $3(n-1)$	27	147	297

换来了稳定性，丢掉的正是简单选择排序唯一的优势——$O(n)$ 的移动次数。 而且此时它相对直接插入排序已经全面落后。所以这个变体只有理论意义。

考点速记

三条结论：

1. 比较次数恒为 $n(n-1)/2$、与输入完全无关——全章唯一"三种情况完全一样"的比较类算法。
2. 移动次数最多 $3(n-1)$，是 $O(n)$——所有 $O(n^2)$ 排序里最少的。
3. 不稳定来自"远距离交换"，反例 {2a, 2b, 1}。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 最坏情况下元素移动最少的是哪个：候选是冒泡、直接插入、快速、简单选择——答简单选择排序。它遍历时不动数据、只在找到目标后做一次集中交换，总移动 $\le 3(n-1)$；另外三个都在比较过程中伴随移动，最坏都是 $O(n^2)$。
• 直插比它快的原因是什么：三个候选理由里只有"比较次数更少"成立。"辅助空间更少"✗（都是 $O(1)$）、"移动次数更少"✗（简单选择的移动次数恒约 $3(n-1)$，反而更稳）。
• "每趟至少确定一个元素最终位置"的有哪些：简单选择符合（每趟恰好 1 个，且是全局最值），与快排、堆排同列（详见排序算法对比）。

易错：它的移动次数比直接插入少一个数量级。 别想当然地认为"插入排序哪儿都比选择排序好"。

易错：它没有"最好情况"。 输入已有序也照比 $n(n-1)/2$ 次。

易错：它每趟就位的是全局最值，与插入类的"局部有序"是两回事——反推算法时靠这一条区分。

教材出处

• 简单选择排序的算法步骤与算法描述（算法 8.6）、以 $\{49,38,65,97,49,13,27,76\}$ 为例的逐趟过程（图 8.6）：严蔚敏《数据结构（C 语言版）》（第 2 版），p246–p247
• 最好情况（正序）不移动、最坏情况（逆序）移动 $3(n-1)$ 次；"无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为 $\text{KCN}=\sum _{i=1}^{n-1}(n-i)=n(n-1)/2$"；空间复杂度 $O(1)$：同书 p247
• 算法特点，含"就选择排序方法本身来讲，它是一种稳定的排序方法，但图 8.6 所表现出来的现象是不稳定的，这是因为上述实现选择排序的算法采用'交换记录'的策略所造成的"、"可用于链式存储结构"、"移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快"：同书 p247
• "在 $n$ 个关键字中选出最小值至少要进行 $n-1$ 次比较，然而继续在剩余的 $n-1$ 个关键字中选择次小值并非一定要进行 $n-2$ 次比较，若能利用前 $n-1$ 次比较所得信息，则可减少以后各趟选择排序中所用的比较次数"（这是通向堆排序的动机）：同书 p247–p248

相关知识

排序的基本概念｜ 堆排序（选择类的改进：用堆复用上一趟的比较结果）｜ 冒泡排序（同为 $O(n^2)$ 的交换型，但稳定且对输入敏感）｜ 直接插入排序（比较次数少，但移动次数高一个数量级）｜ 由中间状态反推排序算法｜ 排序算法对比

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（2题）

2025Q102分2020Q112分