11.2 选择排序¶
选择排序(selection sort)的工作原理非常简单:开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序区间的末尾。
设数组的长度为 \(n\) ,选择排序的算法流程如图 11-2 所示。
- 初始状态下,所有元素未排序,即未排序(索引)区间为 \([0, n-1]\) 。
- 选取区间 \([0, n-1]\) 中的最小元素,将其与索引 \(0\) 处的元素交换。完成后,数组前 1 个元素已排序。
- 选取区间 \([1, n-1]\) 中的最小元素,将其与索引 \(1\) 处的元素交换。完成后,数组前 2 个元素已排序。
- 以此类推。经过 \(n - 1\) 轮选择与交换后,数组前 \(n - 1\) 个元素已排序。
- 仅剩的一个元素必定是最大元素,无须排序,因此数组排序完成。
图 11-2 选择排序步骤
图解 11-2:选择排序
每轮选择未排序区间的最小元素,再与区间首元素交换,使已排序前缀扩大一项。
待排序数组为 nums = [4, 1, 3, 1, 5, 2],共 6 个元素,索引从 0 到 5,目标是按非递减顺序完成排序。
每轮由指针 i 指向当前“未排序区间”的首个元素,由指针 k 记录从该未排序区间中选出的最小元素索引。绿色表示未排序部分,左侧灰色方格表示已排好序的前缀,上方花括号标出当前“未排序区间”;选定 k 后,将最小元素 nums[k] 与区间首元素 nums[i] 交换,使已排序前缀向右扩展一位。
十一幅画面中,前十幅按五轮排列,每轮有选择画面和交换画面:选择画面直接给出扫描完成后的 i、k,不逐格展开内循环比较;交换画面显示完成后的数组,用上下交换弧线标出刚交换的位置,并隐藏 i、k 指针文字。第十一幅显示末尾只剩一个元素,无须第六轮。
选出索引 1 的最小值 1
第 1 轮选择:当前 nums = [4, 1, 3, 1, 5, 2]。在未排序索引区间 [0, 5] 扫描后,i = 0 指向首元素 4,k = 1 指向最小值 1。两个 1 位于索引 1、3,严格小于的比较规则保留靠左的 k = 1。尚无已排序前缀。尚未交换。
交换索引 0 与 1
第 1 轮交换:将未排序索引区间 [0, 5] 的最小值 1(索引 1)与首元素 4(索引 0)交换。当前 nums = [1, 4, 3, 1, 5, 2];灰色已排序前缀为索引 0,值为 [1];未排序索引区间为 [1, 5],值为 [4, 3, 1, 5, 2]。
选出索引 3 的最小值 1
第 2 轮选择:当前 nums = [1, 4, 3, 1, 5, 2]。在未排序索引区间 [1, 5] 扫描后,i = 1 指向首元素 4,k = 3 指向最小值 1。已排序前缀为索引 0,值为 [1]。尚未交换。
交换索引 1 与 3
第 2 轮交换:将未排序索引区间 [1, 5] 的最小值 1(索引 3)与首元素 4(索引 1)交换。当前 nums = [1, 1, 3, 4, 5, 2];灰色已排序前缀为索引 0 至 1,值为 [1, 1];未排序索引区间为 [2, 5],值为 [3, 4, 5, 2]。
选出索引 5 的最小值 2
第 3 轮选择:当前 nums = [1, 1, 3, 4, 5, 2]。在未排序索引区间 [2, 5] 扫描后,i = 2 指向首元素 3,k = 5 指向最小值 2。已排序前缀为索引 0 至 1,值为 [1, 1]。尚未交换。
交换索引 2 与 5
第 3 轮交换:将未排序索引区间 [2, 5] 的最小值 2(索引 5)与首元素 3(索引 2)交换。当前 nums = [1, 1, 2, 4, 5, 3];灰色已排序前缀为索引 0 至 2,值为 [1, 1, 2];未排序索引区间为 [3, 5],值为 [4, 5, 3]。
选出索引 5 的最小值 3
第 4 轮选择:当前 nums = [1, 1, 2, 4, 5, 3]。在未排序索引区间 [3, 5] 扫描后,i = 3 指向首元素 4,k = 5 指向最小值 3。已排序前缀为索引 0 至 2,值为 [1, 1, 2]。尚未交换。
交换索引 3 与 5
第 4 轮交换:将未排序索引区间 [3, 5] 的最小值 3(索引 5)与首元素 4(索引 3)交换。当前 nums = [1, 1, 2, 3, 5, 4];灰色已排序前缀为索引 0 至 3,值为 [1, 1, 2, 3];未排序索引区间为 [4, 5],值为 [5, 4]。
选出索引 5 的最小值 4
第 5 轮选择:当前 nums = [1, 1, 2, 3, 5, 4]。在未排序索引区间 [4, 5] 扫描后,i = 4 指向首元素 5,k = 5 指向最小值 4。已排序前缀为索引 0 至 3,值为 [1, 1, 2, 3]。尚未交换。
交换索引 4 与 5
第 5 轮交换:将未排序索引区间 [4, 5] 的最小值 4(索引 5)与首元素 5(索引 4)交换。当前 nums = [1, 1, 2, 3, 4, 5];灰色已排序前缀为索引 0 至 4,值为 [1, 1, 2, 3, 4];未排序索引区间为 [5, 5],值为 [5]。
排序完成
五轮后 nums = [1, 1, 2, 3, 4, 5]。索引 0 至 4 为灰色已排序前缀;索引 5 的绿色元素 5 仍标在单元素未排序区间 [5, 5],但它必为最大值且已处于正确位置。图中文字说明“完成排序(剩余一个元素无须排序)”,i、k 均已隐藏。
在代码中,我们用 \(k\) 来记录未排序区间内的最小元素:
/* 选择排序 */
void selectionSort(vector<int> &nums) {
int n = nums.size();
// 外循环:未排序区间为 [i, n-1]
for (int i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
swap(nums[i], nums[k]);
}
}
/* 选择排序 */
void selectionSort(int[] nums) {
int n = nums.length;
// 外循环:未排序区间为 [i, n-1]
for (int i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
/* 选择排序 */
void SelectionSort(int[] nums) {
int n = nums.Length;
// 外循环:未排序区间为 [i, n-1]
for (int i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
(nums[k], nums[i]) = (nums[i], nums[k]);
}
}
/* 选择排序 */
function selectionSort(nums) {
let n = nums.length;
// 外循环:未排序区间为 [i, n-1]
for (let i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
let k = i;
for (let j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) {
k = j; // 记录最小元素的索引
}
}
// 将该最小元素与未排序区间的首个元素交换
[nums[i], nums[k]] = [nums[k], nums[i]];
}
}
/* 选择排序 */
function selectionSort(nums: number[]): void {
let n = nums.length;
// 外循环:未排序区间为 [i, n-1]
for (let i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
let k = i;
for (let j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) {
k = j; // 记录最小元素的索引
}
}
// 将该最小元素与未排序区间的首个元素交换
[nums[i], nums[k]] = [nums[k], nums[i]];
}
}
/* 选择排序 */
void selectionSort(List<int> nums) {
int n = nums.length;
// 外循环:未排序区间为 [i, n-1]
for (int i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
/* 选择排序 */
fn selection_sort(nums: &mut [i32]) {
if nums.is_empty() {
return;
}
let n = nums.len();
// 外循环:未排序区间为 [i, n-1]
for i in 0..n - 1 {
// 内循环:找到未排序区间内的最小元素
let mut k = i;
for j in i + 1..n {
if nums[j] < nums[k] {
k = j; // 记录最小元素的索引
}
}
// 将该最小元素与未排序区间的首个元素交换
nums.swap(i, k);
}
}
/* 选择排序 */
void selectionSort(int nums[], int n) {
// 外循环:未排序区间为 [i, n-1]
for (int i = 0; i < n - 1; i++) {
// 内循环:找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
/* 选择排序 */
fun selectionSort(nums: IntArray) {
val n = nums.size
// 外循环:未排序区间为 [i, n-1]
for (i in 0..<n - 1) {
var k = i
// 内循环:找到未排序区间内的最小元素
for (j in i + 1..<n) {
if (nums[j] < nums[k])
k = j // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
val temp = nums[i]
nums[i] = nums[k]
nums[k] = temp
}
}
可视化运行
11.2.1 算法特性¶
- 时间复杂度为 \(O(n^2)\)、非自适应排序:外循环共 \(n - 1\) 轮,第一轮内循环执行 \(n - 1\) 次,最后一轮执行 \(1\) 次,即各轮内循环分别执行 \(n - 1\)、\(n - 2\)、\(\dots\)、\(2\)、\(1\) 次,求和为 \(\frac{n(n - 1)}{2}\) 。
- 空间复杂度为 \(O(1)\)、原地排序:指针 \(i\) 和 \(j\) 使用常数大小的额外空间。
- 非稳定排序:如图 11-3 所示,元素
nums[i]有可能被交换至与其相等的元素的右边,导致两者的相对顺序发生改变。
图 11-3 选择排序非稳定示例
图解 11-3:选择排序中的跨位置交换
观察首轮跨位置交换如何打乱两个相等元素 4 的相对次序,并区分单轮中间状态与完整排序的最终稳定性。
初始数组为 [4A, 4B, 3, 1, 5, 2],索引从 0 到 5。其中 4A 表示初始位于索引 0 的蓝色 4,4B 表示初始位于索引 1 的紫色 4;字母 A、B 仅为说明中区分两个相等元素身份的辅助标记,原图方块内均印数字 4。
选择排序每一轮在未排序区间中找出最小元素,与该区间的首个元素直接交换。排序算法的稳定性,则是按全部轮次结束后的最终输出中相等元素是否保持初始先后次序来判定的。
| 状态 | 索引0 | 索引1 | 索引2 | 索引3 | 索引4 | 索引5 |
|---|---|---|---|---|---|---|
| 交换前 | 4A | 4B | 3 | 1 | 5 | 2 |
| 首轮交换后 | 1 | 4B | 3 | 4A | 5 | 2 |
首轮在未排序区间 [0, 5] 内定位最小元素 1(索引 3),与索引 0 的 4A 交换。交换后 1 在索引 0 归位,未排序区间缩为 [1, 5];而原本在索引 0 的 4A 直接跨过索引 1 的 4B 落到索引 3,使两个 4 在首轮后出现中间逆序。图中仅展示这第一轮,未画出后续轮次。
图示的首轮逆序只是中间状态。按本节代码严格小于的比较规则继续,第二轮将索引 1 的 4B 与索引 5 的 2 交换,完整排序最终得到 [1, 2, 3, 4A, 4B, 5],两个 4 恢复初始先后次序。因此,这张图展示跨位置交换的机制,不能单独证明这个输入最终逆序。补充一个非原图反例:[4A, 4B, 1] 首轮变为 [1, 4B, 4A];第二轮两个 4 相等,严格小于条件不成立,不再交换不同位置,最终仍为 [1, 4B, 4A]。存在这样的输入,就足以说明选择排序不稳定。