31.基数排序挑战¶

挑战1：最有意义的数字¶

打开本章的启动playground，开始。

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

这种排序行为被称为lexicographical sorting，也被用于String的排序。

比如说：

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 radix sort中，你只用整个数组运行一次bucket sort。随后的传递将对每个桶进行递归排序。

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

`Digits`¶

在你的Playground页面内添加以下内容：

extension Int {

  var digits: Int {
    var count = 0
    var num = self
    while num != 0 {
      count += 1
      num /= 10
    }
    return count
  }

  func digit(atPosition position: Int) -> Int? {
    guard position < digits else {
      return nil
    }
    var num = self
    let correctedPosition = Double(position + 1)
    while num / Int(pow(10.0, correctedPosition)) != 0 {
      num /= 10
    }
    return num % 10
  }
}

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

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

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

字典排序¶

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

extension Array where Element == Int {

  mutating func lexicographicalSort() {
    self = msdRadixSorted(self, 0)
  }

  private func msdRadixSorted(_ array: [Int], _ position: Int) -> [Int] {
    // more to come...
  }
}

lexicographicalSort是面向用户的MSD径向排序的API。msdRadixSorted是算法的肉，将用于对数组递归地应用MSD径向排序。

更新msdRadixSorted为以下内容：

private func msdRadixSorted(_ array: [Int], _ position: Int) -> [Int] {

  // 1
  var buckets: [[Int]] = .init(repeating: [], count: 10)
  // 2
  var priorityBucket: [Int] = []

  // 3
  array.forEach { number in
    guard let digit = number.digit(atPosition: position) else {
      priorityBucket.append(number)
      return
    }
    buckets[digit].append(number)
  }

  // more to come...
}

与LSD基数排序类似，你为桶实例化了一个二维数组。
priorityBucket是一个特殊的桶，用来存储比当前位置数字少的值。放入priorityBucket的值将被首先排序。
对于数组中的每一个数字，你要找到当前位置的数字，并将其放入相应的桶中。

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

priorityBucket.append(contentsOf: buckets.reduce(into: []) {
  result, bucket in
  guard !bucket.isEmpty else {
    return
  }
  result.append(contentsOf: msdRadixSorted(bucket, position + 1)
})

return priorityBucket

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

基本案例¶

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

在Array扩展的顶部，写上以下内容：

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

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

guard position < array.maxDigits else {
  return array
}

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

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

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

你应该看到一个与此类似的随机数组：

[1350975449, 1412970969, 1727253826, 2003696829, 2281464743, 2603566662, 3012182591, 3552993620, 3665442670, 4167824072, 465277276]

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