js数据结构与算法

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

2021-04-01  本文已影响0人  miao8862

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

接下来在后面的系列文章中，我将一一介绍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]

   /**
 * @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（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现
排序算法-5（javascript） 计数排序的实现

上一篇下一篇

猜你喜欢

热点阅读