排序算法(七)--计数排序

技数排序的思想：

• 在数组中找到最大的一个，然后生成一个新的数组，计数数组
• 将原数组中的项作为计数数组的索引，将原数组中项出现的次数记录在计数数组中
• 将计数组的索引按出现的次数平铺在原数组中，并返回
  

  var countSort = (arr, max) => {
      let countArr = new Array(max + 1)
      let sortIndex = 0
      for(let i = 0; i < arr.length;i++) {
          if(!countArr[arr[i]]) {
              countArr[arr[i]] = 0
          }
          countArr[arr[i]]++
      }
      for (let j = 0;j < countArr.length;j++) {
          //  判断countArr中存放的次数是大于0的
          while(countArr[j] > 0) {
              arr[sortIndex++] = j
              //  在countArr中存放的是数量
              //  所以需要没存一次就减少一次
              countArr[j]--
          }
      }
      return arr
  }
  let arr = [3,2,4,12,5,5,3,1,7,3,8,5,9,8,9,1]
  countSort(arr, 12)
  //  [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 7, 8, 8, 9, 9, 12]

  注：
  我们可以看到，计数排序并不是像其他排序一样，通过比较大小，所以，计数排序是适合特定情况下的排序，计数排序要求输入的数据必须是有确定范围的整数。