排序-4-计数排序
快速排序、堆排序这样时间复杂度为O(nlogn)的算法已经很快了，但是事实上还存在更快的排序算法，在理想的情况下，某些算法甚至可以做到线性的时间复杂度，例如：计数排序、桶排序、基数排序
例如冒泡排序、堆排序、快速排序都是基于元素之间的比较来进行排序的，但是以计数排序来说，这种排序算法是基于元素的下标来确定元素位置的
初识计数排序
假设数组中有20个随机整数，取值范围为 0 - 10，
1. 则可以根据这个有限的范围建立一个长度为 11 的统计数组，数组下标从 0 - 10，元素初始值全为 0
2. 遍历这个无序随机数组，每一个整数按照其值对应的统计数组下标元素加 1
3. 遍历统计数组，其下标代表无序随机数组中的元素，其value代表该元素出现的次数
代码如下:
function countSort(arr: Array<number>):Array<number> {
// 1. 拿到数列的最大值
let max = arr[0];
for (let index = 1; index < arr.length; index++) {
if(arr[index] > max) {
max = arr[index]
}
}
// 2. 根据最大值确定统计数组长度
let countArray = (new Array(max + 1)).fill(0);
// 3. 遍历无序数组 填充统计数组
for (let index = 0; index < arr.length; index++) {
countArray[arr[index]]++
}
// 遍历统计数组输出结果
let sortedArray = new Array();
for (let index = 0; index <= countArray.length; index++) {
for (let j = 0; j < countArray[index]; j++) {
sortedArray.push(index)
}
}
return sortedArray
}
function main() {
let arr = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10];
console.log(countSort(arr))
}
main()
优化1
问题：只以最大值决定数列长度并不严谨，例如以下数列：
95, 94, 91, 98, 99, 90, 99, 93, 91, 92
这时 最大值是 99，最小值是 90，如果创建长度为 100 的数组，那么从 0 到 89 的空间位置都浪费了
解决：以数列 最大值 - 最小值 + 1 作为长度即可，同时，数列最小值作为一个偏移量，用作计算整数在统计数组中的下标
代码如下：
function countSort(arr: Array<number>) {
// 1. 拿到最大值和最小值
let max = arr[0];
let min = arr[0];
for (let index = 1; index < arr.length; index++) {
if(arr[index] > max) {
max = arr[index]
}
if(arr[index] < min) {
min = arr[index]
}
}
// 2. 根据最大值和最小值确定数组长度
let length = max - min + 1;
let countArray = (new Array(length)).fill(0)
// 3. 统计对应元素个数
for (let index = 0; index < arr.length; index++) {
countArray[arr[index] - min]++
}
// 4. 遍历统计数组 输出结果
let sortedArray = []
for (let index = 0; index < countArray.length; index++) {
for (let j = 0; j < countArray[index]; j++) {
sortedArray.push(index + min)
}
}
return sortedArray
}
function main() {
let arr = [95, 94, 91, 98, 99, 90, 99, 90, 99, 93, 91, 92];
console.log(countSort(arr))
}
main()
优化2
如果只是单纯地给整数排序，这样的做法并没有问题，但是如果在现实业务中，例如给学生的考试分数进行排序，遇到相同的分数就会分不清谁是谁
如下例子：
给出学生成绩表，要求按照成绩从低到高排序，如果成绩相同，则遵循原表固有顺序，那么当我们填充统计数组之后，只知道有两个并列成绩为 95 的同学，却不知道哪一个是 小红，哪一个是小绿
解决方法：
1. 首先将统计数组变形为如下：
变形的方法为 从数组第二个元素开始，每一个元素都加上前边所有元素之和
这样做的目的是让统计数组中储存的元素值，等于相应整数最终排序位置的序号
2. 创建 sortedArray 数组，长度和输入数列一致，然后从后往前遍历输入数列，
遍历成绩表最后一名 小绿 的成绩，成绩为 95，找到下标为 5 的元素，值为 4，代表小绿的成绩排在第 4 位，同时给统计数组下标识 5 的元素值减 1，从 4 变成 3，代表下次再遇到 95 分成绩时，排在第 3 位，
遍历成绩表倒数第二名，小白的成绩 94，找到统计数组下标为 4 的元素，值为 2，代表小白的成绩排在第 2 位，同时统计数组下标为 4 的元素减 1，从 2 变为 1，代表下次再遇到 94 分成绩的排在第 1 位(实际已经遇不到了)
遍历成绩表倒数 第三名，小红同学的成绩，操作同上，排在第 3 位，统计数组下标为 5 的元素值减 1
这样一来，同样分数的同学就能按照原有的顺序排序了，也正是因此，优化版本的计数排序属于稳定排序
代码如下:
function countSort(arr: Array<number>) {
// 1. 拿到最大值和最小值
let max = arr[0];
let min = arr[0];
for (let index = 1; index < arr.length; index++) {
if(arr[index] > max) {
max = arr[index]
}
if(arr[index] < min) {
min = arr[index]
}
}
// 2. 根据最大值和最小值确定数组长度
let length = max - min + 1;
let countArray = (new Array(length)).fill(0)
// 3. 统计对应元素个数
for (let index = 0; index < arr.length; index++) {
countArray[arr[index] - min]++
}
// 4. 统计数组做变形 后边元素值为前边元素值之和
for (let index = 1; index < countArray.length; index++) {
countArray[index] += countArray[index - 1]
}
// 5. 倒序遍历原数组，从统计数组中找到位置，填入结果数组
let sortedArray = new Array(arr.length);
for (let index = arr.length - 1; index >= 0; index--) {
// -1 是因为 元素填入数组是 数组下标从 0 开始
sortedArray[countArray[arr[index] - min] - 1] = arr[index]
countArray[arr[index] - min]--
}
return sortedArray
}
function main() {
let arr = [95, 94, 91, 98, 99, 90, 99, 90, 99, 93, 91, 92];
console.log(countSort(arr))
}
main()
小结
复杂度:
如果原始数列的规模为 n，最大和最小整数的差值为 m，
则总体运算量为 3n + m，时间复杂度为O(n + m)
空间复杂度：如果不考虑输出数组，只考虑统计数组的话，则空间复杂度为O(m)
局限性:
1. 当数列最小值和最大值差距过大时，并不适合用计数排序
2. 当数列元素不是整数时，也不适合用计数排序
摘要总结自: 漫画算法 小灰的算法之旅