线性排序
时刻复杂度是线性的，所以咱们把这类排序算法叫作线性排序（Linear sort），桶排序、计数排序、基数排序便是常见的线性排序，之所以能做到线性，他们不是经过比较完结的。
桶排序（Bucket sort）
桶排序对于排序数据的要求是十分严苛的。
核心思维是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据依照顺序顺次取出，组成的序列便是有序的了。
假如要排序的数据有 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)。
为什么严苛呢？
- 要排序的数据需求很容易就能划分红 m 个桶，并且，桶与桶之间有着天然的巨细顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需求再进行排序。
- 数据在各个桶之间的散布是比较均匀的。假如数据经过桶的划分之后，有些桶里的数据十分多，有些十分少，很不均匀，那桶内数据排序的时刻复杂度就不是常量级了。在极点情况下，假如数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。
桶排序一般适用于外部排序，开发中根本用不到
计数排序（Counting sort）
计数排序其实是桶排序的一种特殊情况
上面的结论是桶排序在开发中根本不必，为什么还要学习计数排序呢？
当要排序的 n 个数据，地点的范围并不大的时分，比方最大值是 k，咱们就能够把数据划分红 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时刻。
高考查分数体系你还记得吗？咱们查分数的时分，体系会显现咱们的成果以及地点省的排名。假如你地点的省有 50 万考生，怎么经过成果快速排序得出名次呢？考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以咱们能够分红 901 个桶，对应分数从 0 分到 900 分。依据考生的成果，咱们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需求再进行排序。咱们只需求顺次扫描每个桶，将桶内的考生顺次输出到一个数组中，就完成了 50 万考生的排序。由于只触及扫描遍历操作，所以时刻复杂度是 O(n)。
计数排序的算法思维便是这么简略，跟桶排序十分类似，只是桶的巨细粒度不一样。
它的核心点在于“计数”
经过一个例子来阐明何为计数.
假设只要 8 个考生，分数在 0 到 5 分之间， 考生成果如下：
记为：
//考生成果
examineeScore = [1, 5, 2, 0, 1, 3, 0, 3]
然后咱们把考生的成果依照分数分为6个桶, 数组下标表示分数
score = [size=6]
比方： socre = [2,1]
下标为0: 则0分的有两人
此时咱们遍历一遍考生成果就能够得到成果对应人个数的数组
for (i in examineeScore.indices) {
// socre[examineeScore[i]] = socre[examineeScore[i]] + 1
// 简化：
socre[examineeScore[i]]++
}
res:[2, 2, 1, 2, 0, 1]
个数有了，怎么进行排序呢？
这里有一个程式的技能点：
- 对 socre[6]数组顺序求和，socre[6]存储的数据就变成了下面这样子。socre[k]里存储小于等于分数 k 的考生个数。
[2, 4, 5, 7, 7, 8]
详细核算为：
2 + 2 + 1 + 2 + 0 + 1
2。 4。 5。 7。 7。 8。
比方socre[3] 里面的数据5，表示小于等于3分的人有5个 （[1, 5, 2, 0, 1, 3, 0, 3]）
- 对带排序数组进行处理
比方，当扫描到 3 时，咱们能够从数组 socre 中取出下标为 3 的值 7，也便是说，到目前为止，包含自己在内，分数小于等于 3 的考生有 7 个，也便是说 3 是排序后的数组中的第 7 个元素（也便是下标为 6 的方位）。当 3 放入到排序后的数组中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 socre[3]要减 1，变成 6。
执行流程如下：
注意红色箭头的变化，便是上述描述的（所以相应的 socre[3]要减 1，变成 6）部分
详细代码
private fun countSort(arr: IntArray, count: IntArray) {
for (i in arr.indices) {
count[arr[i]]++
}
var sum = 0
for (i in count.indices) {
print("${count[i]} \t")
sum += count[i]
count[i] = sum
}
println("计数数组 = ${Arrays.toString(count)}\n")
for (i in arr.size - 1 downTo 0) {
result[count[arr[i]] - 1] = arr[i]
//2,2,4,7,7,8
println(
"数组下标为${arr[i]}的值${count[arr[i]]} --> 也便是分数小于等于${arr[i]}的人有${count[arr[i]]}个 --> ${
Arrays.toString(
result
)
} \t"
)
count[arr[i]]--
println("count 变为 ${Arrays.toString(count)}")
}
}
计数排序只能用在数据范围不大的场景中，假如数据范围 k 比要排序的数据 n 大许多，就不合适用计数排序了。并且，计数排序只能给非负整数排序，假如要排序的数据是其他类型的，要将其在不改变相对巨细的情况下，转化为非负整数.
