排序算法-5（javascript） 计数排序的实现

前面讲的都是基于比较交换的算法，那有没有不使用比较就能排序的算法呢？它们的复杂度会不会更优呢？

接下来在后面的系列文章中，我将一一介绍O(n)线性的排序方法：

• 计数排序
• 桶排序
• 基数排序

这一篇文章我们就先来学习什么是计数排序：

计数排序

计数排序是针对给定范围的队列，创建这个范围大小的数组，初始值都为0，然后遍历队列，将数字放至到对应的下标位置，如果出现1次，则计数+1，直至遍历完成，就将所有的数字都放入这个数组里了。

然后再次遍历这个数组，按照数组下标，将取出对应的值，如果计数为几，就按顺序出现几次，将这些值放入一个新数组中，遍历完成后，就可以得到有序队列了

下面，按常，举个栗子：
初始的无序数组，假设总共有12个数，假设所有值都在0-10之间取，这12个值分别为：1、3、4、6、8、9、1、2、3、10、7、5

1. 创建一个长度为11的数组，初始值全设为0：[0,0,0,0,0,0,0,0,0,0,0]
2. 遍历这12个值，第1个为1，将数组下标为1的位置，计数加1 ：[0,1,0,0,0,0,0,0,0,0,0]
3. 第2个为3，将数组下标为3的位置，计数加1： [0,1,0,1,0,0,0,0,0,0,0,0]
   ...
4. 直到所有数字遍历完成，结果为：[0,2,1,2,1,1,1,1,1,1,1]
5. 这时候，遍历这个数组，取出对应下标的值，根据次数，放到一个新队列中
6. 比如，下标为0的计数为0，代表没有数字，忽略；
7. 下标为1的数字计数为2，代表1出现了2次，则新队列结果为:[1,1]
8. 下标为2的数字计数为1，代表2出现了1次，则往新队列中添加元素[1,1,2]
   ...
9. 最后，可以得到最终的结果[1,1,2,3,3,4,5,6,7,8,9,10]，这就是我们想要的有序队列了

计数算法的优化

如果这个序列的范围不是从0开始，而是从某个值到某个值之间，比如是500-600之间取值，这其实只用了101个空间，这时候如果从创建从0-600的初始数组，这无疑浪费了0-499的空间，计算机说不要占着茅坑不干事！

所以要优化一下，只创建101个空间大小，来放置500-600间的数，那么这个关系怎么对应上呢？
其实只要下标 + min就是我们对应的值了，比如500放到下标为0的位置，到时取出来的值时，就下标0 + 500，就是我们想到的值了

/**
 * @description 实现计数算法
 * @param arr: 初始的无序队列（一般为指定范围）
 * @return res: 计数排序后的有序队列
 */

function countSort(arr) {
  // 计算出原始数组的最大最小值
  let max = arr[0]
  let min = arr[0]
  const len = arr.length
  for(let i = 0; i< len; i++) {
    if(arr[i] > max) {
      max = arr[i]
    }
    if(arr[i] < min) {
      min = arr[i]
    }
  }
  // 计算计数数组的容量
  const countLen = max - min + 1
  let countArr = new Array(countLen).fill(0)  // 创建计数数组，并设置所有数的计数初始值为0
  
  // 遍历初始数组，给对应下标(arr[j] - min)计数加1
  for(let j = 0; j < len; j++ ) {
    countArr[arr[j] - min]++;
  }

  // 结果队列
  let res = []
  // 遍历结果队列的指针
  let resIndex = 0
  for(let k = 0; k < countLen; k++) {
    // 如果某数计数大于0，就循环取出值
    while(countArr[k] > 0) {
      // 将此数放入结果队列中
      res[resIndex] = k + min
      // 队列指针右移
      resIndex++;
      // 计数减1
      countArr[k]--;
    }
  }

  return res
}
//  使用console.time()和console.timeEnd()这一句语句，会输出中间程序执行的运行时间
console.time()
const arr = [544,522,522,533,511,522,551,552,553,510,557,555]
let res = countSort(arr)
console.log('res:', res); // [ 510, 511, 522, 522, 522, 533, 544, 551, 552, 553, 555, 557 ]
console.timeEnd()  // default: 4.135ms

计数算法的再次优化

之前计算排序已经实现排序的基本功能了？但是，我们会发现，它把相同的部分，使用计数方式存储后，这几个相同部分，我就分不清它在初始队列中哪个先哪个后出现的了，是一个不稳定的算法

比如:[3,1,2,1]，当计数统计后为：[2,1,1]，那么在1位置上的两个1，最终会变成:[1,1,2,3]排序后我是分不清之前是哪个1先哪个1后，如果我希望排序后，不要改变相同元素的相对位置，也就是让它变成一个稳定的算法，要怎么做呢？

要实现这个功能，其实就是把当前元素的计数改成： 前面所有元素计数之和 + 当前元素计数，这样，对应下标元素对应的那个元素的计数，就是它最终序列的位置，有一些绕，还是来讲栗子吧：
比如：
初始[3,1,2,1,5]

• 按照之前优化1的算法：
  最大值max为5，最小值min为1，那么设置空间为3的计数数组[0,0,0,0,0]：

  1. 下标0对应元素1 (下标+min，就是它所对应的元素值)，下标所在位置放置元素1的计数2, [2,0,0,0,0]
  2. 下标1对应元素2，下标所在位置放置元素2的计数1, [2,1,0,0,0]
  3. 下标2对应元素3，下标所在位置放置元素3的计数1, [2,1,1,0,0]
  4. 下标4对应元素5，下标所在位置放置元素5的计数1, [2,1,1,0,1]
     这时，遍历计数数组，根据下标所在得出:
  5. 下标0，对应元素是1，计数为2，所以生成新数组[1,1]
  6. 下标1，对应元素2，计数为1，所以生成新数组[1,1,2]
  7. 下标2，对应元素3，计数为1，所以生成新数组[1,1,2,3]
  8. 下标3，因为计数为0，忽略
  9. 下标5，对应元素5，计数为1，所以就生成新数组[1,1,2,3,5]

