计数、桶、基数

桶排序（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++
          }
      }
  }