2020-11-25 排序算法三（计数排序和桶排序）

计数排序

计数排序非常容易理解，相信等我介绍完概念，大家都可以写出来。

通过数组下标来记录数列中各数的值，通过下标对应的值来记录相同数出现的频率。打个比方，一个长度为10的数组，下标为0-9，如果我们要排序的数列为0-9之间的随机数，如list = [0, 0, 8, 3, 4, 2, 7, 7, 7, 5]，要将其从小到大排列：

• 声明一个下标计数数组为sortArray = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]，初始值都为0；
• 遍历list，每个元素大小对应下标的值在计数数组中加1，如遍历完前三个数后，sortArray变成了[2, 0, 0, 0, 0, 0, 0, 0, 1, 0]。
• 结束后再遍历sortArray打印出有序的数列。

是不是很简单呢，代码如下：
需要注意，一开始我们是不确定数列的最大值的，所以我们要先找到数列中的最大值max，并将sortArray的长度设为max + 1，保证最大值可以找到其对应的下标

function countSort(list: number[]): number[] {
  let max = 0;
  for (let i = 0; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i];
    }
  }
  const sortArray: number[] = new Array(max+1);
  list.forEach(item => {
    if (sortArray[item] === undefined) {
      sortArray[item] = 0;
    }
    sortArray[item]++;
  });
  const res = [];
  sortArray.forEach((sort, index) => {
    if (sort > 0) {
      for (let i = 0; i < sort; i++) {
        res.push(index);
      }
    }
  });
  return res;
}

这样是可以实现了排序，但是还可以进行优化，如果我们要排列的数组为[99, 98, 97, 93, 95]呢？最大值为99，所以我们建了一个长度为100的数组，而实际只利用了下标为93-99这一段空间。所以我们可以建立一个长度为max - min + 1的数组，来进行计数。最后统计的时候每个元素都加上最小值min即可。

function countSort(list: number[]): number[] {
  let max = 0;
  let min = 0;
  for (let i = 0; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i];
    }
    if (list[i] < min) {
      min = list[i];
    }
  }
  const sortArray: number[] = new Array(max - min + 1);
  list.forEach(item => {
    const index = item - min;
    if (sortArray[index] === undefined) {
      sortArray[index] = 0;
    }
    sortArray[index]++;
  });
  const res = [];
  sortArray.forEach((sort, index) => {
    if (sort > 0) {
      for (let i = 0; i < sort; i++) {
        res.push(index + min);
      }
    }
  });
  return res;
}

上述方法只是记录了某个数出现的频率，并没有真正将输入的数列排列成有序的，造成了我们容易分不清相同大小的值谁在前谁在后。

改进：

• 将统计数组sortArray进行处理，让其变成值为代表输入数列为该下标的元素的排名；
  如[5, 5, 9, 0, 4]进行统计并处理的过程如下：从第二个元素开始，每个元素的值为前面所有值的和，因为我们是从小到大排序，所以在sortArray前面出现的元素，在输出结果中排名肯定是比后面的高
  

  image.png

• 从后往前（为了保证排序稳定性）遍历输入数组，利用其值value找到sortArray中对应下标的元素item（处理完该元素后，该item的值应该减一，因为下次再出现相同的值，由于排序稳定性，应该是排名靠前一位的），item就代表着value元素在最终的输出结果中的位置排名。

function countSort(list: number[]): number[] {
  let max = 0;
  let min = 0;
  for (let i = 0; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i];
    }
    if (list[i] < min) {
      min = list[i];
    }
  }
  const sortArray: number[] = new Array(max - min + 1);
  list.forEach(item => {
    const index = item - min;
    if (sortArray[index] === undefined) {
      sortArray[index] = 0;
    }
    sortArray[index]++;
  });
  for (let i = 1; i < sortArray.length; i++) {
    // 排名递增
    if (sortArray[i] === undefined) {
      sortArray[i] = 0;
    }
    sortArray[i] += sortArray[i - 1];
  }
  const res = new Array(list.length);
  list.forEach(value => {
    const realIndex = value - min;
    res[sortArray[realIndex] - 1] = value;
    sortArray[realIndex]--;
  });
  return res;
}

总结

• 计数排序只适合在一定范围内的整数排序；
• 极值差为m，输入规模为n，其时间复杂度为O(n+m)（遍历了三次输入数组，3n省略了系数），空间复杂度为O(m)（sortArray长度为m）

桶排序

基本思想就是：

• 创建桶，方法有很多，一般来说对n个数进行排序就创建n个桶，可以把桶当作一个链表，一堆桶当作一个数组；
• 确定每个桶的存值区间，方法也很多，一般来说是输入数列的极值差（max-min）除以个数n为一个区间值，每个桶之间间隔一个区间值；
• 遍历输入数列list，将其按照区间存放到桶内，同一个桶内可能存在0个或多个值；
• 遍历桶，将其内部值进行排序；
• 遍历桶，输出所有元素，得到有序数列。

function sortByBucket(list: number[]) {
  let max = list[0];
  let min = list[0];
  for (let i = 1; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i];
    }
    if (list[i] < min) {
      min = list[i];
    }
  }
  const dValue = max - min;
  // 确定桶的存值区间
  const partValue = dValue / (list.length - 1);
  // 建桶
  const bucket: number[][] = [];
  for (let i = 0; i < list.length; i++) {
    bucket.push([]);
  }
  // 插值
  for (let i = 0; i < list.length; i++) {
    const index = Math.floor((list[i] - min) / partValue);
    bucket[index].push(list[i]);
    // 内部排序
    for (let i = bucket.length - 1; i > 1; i--) {
      const singleBucket = bucket[index];
      if (singleBucket[i - 1] > singleBucket[i]) {
        singleBucket[i - 1] = singleBucket[i] ^ singleBucket[i - 1];
        singleBucket[i] = singleBucket[i] ^ singleBucket[i - 1];
        singleBucket[i - 1] = singleBucket[i] ^ singleBucket[i - 1];
      }
    }
    console.log(bucket)
  }
  // 输出
  const res = [];
  for (let i = 0; i < bucket.length; i++) {
    res.push(...bucket[i]);
  }
  return res;
}

总结

image.png