基数排序

8/17/2020 数据结构与算法基础

# 基数排序

基数排序(Radix sort)是一种非比较型整数排序算法,时间复杂度是 O(n) 。

754476-6bf41f1ec1fdb8b4

# 思路

它的主要思路是:

  1. 将所有待排序整数(注意,必须是非负整数)统一为位数相同的整数,位数较少的前面补零。一般用 10 进制,也可以用 16 进制甚至 2 进制。所以前提是能够找到最大值,得到最长的位数,设 k 进制下最长为位数为 d。
  2. 从最低位开始,依次进行一次稳定排序。这样从最低位一直到最高位排序完成以后,整个序列就变成了一个有序序列。

# 代码

// 不能处理负数
func radixSort(_ array: inout [Int] ) {
  let radix = 10  //在这里我们定义基数为10
  var done = false
  var index: Int
  var digit = 1  // 我们在哪个位数上

  while !done {
    done = true  // 假设现在完成
    var buckets: [[Int]] = []  // 我们的排序子程序是桶排序,所以让我们预定义我们的桶
    for _ in 1...radix {
      buckets.append([])
    }

    for number in array {
      index = number / digit  // 我们将访问哪个桶?
      buckets[index % radix].append(number)

      if done && index > 0 {  // If we arent done, continue to finish, otherwise we are done
        done = false
      }
    }

   /// 输出
    var i = 0
    for j in 0..<radix {
      let bucket = buckets[j]
      for number in bucket {
        array[i] = number
        i += 1
      }
    }

    digit *= radix  // 下一位
  }
}
上次更新: 6/18/2022, 10:39:15 AM