第 83 节 · SECTION 83
练习
知识巩固
选择排序和冒泡排序的前几轮
给定数组 [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$ 的数值相同，但用下标标出了原有次序。
- 写出选择排序第一轮结束后的数组。$2_a$ 和 $2_b$ 的相对次序是否改变？
- 写出冒泡排序第一轮结束后的数组。$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 个数位，因此从最低位到最高位共处理 8 轮；每轮只按 0～9 分组。
直接计数需要为所有可能的 8 位取值预留位置，但实际学生只使用其中很少一部分， 大多数计数位置会一直为 0。
应选择基数排序。它利用了“位数固定、每位只有 10 种取值”的特点，只需重复 8 轮稳定分组。 计数排序若把整个 8 位学号当作整数下标，则需要为大量实际不会出现的数值预留计数位置。
编程练习
用归并排序排列数组
给定一个整数数组 nums，请自行实现归并排序，把其中的元素按非递减顺序排列并返回。不要调用语言自带的排序函数。
解题提示
- 区间长度不超过 1 时，它已经有序
- 从中点把区间分成两半，并分别递归排序
- 用两个指针合并两个有序半区，再把结果写回原数组
用计数排序排列整数数组
给定整数数组 nums 和非负整数 $K$，数组中的每个元素都在 $0$ 到 $K$ 之间。
请实现计数排序，把结果按非递减顺序写回 nums 并返回 nums。
不要使用元素之间的大小比较来决定顺序，也不要调用语言自带的排序函数。
解题提示
- 因为每个元素都在 0 到 K 之间，可以直接用元素值作为计数数组的索引
- 第一遍扫描 nums，令对应位置的计数加 1
- 再从 0 到 K 扫描计数数组；数值 x 出现多少次，就向 nums 中连续写入多少个 x