30.基数排序¶

在本章中，你将看到一个完全不同的排序模型。到目前为止，你一直在依靠比较来决定排序的顺序。

Radix sort是一种在线性时间内对整数进行排序的非比较算法。基数排序有多种实现方式，主要针对不同的问题。

为了简单起见，在本章中，你将重点研究基数为10的整数的排序，同时研究radix sort的最小有效数字(LSD)变体。

示例¶

为了说明基数排序的工作原理，你将对以下数组进行排序：

var array = [88, 410, 1772, 20]

Radix排序依赖于整数的位置符号，如图所示：

首先，数组根据最小有效数字的值被分成几个桶：ones数字。

然后，这些桶被按顺序清空，产生了以下部分排序的数组：

array = [410, 20, 1772, 88]

接下来，对tens的数字重复这一程序。

这次元素的相对顺序没有改变，但你仍然有更多的数字需要检查。

下一个要考虑的数字是hundreds数字：

对于没有百位的数值（或任何其他没有数值的位置），数字将被假定为zero。

在这些桶的基础上对数组进行重新组合，得到以下结果：

array = [20, 88, 410, 1772]

最后，你需要考虑thousands这个数字：

从这些桶中重新组合数组，就可以得到最终的排序数组：

array = [20, 88, 410, 1772]

当多个数字最终出现在同一个桶里时，它们的相对顺序不会改变。例如，在百位的零桶中，20排在88之前。这是因为上一步把20放在比80低的桶里，所以在数组中20最后排在88之前。

实施¶

打开本章的启动项目。在Sources目录下，创建一个名为RadixSort.swift的新文件。

在该文件中加入以下内容：

extension Array where Element == Int {

  public mutating func radixSort() {

  }
}

在这里，你通过一个扩展为整数数组添加了一个radixSort方法。用下面的方法开始实现radixSort方法：

public mutating func radixSort() {
  // 1
  let base = 10
  // 2
  var done = false
  var digits = 1
  while !done {

  }
}

这个位子相对来说是比较简单的：

在这个例子中，你要对基数为10的整数进行排序。因为你将在算法中多次使用这个值，所以你将它存储在一个常数base中。
你声明两个变量来跟踪你的进度。Radix排序是分多次进行的，所以done作为一个标志，决定了排序是否完成。digits变量记录了你正在查看的当前数字。

接下来，你将写出将每个元素分到桶中的逻辑(也称为Bucket sort)。

桶式排序¶

在while循环中写下以下内容inside：

// 1
var buckets: [[Int]] = .init(repeating: [], count: base)
// 2
forEach {
  number in
  let remainingPart = number / digits
  let digit = remainingPart % base
  buckets[digit].append(number)
}
// 3
digits *= base
self = buckets.flatMap { $0 }

下面是你写的内容：

你用一个二维数组来实例化这些桶。因为你使用的是基数10，所以你需要十个桶。
你把每个数字放在正确的桶里。
你将digits更新为你想检查的下一个数字，并使用buckets的内容更新数组。flatMap将把二维数组平移为一维数组，就像你把桶里的东西倒入数组一样。

你什么时候停止?¶

你的while循环目前一直在运行，所以你需要在某个地方设置一个终止条件。你将按以下方式进行。

在while循环的开头，添加done = true。
在forEach的闭包中，添加以下内容：

if remainingPart > 0 {
  done = false
}

由于forEach遍历了所有的整数，只要其中一个整数仍有未排序的数字，你就需要继续排序。

就这样，你已经了解了你的第一个非比较性排序算法! 回到playground页面，写下以下内容，试试你的代码：

example(of: "radix sort") {
  var array = [88, 410, 1772, 20]
  print("Original array: \(array)")
  array.radixSort()
  print("Radix sorted: \(array)")
}

你应该看到以下控制台输出：

---Example of: radix sort---
Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]

弧形排序是最快的排序算法之一。径向排序的平均时间复杂度为O(k×n)，其中k是最大数字的有效位数，n是数组中的整数数。

当k为常数时，Radix排序效果最好，这发生在数组中的所有数字都有相同的有效数字。它的时间复杂度就变成了O(n)。径向排序也会产生O(n)空间复杂度，因为你需要空间来存储每个桶。

关键点¶

与你在前一章所做的其他搜索不同，拉德值排序是非比较性的，不依赖于比较两个值。基数排序利用了桶状排序，它就像一个筛子，用于过滤掉数值。一个有用的比喻是一些自动售货机如何接受硬币--硬币是按大小区分的。
弧形排序可以说是用位置符号对数值进行排序的最快的排序算法之一。
本章介绍了least significant digit的拉德值排序。另一种实现径向排序的方法是most significant digit形式。这种形式通过优先考虑最重要的数字而不是较小的数字来进行排序，最好的例子是String类型的排序行为。