数据结构和算法之美-第十篇-桶排序、计数排序、基数排序

桶排序、计数排序、基数排序都是线性排序，它们的时间复杂度都是O(n)，这样一看好像很厉害的样子，比我们之前提到的快排、归并都要牛，使用分治的思想结合递归的手段最终的平均时间复杂度也只能做到O(nlogn)。

其实不然，因为这三种排序只能用于特定的场景，只有在适用的场景中这些排序才能派上用场。

桶排序

桶排序的工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

桶排序以下列程序进行：

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

假设有 n 个数据，我们把它均匀的分不到 m 个桶里，每个桶里的数据都是 k = n/m ，每个桶里的数据再使用快排进行排序，那 m 个桶的时间复杂度就是O(m * k (logk))，当桶的个数 m 接近于数据 n 时，时间复杂度就是O(n)。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

计数排序

计数排序可看成桶排序的一种特殊情况，计数排序的每个桶中的元素的值是一样的。

算法步骤：
算法的步骤如下：

找出待排序的数组中最大和最小的元素
统计数组中每个值为 {\displaystyle i} i的元素出现的次数，存入数组 {\displaystyle C} C 的第 {\displaystyle i} i项
对所有的计数累加（从 {\displaystyle C} C 中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素 {\displaystyle i} i放在新数组的第 {\displaystyle C[i]} {\displaystyle C[i]}项，每放一个元素就将 {\displaystyle C[i]} {\displaystyle C[i]}减去1

举个栗子：假设高考满分900分，最低0分，现有50万考生，我需要给他们排名。这种情况就很适合计数排序。
0-900我们要901个桶，遍历一遍数据（内存足够）分别放入这901个桶中，同一个桶内的考生分数是相同的。其实这样基本就已经实现了排序。但想达到完美，还差一步，相同分数的考生排名顺序的问题，这其实也就是之前说过的稳定性的问题。如果我们直接从这901个桶中把数据取出来，那就是一个不稳定的排序，为了达到稳定，需要进行反向填充，也就是上面算法步骤的第四步。

我们假设考生只有8人，分数范围为 [0-5] ，现有数组[2, 5, 3, 0, 2, 3, 0, 3]，排序并保持稳定性。

const countingSort = arr => {
  const len = arr.length;
  if (!len) return;

  // 找最大值
  let max = 0;
  for (let i = 0; i < len; i++) {
    if (arr[i] > max) max = arr[i];
  }

  // 计数数组
  const c = new Array(max + 1).fill(0);
  for (let i = 0; i < len; i++) {
    c[arr[i]]++;
  }
  // c累加
  for (let i = 1; i < c.length; i++) {
    c[i] += c[i - 1];
  }

  // 存储排名之后的数据
  const r = [];
  /**
   * 计数排序代码的精妙之处就是下面这个循环了
   * 从后往前遍历
   */
  for (let i = len - 1; i >= 0; i--) {
    r[c[arr[i]] - 1] = arr[i];
    c[arr[i]]--;
  }
  return r;
};

const a = [2, 5, 3, 0, 2, 3, 0, 3];
countingSort(a);

计数排序只能用在数据范围不大的场景，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且计数排序只适合给非负整数排序，如果要排序的数据是其他类型的，要其在不改变相对大小的情况下，转化为非负整数。

基数排序

实现原理：将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

手机号码的排序就很适合使用基数排序。当然前提是数据规模大。若是少量的数据，我们之前提到的快排、归并甚至是冒泡、插入都可以，但是数据规模超大，排序算法细微的性能差异就会被放的超大，所以算法很重要。

比如现在有十万个手机号，要对它们进行排序。即使用快排时间复杂度也只能是O(nlogn)；如果使用基数排序，基本思路：根据手机号的最后一位使用计数排序，然后按照倒数第二位计数排序，一直排到第一位手机号就都有序了。时间复杂度是11 * O(n)，按照大O表示法，时间复杂度是O(n)

如果数据量很小的话 logn < 11是很有可能的，所以在具体的场景中，考虑时间复杂度是不能直接忽略系数等变量的，要综合实际情况。

总结一下：基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

总结

到此排序基本就告一段落了，常见的排序除了堆排序（了解树结构之后在整理）之外基本都已经涉及了。

排序算法本身是有一定的优劣之分的，比如冒泡和插入排序比选择排序要更好
同一排序算法的时间复杂度根据不同情况（最好、最坏）有时会有很大差距，可以通过一些策略来优化，比如三数取中法来优化快排等
排序算法的选择是要根据具体的场景的，从这个角度看，没有最好的排序算法，只有最合适的排序算法。

所以，一个好的排序算法需要根据场景去切换，需要各种策略去调整。比如 Glibc 中的 qsort() 函数，qsort() 会优先使用归并排序，当数据量比较大时，会改用快速排序进行排序。qsort() 快速排序选择基准点的策略就是三数取中法。

桶排序

计数排序

基数排序

总结

FEATURED TAGS

FRIENDS