桶排序、计数排序、基数排序算法
这3种排序通常都算作是一类排序算法，他们不像选择、冒泡、归并、快排之类的是基于比较来排序的。
1. 桶排序
以一个例子来说明：有一个数组为 [3, 4, 4, 7, 9, 1, 8, 1]，我们能找到其中最小值为 min = 1，其中最大值为 max = 9，如果每个桶只装 2 种不同的数据(同种数据可以有多个)，那么需要定义 (max - min) / 2 + 1 = 5 个桶，这5个桶按顺序只能装这样子的数据：[1, 2]、[3, 4]、 [5, 6]、 [7, 8]、 [9]。也就是说第 1 个桶只装 1 和 2，第 2 个桶只装 3 和 4，依次类推。遍历一遍数组，将数据分别装入到对应的桶中，这5个桶内的实际数据应该为：[1, 1]、[3, 4, 4]、[ ]、[7, 8]、[9]，第 3 个桶是空桶。接着我们对每个桶排序，排好序之后，这 5 个桶按顺序合起来就是排好序的数据了。
代码如下（kotlin编写）：
/**
* @param array 待排序数组
* @param bucketSize 桶的个数
*/
private fun bucketSort(array: Array<Int>, bucketSize: Int) {
if (array.size <= 1 || bucketSize < 1)
return
//找出最大值、最小值
var min = array[0]
var max = array[0]
for (item in array) {
if (item > max) {
max = item
} else if (item < min) {
min = item
}
}
//定义桶
var bucketList = ArrayList<ArrayList<Int>>(bucketSize)
for (i in 0 until bucketSize) {
bucketList.add(ArrayList())
}
//每个桶数字的间隔区间
var section = (max - min + 1) / bucketSize
if (section == 0)
section = 1
//遍历数据，放到对应桶中
for (i in array.indices) {
var bucketIndex = (array[i] - min) / section
if (bucketIndex >= bucketList.size)
bucketIndex = bucketList.size - 1
var list = bucketList[bucketIndex]
list.add(array[i])
}
for (i in bucketList.indices) {
val itemList = bucketList[i]
if (itemList.size <= 1)
continue
var arr: Array<Int> = itemList.toTypedArray()
//数据少的话，直接使用插入排序，也可选择其他如快排，不会有太大区别
insertSort(arr)
itemList.clear()
for (item in arr) {
itemList.add(item)
}
}
var i = 0
for (itemList in bucketList) {
for (item in itemList) {
array[i++] = item
}
}
}
桶排序有很多局限性，它一般应用在特殊的场合下，桶大小的分配会影响到排序的性能。
桶排序是否稳定，要看桶内部的排序用什么算法。
其空间复杂度为：其时间复杂度与桶的个数有关，桶越多的情况下，其时间复杂度接近 O(n)
2. 计数排序
计数排序有 2 个基本条件：
- 计数排序不能有负数，如果有负数，可以统一加上一个正数之后，将所有数都转换为大于等于 0 的数，排好序之后再减去之前加的正数；
- 计数排序里的最大数不宜过大，否则会比较浪费空间；
计数排序过程图.png
具体逻辑，还是看代码比较清楚：
/**
* 计数排序，待排序数组不能有负整数，如果有则需要将数据处理成非负整数
*/
fun countingSort(array: IntArray?) {
array ?: return
if (array.size <= 1)
return
//查找最大值
var max = array[0]
for (item in array) {
if (max < item) max = item
}
//定义计数数组 [0, max]，大小为 max + 1，
var countingArr = Array(max + 1) { 0 }
//遍历数组，统计每个数字的个数，例如数字 1 的个数存储在 countingArr[1] 中
//统计结束之后，countingArr[i] 表示数字 i 在数组中的个数
for (item in array) {
countingArr[item]++
}
//计数数组依次累加，累加后对计数数组来说， countingArr[i] 存储的是 <= i 的数据的个数
//其实这是构造一个前缀和数组
for (i in 0 until countingArr.size - 1) {
countingArr[i + 1] = countingArr[i + 1] + countingArr[i]
}
//申请一个临时数组，大小与待排序数组一样大
var tmpArr = Array(array.size) { 0 }
//将每个元素 num 放在新数组的第 countingArr[num] 项，每放一个元素就将 countingArr[num] 减去1。
//假设countingArr[num] = c, 则表示原数组中 <= num 的元素个数有 c 个，我们想象一下如果将原数组排好序之后
//则排好序的数组中索引为 c-1 的数肯定为 num
for (num in array) {
tmpArr[countingArr[num] - 1] = num
countingArr[num]--
}
//从排好序的数组拷贝数据到原数组里
for (i in tmpArr.indices) {
array[i] = tmpArr[i]
}
}
计数排序是稳定的
空间复杂度：O(n + k)，k 为最大数的值
时间复杂度：O(n + k)，k 为最大数的值，当 k 比较小时，其复杂度接近于 O(n)
3. 基数排序
通过数据的“位”来进行排序，可以从低位到高位进行排序，也可行从高位到低位进行排序，所有“位”都比较完毕之后，也就排好序了。如果“位”不足，可以补 0 或者其他。举个例子：
待排序数据列：178、50、34、1、8、251
比较个位：50、1、251、34、178、8
比较十位：1、8、34、50、251、178
比较百位：1、8、34、50、178、251
最后排序完成，代码如下：
/**
* 基数排序
*/
fun radixSort(array: IntArray?) {
array ?: return
if (array.size <= 1)
return
//查找最大值
var max = array[0]
for (item in array) {
if (max < item) max = item
}
//计算最大值的位数，例如 max = 148，则位数为 3
var maxDigit = 0
while (max != 0) {
maxDigit++
max /= 10
}
//每位的数字范围是[0-9]，所以桶的大小设置成 10
val bucketList = ArrayList<ArrayList<Int>>(10)
for (i in 0 until 10) {
bucketList.add(ArrayList())
}
//从低位到高位开始排序，这里采用桶排序
var mod = 10
var divide = 1
//每位都进行一次桶排序
for (i in 0 until maxDigit) {
//遍历数据，根据"位"来判断数据放在哪个桶中
for (j in array.indices) {
val item = array[j]
//取出数字的"位"，例如 158 的个位为：(158 % 10) / 1 = 8
//158 的十位为：(158 % 100) / 10 = 5
//158 的百位为：(158 % 1000) / 100 = 1
val num = (item % mod) / divide
bucketList[num].add(item)
}
//从桶中取出数据放在原数组中，同一个桶中存储的是“位”相同的数据
var index = 0
for (list in bucketList) {
for (item in list) {
array[index++] = item
}
list.clear()
}
mod *= 10
divide *= 10
}
}
基数排序也是稳定的排序方式
空间复杂度：O(n)
时间复杂度：O(k * n)，当 k 不大时，其复杂度接近于 O(n)
