O(n)

排序系列文章链接：

O(n^2) (Jul 16, 2021)
O(nlogn) (Jul 16, 2021)
O(n) (Jul 16, 2021)
二分查找 (Jul 16, 2021)

桶排序

将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序的时间复杂度为什么是 O(n) 呢？

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。
每个桶内部使用快速排序，时间复杂度为 O(k * logk)。
m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。
当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

// 获取待排序数组中的最大值
func getMax(a []int)int{
    max := a[0]
    for i:=1; i<len(a); i++{
        if a[i] > max{
            max = a[i]
        }
    }
    return max
}

func BucketSort(a []int)  {
    num := len(a)
    if num <= 1{
        return
    }
    max := getMax(a)
    buckets := make([][]int, num)  // 二维切片

    index :=0
    for i:=0; i< num; i++{
        index = a[i]*(num -1) / max  // 桶序号
        buckets[index] = append(buckets[index],a[i]) // 加入对应的桶中
    }

    tmpPos := 0  // 标记数组位置
    for i := 0; i < num; i++ {
        bucketLen := len(buckets[i])
        if bucketLen > 0{
            Sort.QuickSort(buckets[i])  // 桶内做快速排序
            copy(a[tmpPos:], buckets[i])
            tmpPos += bucketLen
        }
    }

}

桶排序看起来很优秀，那它是不是可以替代我们之前讲的排序算法呢？

答案当然是否定的。桶排序对要排序数据的要求是非常苛刻的。
首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。
- 这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。
- 如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。
- 在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。
桶排序比较适合用在外部排序中。
- 我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？
- 我们可以先扫描一遍文件，看订单金额所处的数据范围。
- 确定桶的大小，把数据范围划分为多个等长的桶。
- 如果某个桶的数据过多，就对这个桶单独进行细分。

计数排序(counting sort)

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

高考查分系统，如何根据一个学生的分数查询对应的排名:

考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。
根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。
桶内的数据都是分数相同的考生，所以并不需要再进行排序。
我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。
因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

不过，为什么这个排序算法叫“计数”排序呢？“计数”的含义来自哪里呢？

假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8]中，它们分别是：2，5，3，0，2，3，0，3。
考生的成绩从 0 到 5 分，我们使用大小为 6 的数组 C[6]表示桶，其中下标对应分数。不过，C[6]存储的并不是考生，而是对应的考生个数。
```
C[6] [2][0][2][3][0][1]
      0  1  2  3  4  5
```

将这些考生按成绩排序之后可以得到有序数组 R[8]：

     |- lt 3   -||- eq 3-|
R[8] [0][0][2][2][3][3][3][5]
      0  1  2  3  4  5  6  7

如何根据C[6]数组计算出R[8]
- 对 C[6]数组顺序求和，C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数 k 的考生个数：
```
C[6] [2][2][4][7][7][8]
      0  1  2  3  4  5
```
  - 数组的下标表示A数组的值，数组的值表示A数组的值在排好序的数组R的位置。
  - 数组的值每被用一次，都要减一。
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
而且，计数排序只能给非负整数排序(因为数组的下标是非负整数)。

func CountingSort(a []int, n int) {
    if n <= 1 { return }

    // 查找数组中数据的范围
    var max int = math.MinInt32
    for i := range a {
        if a[i] > max {
            max = a[i]
        }
    }

    c := make([]int, max+1)
    // 计算每个元素的个数，放入c中
    for i := range a {
        c[a[i]]++
    }
    // 依次累加
    for i := 1; i <= max; i++ {
        c[i] += c[i-1]
    }

    // 临时数组r，存储排序之后的结果
    r := make([]int, n)
    // 计算排序的关键步骤，有点难理解
    for i := n - 1; i >= 0; i-- {
        index := c[a[i]] - 1
        r[index] = a[i]
        c[a[i]]--
    }

    // 将结果拷贝给a数组
    copy(a, r)
}

基数排序(Radix sort)

基数排序对要排序的数据是有要求的

需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。
每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

以手机号排序为例介绍基数排序的过程：

先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。
经过 11 次排序之后，手机号码就都有序了。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。
- 因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
根据每一位来排序，可以使用时间复杂度为O(n)的桶排序或者计数排序。
- 如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。