跳转至
纸质书已发行，详情请见这里

# 11.12 练习

## 11.12.1 知识巩固

### 1. 选择排序和冒泡排序的前几轮

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

1. 按选择排序模拟前两轮，写出每轮结束后的数组，并指出此时哪些位置已经确定。
2. 按冒泡排序模拟第一轮，写出数组状态和交换次数，并指出哪个位置已经确定。

参考答案

1. 前两轮为：

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

   此时前两个位置已经确定，后续只需在 `[5, 4, 3]` 中继续选择最小元素。

2. 依次比较相邻元素：4 与 2 交换、4 与 5 不换、5 与 1 交换、5 与 3 交换， 得 `[2, 4, 1, 3, 5]` ，共 3 次交换；最大元素 5 已移动到数组末尾，因此最后一个位置已经确定。

### 2. 相同元素的先后次序会变吗

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

1. 写出选择排序第一轮结束后的数组。\(2_a\) 和 \(2_b\) 的相对次序是否改变？
2. 写出冒泡排序第一轮结束后的数组。\(2_a\) 和 \(2_b\) 的相对次序是否改变？
3. 根据前两问，说明两种排序在保持相等元素原有次序方面有什么不同。

参考答案

1. 选择排序第一轮选出最小元素 1，并与首位 \(2_a\) 交换，得 \([1, 2_b, 2_a]\) 。\(2_a\) 被换到了 \(2_b\) 之后，两者的相对次序已经改变。

2. 冒泡排序先比较 \(2_a\) 和 \(2_b\)，因为两者相等，不交换；再比较 \(2_b\) 和 1 并交换， 第一轮结束后为 \([2_a, 1, 2_b]\) 。\(2_a\) 仍在 \(2_b\) 之前，相对次序没有改变。

3. 这个例子中，选择排序会改变相等元素的原有次序；冒泡排序只在左边元素大于右边元素时 交换相邻元素。相等元素之间不交换，因此能保持它们原有的先后次序。

### 3. 比较计数排序和基数排序

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

1. 从最低位开始的基数排序需要处理几轮？
2. 如果把学号直接当作整数使用计数排序，为什么会准备大量没有用到的计数位置？
3. 根据前两问，如果在计数排序和基数排序之间选择一种处理大量固定为 8 位的学号，你会选择哪一种？为什么？

参考答案

1. 学号有 8 个数位，因此从最低位到最高位共处理 8 轮；每轮只按 0～9 分组。

2. 直接计数需要为所有可能的 8 位取值预留位置，但实际学生只使用其中很少一部分， 大多数计数位置会一直为 0。

3. 应选择基数排序。它利用了“位数固定、每位只有 10 种取值”的特点，只需重复 8 轮稳定分组。 计数排序若把整个 8 位学号当作整数下标，则需要为大量实际不会出现的数值预留计数位置。

## 11.12.2 编程练习

### 1. 用归并排序排列数组

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

解题提示

1. 区间长度不超过 1 时，它已经有序
2. 从中点把区间分成两半，并分别递归排序
3. 用两个指针合并两个有序半区，再把结果写回原数组

LeetCode

### 2. 用计数排序排列整数数组

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

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

解题提示

1. 因为每个元素都在 0 到 K 之间，可以直接用元素值作为计数数组的索引
2. 第一遍扫描 nums，令对应位置的计数加 1
3. 再从 0 到 K 扫描计数数组；数值 x 出现多少次，就向 nums 中连续写入多少个 x

##### 欢迎在评论区留下你的见解、问题或建议