11.12 练习¶

11.12.1 知识巩固¶

给定数组 [4, 2, 5, 1, 3]，以下都按从小到大排序。

参考答案

前两轮为：

轮次数组状态说明

1 [1, 2, 5, 4, 3] 最小元素 1 与首位交换

2 [1, 2, 5, 4, 3] 数值 2 已位于索引 1，无须交换

此时前两个位置已经确定，后续只需在 [5, 4, 3] 中继续选择最小元素。
依次比较相邻元素：4 与 2 交换、4 与 5 不换、5 与 1 交换、5 与 3 交换，得 [2, 4, 1, 3, 5] ，共 3 次交换；最大元素 5 已移动到数组末尾，因此最后一个位置已经确定。

数组 \([2_a, 2_b, 1]\) 中，\(2_a\) 和 \(2_b\) 的数值相同，但用下标标出了原有次序。

参考答案

选择排序第一轮选出最小元素 1，并与首位 \(2_a\) 交换，得 \([1, 2_b, 2_a]\) 。\(2_a\) 被换到了 \(2_b\) 之后，两者的相对次序已经改变。
冒泡排序先比较 \(2_a\) 和 \(2_b\)，因为两者相等，不交换；再比较 \(2_b\) 和 1 并交换，第一轮结束后为 \([2_a, 1, 2_b]\) 。\(2_a\) 仍在 \(2_b\) 之前，相对次序没有改变。
这个例子中，选择排序会改变相等元素的原有次序；冒泡排序只在左边元素大于右边元素时交换相邻元素。相等元素之间不交换，因此能保持它们原有的先后次序。

学校要排序许多固定为 8 位的学号。请回答：

参考答案

学号有 8 个数位，因此从最低位到最高位共处理 8 轮；每轮只按 0～9 分组。
直接计数需要为所有可能的 8 位取值预留位置，但实际学生只使用其中很少一部分，大多数计数位置会一直为 0。
应选择基数排序。它利用了“位数固定、每位只有 10 种取值”的特点，只需重复 8 轮稳定分组。计数排序若把整个 8 位学号当作整数下标，则需要为大量实际不会出现的数值预留计数位置。

给定一个整数数组 nums，请自行实现归并排序，把其中的元素按非递减顺序排列并返回。不要调用语言自带的排序函数。

解题提示

给定整数数组 nums 和非负整数 \(K\)，数组中的每个元素都在 \(0\) 到 \(K\) 之间。

请实现计数排序，把结果按非递减顺序写回 nums 并返回 nums。不要使用元素之间的大小比较来决定顺序，也不要调用语言自带的排序函数。

解题提示

轮次	数组状态	说明
1	`[1, 2, 5, 4, 3]`	最小元素 1 与首位交换
2	`[1, 2, 5, 4, 3]`	数值 2 已位于索引 1，无须交换