• 按照现在优化2的算法：
  最大值max为5，最小值min为1，计数数组[0,0,0,0,0]：

  1. 下标0对应元素1 (下标+min，就是它所对应的元素值)，下标所在位置放置元素1的计数2, [2,0,0]
  2. 下标1对应元素2，下标所在位置放置元素2的自身计数1 + 前面元素的计数2 = 计数3, [2,3,0]
  3. 下标2对应元素3，下标所在位置放置元素3的自身计数1 + 前面元素的计数3 = 计数4, 最终的计数数组为：[2,3,4]
  4. 下标3对应元素4，下标所在位置放置元素3的自身计数0 + 前面元素的计数4 = 计数4, 最终的计数数组为：[2,3,4,4]
  5. 下标4对应元素5，下标所在位置放置元素5的自身计数1 + 前面元素的计数4 = 计数5, 最终的计数数组为：[2,3,4,4,5]

  这时候，创建一个跟原数组一样大小的空数组，从后向前遍历初始数组，根据元素获取对应计数数组中下标（元素值-min）的计数值，就是它的最终位置，并更新其计数-1，代表下一次相同元素要放置的位置：

  1. 遍历[3,1,2,1,5]最后一个数5,它的计数下标位置为：5-min=5-1=4,查看计数数组下标为4的值，为5，代表代表它放置在新数组的第5位[,,,,5]，此时，计数数组更新5的计数为：5-1=4，代表下一次相同元素应该放置的位置[2,3,4,4,4]；
  2. 遍历倒数第二个数1，它的计数下标位置：1-1=0，查看计数数组下标为0的值，为计数2，代表它放置在新数据的第2数，[,1,,,5]，此时，计数数组更新1的计数为：2-1=1，代表下一次相同元素应该放置的位置，计数数组更新为：[1,3,4,4,4]；
  3. 遍历倒数三个数2，它的计数下标位置: 2-1=1，查看计数数组下标为1的值，为计数3，代表它放置在新数据的第3位，[,1,2,,5]，此时，计数数组更新2的计数为：3-1=2，代表下一次相同元素应该放置的位置，计数数组更新为：[1,2,4,4,4]；
  4. 遍历倒数第四个数1，它的计数下标位置1-1=0，计数数组下标为1的值已经在上一次更新为1，所以此时，把它放在新数组第1的位置[1,1,2,,5],计数数组更新为[0,2,4,4,4]
  5. 遍历第一个数3，它的计数下标位置为：3-min = 3-1 = 2，查看计数数组下标为2的值，为4，代表它放置在新数组的第4位[1,1,2,3,5]，计数数组更新为[0,2,3,4,4]，至此，排序结束
     这时候发现，越往后的出现相同元素的位置越后，这样就实现稳定的计数排序了

   /**
 * @description 优化版：实现稳定的计数排序
 * @param arr: 初始的无序队列（一般为指定范围）
 * @return res: 计数排序后的有序队列
 */

function stableCountSort(arr) {
  let max = arr[0]
  let min = arr[0]
  const len = arr.length
  for(let i = 0; i< len; i++) {
    if(arr[i] > max) {
      max = arr[i]
    }
    if(arr[i] < min) {
      min = arr[i]
    }
  }
 const countLen = max - min + 1
 // 前面创建计数数组的步骤不变
 let countArr = new Array(countLen).fill(0)
 for(let j = 0; j < len; j++ ) {
   countArr[arr[j] - min]++;
 }
 // 就增加了：从第2个数开始，将后面元素的计数变成与前面所有元素的计数之和 
 for(let z = 1; z < countLen; z++) {
   // 加上前一位的计数次数（也就是之前所有元素的计数之和）  
   countArr[z] += countArr[z -1]
 }
 console.log('2222', countArr); // 此时，计数数组：[ 2, 3, 4, 4, 5 ]
 
 // 结果队列  
 let res = new Array(len)
 let countIndex = 0
 // 对初始序列，进行从后往前遍历  
 for(let k = len - 1; k >= 0; k--) {
   //  获取元素对应的计数
   countIndex = countArr[arr[k] - min]
   // 因为下标0占了一位，所以下标要减1   
   res[countIndex - 1] = arr[k]
   console.log(res)
   countArr[arr[k] - min]--;
 }

 return res
}
const arr1 = [3,1,2,1,5]
res = stableCountSort(arr1)
console.log('res2:', res); // [ 1, 1, 2, 3, 5 ]

计数排序的局限性

虽然计数排序的时间复杂度只有O(n)，为什么我们很少用到它呢？因为它有比较大的局限性：

1. 当数列最大和最小值的差距过大时，并不适合；过大的差距意思空间上的消耗也要随之变 大。不但浪费空间，而且时间复杂度也会随之升高
2. 当数列元素不是整数时，也不适合。比如小数，就无法根据元素创建对应的计数数组。

总结

• 时间复杂度：
  1. 获取最大最小值O(n)
  2. 获取计数数组O(n)
  3. 获取累加计数数组O(n)
  4. 遍历初始数组O(n)
     总的是O(4n)，还是约等于O(n)
• 空间复杂度
  1. 创建计数数组空间O(n)
  2. 结果队列O(n)
     总的是O(2n)，还是约等于O(n)
• 是一种典型的空间换时间的算法
• 优化后的计数排序已经是稳定的排序方法

排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现
排序算法-5（javascript） 计数排序的实现