第30章：基数排序

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

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

为了保持简单，在本章中，你将专注于对基数为10的整数进行排序，同时研究radix sort的最小有效数字（LSD）变体。

例子

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

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

径向排序依靠的是整数的位置符号，如图所示。

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

然后按顺序清空这些桶，得到下面这个部分排序的数组。

array = [410, 20, 1772, 88]

接下来，对十位数重复这个程序。

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

下一个要考虑的数字是百位数。

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

根据这些桶来重新组合数组，可以得到以下结果。

array = [20, 88, 410, 1772]

最后，你需要考虑千位数。

从这些桶中重新组合数组，得到最终的排序数组。

array = [20, 88, 410, 1772]

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

实现

打开本章的启动项目。在Source目录下，创建一个名为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的整数进行排序。因为你会在算法中多次使用这个值，所以你把它存储在一个恒定的基数中。
你声明两个变量来跟踪你的进度。Radix排序是分多次进行的，所以完成作为一个标志，决定排序是否完成。digits变量记录了你正在看的当前数字。

接下来，你要写出将每个元素分到桶中的逻辑（也称为桶排序）。

桶排序

在while循环中写下以下内容。

这是你写的东西。

你用一个二维数组来实例化buckets。因为你使用的是基数10，所以你需要十个桶。
你把每个数字放在正确的桶里。
你把数字更新到你想检查的下一个数字，并使用桶的内容更新数组。 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)空间复杂度，因为你需要空间来存储每个桶。

关键点

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

上一章	目录	下一章