桶、计数、基数

约 1748 字大约 6 分钟...

计数、桶、基数

桶排序（Bucket Sort）：

思想：它通过设置一些具有有限数量、大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并
稳定排序、非原地排序，需要借助k个桶和n个元素的数组
非比较排序算法
算法流程：条件一个长度为 $n$ 的数组，其元素是范围 $[0, 1)$ 内的浮点数
1. 初始化 $k$ 个桶，将 $n$ 个元素分配到 $k$ 个桶中。
2. 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。
3. 按照桶从小到大的顺序合并结果。
桶排序的优化：
- 将元素均匀分配到各个桶中，时间复杂度趋近于 $O(n)$ 。可以借助值的概率分布。
图解：

代码：

/* 桶排序 */
func bucketSort(nums []float64) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    k := len(nums) / 2
    buckets := make([][]float64, k)
    for i := 0; i < k; i++ {
        buckets[i] = make([]float64, 0)
    }
    // 1. 将数组元素分配到各个桶中
    for _, num := range nums {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        i := int(num * float64(k))
        // 将 num 添加进桶 i
        buckets[i] = append(buckets[i], num)
    }
    // 2. 对各个桶执行排序
    for i := 0; i < k; i++ {
        // 使用内置切片排序函数，也可以替换成其他排序算法
        sort.Float64s(buckets[i])
    }
    // 3. 遍历桶合并结果
    i := 0
    for _, bucket := range buckets {
        for _, num := range bucket {
            nums[i] = num
            i++
        }
    }
}

计数排序（Counting Sort）：

思想：对于给定的输入序列中的每一个元素，确定小于该元素的元素个数，利用这个信息将该元素直接存放到输出序列的相应位置上。
本质上，计数排序是桶排序在整型数据下的一个特例
稳定排序
非比较排序算法
算法流程：
1. 遍历数组，找出其中的最大数字，记为 $m$ ，然后创建一个长度为 $m + 1$ 的辅助数组 counter 。
2. 借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 $1$ 即可。
3. 由于 counter 的各个索引天然有序，因此相当于所有数字已经排序好了。接下来，我们遍历 counter ，根据各数字出现次数从小到大的顺序填入 nums 即可。
前缀和：
- counter的前缀和计算方法：
  - 索引 i 处的前缀和 prefix[i] 等于数组前 i个元素之和，公式：
  $\text{prefix}[i] = \sum_{j=0}^i \text{counter[j]}$
- 前缀和的具体意义：
  - prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。
  - 它告诉我们各个元素应该出现在结果数组的哪个位置。接下来，我们倒序遍历原数组 nums 的每个元素 num ，在每轮迭代中执行以下两步。
    1. 将 num 填入数组 res 的索引 prefix[num] - 1 处。
    2. 令前缀和 prefix[num] 减小 $1$ ，从而得到下次放置 num 的索引。
图解：
局限性：
- 计数排序只适用于非负整数
- 计数排序适用于数据量大但数据范围较小的情况

代码：

/* 计数排序 */
// 完整实现，可排序对象，并且是稳定排序
func countingSort(nums []int) {
    // 1. 统计数组最大元素 m
    m := 0
    for _, num := range nums {
        if num > m {
            m = num
        }
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    counter := make([]int, m+1)
    for _, num := range nums {
        counter[num]++
    }
    // 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i := 0; i < m; i++ {
        counter[i+1] += counter[i]
    }
    // 4. 倒序遍历 nums ，将各元素填入结果数组 res
    // 初始化数组 res 用于记录结果
    n := len(nums)
    res := make([]int, n)
    for i := n - 1; i >= 0; i-- {
        num := nums[i]
        // 将 num 放置到对应索引处
        res[counter[num]-1] = num
        // 令前缀和自减 1 ，得到下次放置 num 的索引
        counter[num]--
    }
    // 使用结果数组 res 覆盖原数组 nums
    copy(nums, res)
}

基数排序（Radix Sort）：

核心思想与计数排序一致，也通过统计个数来实现排序。将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次按照每个位上的数值进行排序。
稳定排序、非就地排序
非比较排序算法
算法流程：
1. 初始化位数 $k = 1$ 。
2. 对学号的第 $k$ 位执行“计数排序”。完成后，数据会根据第 $k$ 位从小到大排序。
3. 将 $k$ 增加 $1$ ，然后返回步骤 2. 继续迭代，直到所有位都排序完成后结束。

代码：

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
func digit(num, exp int) int {
    // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num / exp) % 10
}

/* 计数排序（根据 nums 第 k 位排序） */
func countingSortDigit(nums []int, exp int) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
    counter := make([]int, 10)
    n := len(nums)
    // 统计 0~9 各数字的出现次数
    for i := 0; i < n; i++ {
        d := digit(nums[i], exp) // 获取 nums[i] 第 k 位，记为 d
        counter[d]++             // 统计数字 d 的出现次数
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for i := 1; i < 10; i++ {
        counter[i] += counter[i-1]
    }
    // 倒序遍历，根据桶内统计结果，将各元素填入 res
    res := make([]int, n)
    for i := n - 1; i >= 0; i-- {
        d := digit(nums[i], exp)
        j := counter[d] - 1 // 获取 d 在数组中的索引 j
        res[j] = nums[i]    // 将当前元素填入索引 j
        counter[d]--        // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for i := 0; i < n; i++ {
        nums[i] = res[i]
    }
}

/* 基数排序 */
func radixSort(nums []int) {
    // 获取数组的最大元素，用于判断最大位数
    max := math.MinInt
    for _, num := range nums {
        if num > max {
            max = num
        }
    }
    // 按照从低位到高位的顺序遍历
    for exp := 1; max >= exp; exp *= 10 {
        // 对数组元素的第 k 位执行计数排序
        // k = 1 -> exp = 1
        // k = 2 -> exp = 10
        // 即 exp = 10^(k-1)
        countingSortDigit(nums, exp)
    }
}