第31章：基数排序进阶

挑战1：最重要的数字

打开本章的启动游戏，开始。

本章讨论的实现方法采用了最小有效数字的小数点阵。你的任务是实现一个最重要数字的小数点排序。

这种排序行为被称为基数排序，也被用于字符串排序。

比如说。

var array = [500, 1345, 13, 459, 44, 999]
array.lexicographicalSort() 
print(array) // outputs [13, 1345, 44, 459, 500, 999]

挑战1的解决方案

MSD 弧度排序与 LSD 弧度排序密切相关，两者都利用桶状排序。不同的是，MSD 弧度排序需要精心策划后续的桶式排序过程。在LSD弧度排序中，桶状排序重复运行，每次都使用整个数组。在MSD径向排序中，你只用整个数组运行一次桶状排序。随后的传递将对每个桶进行递归排序。

你将逐个实现 MSD 径向排序，从它所依赖的组件开始。

数字

在你的playground页面中添加以下内容。

digits是一个计算属性，返回Int有多少个数字。例如，值1024有四位数。

digit(atPosition:) 返回指定位置的数字。和数组一样，最左边的位置是零。因此，1024的第0位的数字是1，第3位的数字是4，由于只有四个数字，第5位的数字将返回nil。

digit(atPosition:)的实现是通过重复地从数字的末尾砍掉一个数字，直到要求的数字在末尾。然后用余数运算符将其提取出来。

词典排序

有了这些辅助方法，你现在已经具备了处理MSD词缀排序的能力。在playground的底部写上以下内容。

msdRadixSorted是算法的主要部分，将用于对数组递归地应用MSD弧度排序。

将msdRadixSorted更新为以下内容。

1. 与LSD弧度排序类似，你为桶实例化了一个二维数组。

2. priorityBucket是一个特殊的桶，用来存储比当前位置数字少的值。放入priorityBucket的值将被优先排序。

3. 对于数组中的每一个数字，你要找到当前位置的数字，并将该数字放入适当的桶中。

接下来，你需要递归地对每个单独的桶应用MSD径向排序。在msdRadixSorted的末尾写上以下内容。

这个语句调用reduce(into:)来收集递归排序的结果，并将其追加到优先级Bucket中。这样一来，priorityBucket中的元素总是排在第一位。你就快完成了!

基本案例

与所有的递归操作一样，你需要设置一个终止条件来停止递归。如果你正在检查的当前位置大于数组内最大值的有效位数，递归就应该停止。

在数组扩展的顶部，写上以下内容。

private var maxDigits: Int { 
  self.max()?.digits ?? 0 
}

接下来，在msdRadixSorted的顶部添加以下内容。

guard position < array.maxDigits else { 
  return array 
}

这个检查确保如果位置等于或大于数组的maxDigits，你将终止递归。

让我们把它拿出来转转吧! 在playground的底部添加以下内容来测试代码。

var array: [Int] = (0...10).map { _ in Int(arc4random()) } 
array.lexicographicalSort() 
print(array)

你应该看到一个类似这样的随机数数组。

由于数字是随机的，你不会得到一个相同的数组。需要注意的是这些数值的列序。

---

上一章	目录	下一章