说透排序算法(中)

系列开篇

为进入前端的你建立清晰、准确、必要的概念和这些概念的之间清晰、准确、必要的关联, 让你不管在什么面试中都能淡定从容。没有目录，而是通过概念关联形成了一张知识网络，往下看你就明白了。当你遇到【关联概念】时，可先从括号中的(强/弱)判断简单这个关联是对你正在理解的概念是强相关(得先理解你才能继续往下)还是弱相关(知识拓展)从而提高你的阅读效率。我也会定期更新相关关联概念。

算法拆解是带你分析算法，掌握算法规律，体会概念与关联的力量。更重要的是让你不害怕算法题，利用分治思维拆解它，你会发现，又是回到了 概念 和 关联 上。下面来看看我们遇到问题，如何去拆解, 并举一反三的吧。

算法是逃不掉的，它是你最直接的实现程序能力的体现。你写的每一句代码，每一种架构思考，每一种优化方式，都是你编程路上的硬核能力，所幸这个能力下'功夫'就能得到。

这几篇说什么，你能获得什么

这几篇重点是：

1. 详细描述各种排序算法的使用方式，实现方式，特点，复杂度分析。
2. 让你能清晰的了解这些排序的区别与联系、掌握排序思想的精髓。

先说下为什么分上中下3篇，因为一篇的话篇幅太长，人的接受能力、程度还有耐心分成2篇比一篇更容易吸收，而且读下篇的时候能很好的用上篇的一些基础知识来做铺垫，流水账列出全部的排序方式只会让你读一遍就忘，收藏然后永远就不看了。

我们不要流水账列举这些算法，一个个拆解他们，从简单的开始，一步步走向更复杂的逻辑。

下面我们就一个个看这些个排序算法，不要急，一个个吃透了就不担心忘记，因为理解了，忘了就直接跳到中间看就好，右边有目录，随时查阅。

先列下上篇链接

大纲-由浅入深

上：

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序

中：

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

下

• 快速排序
• 归并排序
• 堆排序
• Timsort

总结

• 先了解各种排序后再看看动画图加深印象
• 各种排序的各维度对比
• 时间空间复杂度如何分析
• 排序的深水区拓展

中篇我们来介绍下3种非比较型的排序。

直接进入主题

1.计数排序

拆解过程

这种排序不是基于元素的比较，而是利用数组的下标来计算元素正确位置。

我们举个例子来说明它的核心思想：

我们首先假设规定了这10个数取数范围是从 0 ~ 10。

1. 我们知道数字范围从0 ~ 10共11个数字，或者说你的这数列里总共就这 11种数字。

2. 那我们根据这个范围，建立一个长度为 11的数组，数组下标从 0 ~ 10，元素初始值为 0，这个0表示这个数字出现的次数。

bucket = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   // length === 11   
          0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10   // 下标 i

1. 假定20个随机整数的值如下：

array = [9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9]

如何给这些无序的随机整数排序呢？

非常简单，让我们遍历这个无序的随机数列，每一个整数按照其值对号入座，

比如第一个整数是9，那么下标为 9 的数位值 + 1，表示这个数列里现在有 1 个 9，下一个 3,则 下标为 3，的数位值 + 1，依次遍历到底。得到下面数组:

bucket = [1, 2, 1, 3, 2, 2, 1, 2, 1, 4, 1]   // length === 11   
          0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10   // 下标 i

看明白了吗，很简单，这个数组的每一个值，就是表示这个下标的数字在列表里出现了几次。

1. 有了这个统计结果，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次就ok了

array = [0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10]

优化：这个优化很简单，现在我们其实是以最大值来确定统计数组的长度，因为用的是下标来表示。如遇到下面的数列

array = [99, 93, 95, 94, 99, 91, 92, 97, 98, 91, 93]

这种，下标从0 到 99这样 前面很多空间就被浪费了，所以我们利用最小值，做个偏移量就能大大增加效率。比如一个整数95，对应的统计数组下标是 95-90 = 5

我们最后放出完整代码

实现

let testArr = [5, 6, 1, 8, 2, 4, 6, 1, 16]

const countingSort = (array) => {
  // 找到list的最大最小元素，这里有遍历，所以使用这个排序最好是知道最大最小值
  let maxNum = Math.max(...array), 
    minNum = Math.min(...array)
  // 建立一个新数组, 默认置0
  let bucket = new Array(maxNum - minNum + 1).fill(0)

  // 以原数组中的`元素减去最小值`作为bucket数组的`索引`，
  // 以原数组中`元素的出现次数`作为bucket数组的`元素值`
  array.map(item => {
    bucket[item - minNum]++;
  })

  // 把计数数组中的元素放回到旧数组中
  let cur = 0;
  for (let i = 0; i < bucket.length; i++) {
    // 直到本位置数量为 0 了继续往下
    while (bucket[i] > 0) {
      array[cur++] = i + minNum;
      bucket[i]--;
    }
  }

  return array
}

console.log(countingSort(testArr))

下面来说下缺陷，虽然下篇会总结，现在先说下

1. 当数列最大最小值差距过大时，并不适用计数排序。 比如给定20个随机整数，范围在0到1亿之间，这时候如果使用计数排序，需要创建长度1亿的数组。不但严重浪费空间，而且时间复杂度也随之升高。

2. 当数列元素不是整数，并不适用计数排序。 如果数列中的元素都是小数，比如25.213，或是0.00001这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

那么有没方式来解决呢，看下一种排序

2.桶排序

拆解过程

桶排序是计数排序的升级版，我们可以用来解决小数问题。

桶排序当中所谓的“桶”（bucket）其实就是代表一个个 区间范围，每一个桶里面可以承载一个或多个元素。

1. 桶排序的第一步，就是创建这些桶，如何确定桶的"大小"，有很多不同的方式，我们先假设一个 BucketSize = 5作为区间范围大小，那么这些个桶就随之而确定了。

还是用举例来明确：排序数列为[5, 6, 0.1, 8.9, 0.2, 4, 6.3, 13, 16, 0.4, 0.024, 8.5, 0.2]

范围是 5，最大是 16， 最小是 0.024 那么情况就是分成下面 4 个桶

      桶1             桶2               桶3                桶4
[0.024, 5.024)  [5.024, 10.024)  [10.024, 15.024)  [15.024, 20.024)

具体建立多少个桶，如何确定桶的区间范围，有很多不同的方式。高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据尽量均匀的分配到 K 个桶中

1. 桶建立好了，下面第二步就是，遍历原始数列，把元素根据映射函数放入各个桶中：

      桶1             桶2               桶3                桶4
[0.024, 5.024)  [5.024, 10.024)  [10.024, 15.024)  [15.024, 20.024)

5, 0.1, 0.2,      6, 8.9,              13                 16
4, 0.4, 0.024,    6.3, 8.5
0.2

1. 第三步，每个桶内部的元素分别排序(可以递归使用桶排序进行排序，也能用其他排序方式)：

      桶1             桶2               桶3                桶4
[0.024, 5.024)  [5.024, 10.024)  [10.024, 15.024)  [15.024, 20.024)

0.024, 0.1, 
0.2,  0.2,          6, 6.3,            13                 16
0.4, 4, 5           8.5, 8.9

1. 遍历所有的桶，输出所有元素：

[  0.024, 0.1, 0.2, 0.2, 0.4,   4,   5,     6,6.3, 8.5, 8.9,    13,  16]

我们最后放出完整代码

实现

let testArr = [5, 6, 0.1, 8.9, 0.2, 4, 6.3, 13, 16, 0.4, 0.024, 8.5, 0.2]

const bucketSort = (array) => {
  let res = []
  // 找到list的最大最小元素
  let maxNum = Math.max(...array), 
    minNum = Math.min(...array)
  // 假设桶的大小是 5
  const bucketSize = 5
  // 先算出要几个桶，这里是 4 个
  let bucketCount = Math.floor((maxNum - minNum) / bucketSize) + 1;
  // 初始化桶数组 现在成了 [ [], [], [], [] ]
  let bucketLists = new Array(bucketCount)
  for (let i = 0; i < bucketCount; i++) {
    bucketLists[i] = [];
  }

  // 用我们上面分组的方式，把这些数扔到桶里，下面这步之后会变成这样
    // [[ 5, 0.1, 0.2, 4, 0.4, 0.024, 0.2 ],
    // [ 6, 8.9, 6.3, 8.5 ],
    // [ 13 ],
    // [ 16 ]]
  for (i = 0; i < array.length; i++) {
    bucketLists[Math.floor((array[i] - minNum) / bucketSize)].push(array[i]);
  }

  // 然后我们再对每个桶进行排序然后输出就ok了
  for (i = 0; i < bucketLists.length; i++) {
    // 先每个桶进行排序，这里我们就用api了，可以去MDN看下sort的实现
    bucketLists[i] = bucketLists[i].sort((a, b) => a - b);
    // 直接顺序输出每个桶的排好的元素
    for (let j = 0; j < bucketLists[i].length; j++) {
      res.push(bucketLists[i][j]);       
    }
  }

  return res
}

console.log(bucketSort(testArr))

3.基数排序

拆解过程

基数排序不是计数排序，但这也是非比较的一种排序方式，有时候我们可以把排序工作拆分成多个阶段，每一个阶段只根据一个字符进行排序，一共排序k轮（k是最长元素长度）。或者说基数排序是一种基数"桶"的排序，听起来抽象

我们还是来看个具体例子拆解，先看个朴素的例子：[73, 22, 93, 43, 55, 14, 28, 65, 39, 81]

简单来说就是，先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小......每一位其实就是一轮排序。

1. 第一步我们以每轮"基数"建立桶，首先个位数的数值为基数，遍历将它们分配 0 到 9 的桶中，因为数值只能从中选择。得到下面情况，注意个位数为基数

基数    桶
[0] -> []
[1] -> [81]
[2] -> [22]
[3] -> [73 -> 93 -> 43]
[4] -> [14]
[5] -> [55 -> 65]
[6] -> []
[7] -> []
[8] -> [28]
[9] -> [39]

1. 接下来将这些桶中的数值重新串接起来，也就是从上往下依次遍历，得到下面数列:

[81, 22, 73, 93, 43, 14, 55, 65, 28, 39] 注意看这些数其实就是走了一遍个位数的计数排序，个位数是有序的。

1. 下面再来以下一位，十位数作为基数依次遍历放进桶里，注意这里的依次，由于上一轮排序已经把个位数排好了，所以依次排十位时个位数大的就会后面遍历到放进桶里。得到下面情况

基数    桶
[0] -> []
[1] -> [14]
[2] -> [22 -> 28]        // 第一轮排完后 22 第2位，28 倒数第二，所以第二轮 28后入桶
[3] -> [39]
[4] -> [43]
[5] -> [55]
[6] -> [65]
[7] -> [73]
[8] -> [81]
[9] -> [93]

接下来简单了，将这些桶中的数值重新串接起来，成为以下的数列：[14, 22, 28, 39, 43, 55, 65, 73, 81, 93]，已经排好序了。如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD & MSD

• 基数排序既可以从高位优先进行排序（Most Significant Digit first，简称MSD）
• 也可以从低位优先进行排序（Least Significant Digit first，简称LSD）

刚才我们所举的例子，就是典型的LSD方式的基数排序，先排低位，再排高位。

MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个桶中建立“子桶”，将每个桶中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

我们也简单举个例子: 还是这个数列 [11, 13, 22, 18, 21, 12, 33, 55, 51, 88]

1. 第一轮：最高位十位数排序，结果如下:

基数    桶
[0] -> []
[1] -> [11 -> 13 -> 18 -> 12]  => 下一步MSD操作 [1] 11 [2] 12 [3] 13 [8] 18
[2] -> [22 -> 21]
[3] -> [33]
[4] -> []
[5] -> [55 -> 51]
[6] -> []
[7] -> []
[8] -> [88]
[9] -> []

显然，不在一个桶里的数，大小顺序已经是已知的了，(下边桶的数一定比上边桶的数大)，所有在接下来的个位数排序里，我们只需要进行**“各部分”单独排序**就可以了，每一小部分都类似于原问题的一个子问题，做的时候可以采用递归的形式来处理。最后合并成一个有序大数组。

比如 [11 13 18 12] 这个桶可再采用MSD 得到 [11, 12, 13, 18]递归，最后合并就行了。

缺点这种方式桶的空间需求变大，因为每个桶会继续分子桶。

下面来看看实现

LSD实现数字型排序

let testArr = [81, 22, 73, 93, 43, 14, 55, 65, 28]

const RadixNumSortLSD = (array) => {
  // 取得最大数的位数
  let maxDigit = `${Math.max(...array)}`.length
  let mod = 10;
  let dev = 1;
  let tempResArr = [];
  for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for(let j = 0; j < array.length; j++) {
      let bucket = parseInt((array[j] % mod) / dev);
      // 如果没有便新建一个该位上的桶
      if(tempResArr[bucket] === undefined) {
        tempResArr[bucket] = [];
      }
      // 否则就把这个数置入这个桶中
      tempResArr[bucket].push(array[j]);
    }
    // tempResArr 现在是这样 [
    //   [],
    //   [ 81 ],   -> 位数为 1
    //   [ 22 ],
    //   [ 73, 93, 43 ],
    //   [ 14 ],
    //   [ 55, 65 ],
    //   [],
    //   [],
    //   [ 28 ]
    // ]
    // 我们得到中间数组后，遍历得到第一轮排序结果
    let pos = 0;
    // 从上到下遍历输出就行了
    tempResArr.map(item => {
      if (item && item.length > 0) {
        let temp;
        while((temp = item.shift()) !== undefined) {
          array[pos++] = temp
        }
      }
    })
  }
  return array;
}

console.log(RadixNumSortLSD(testArr))

LSD实现字符串排序

我们再拓展到不是数字的序列排序： ['bda', 'cfd', 'qwe', 'yui', 'abc', 'rrr', 'uue', 'dd']

由于每个字符串的长度是3个字符，我们可以把排序工作拆分成3轮：

1. 第一轮：按照最低位字符排序。排序过程使用计数排序，把字母的ascii码对应到数组下标，第一轮排序结果如下：

原数组     ['bda', 'cfd', 'qwe', 'yui', 'abc', 'rrr', 'uue'            // 中间过程跟上面一样，其实用字母作为"桶"，来利用字母的ascii码对应到数组下标第一轮     ['bda', 'abc', 'cfd', 'qwe', 'uue', 'yui', 'rrr']
              ^      ^      ^      ^      ^      ^      ^

1. 第二轮：在第一轮排序结果的基础上，按照第二位字符排序：

原数组     ['bda', 'cfd', 'qwe', 'yui', 'abc', 'rrr', 'uue'第一轮     ['bda', 'abc', 'cfd', 'qwe', 'uue', 'yui', 'rrr']
              ^      ^      ^      ^      ^      ^      ^
第二轮     ['abc', 'bda', 'cfd', 'rrr', 'uue', 'yui', 'qwe']
             ^      ^      ^      ^      ^      ^      ^

需要注意的是，这里使用的计数排序必须是稳定排序，这样才能保证第一轮排出的先后顺序在第二轮还能继续保持。比如在第一轮排序后，元素uue在元素yui之前。那么第二轮排序时，两者的第二位字符虽然同样是u，但先后顺序万万不能变，否则第一轮排序就白做了。

1. 第三轮：在第二轮排序结果的基础上，按照最高位字符排序。

原数组     ['bda', 'cfd', 'qwe', 'yui', 'abc', 'rrr', 'uue'第一轮     ['bda', 'abc', 'cfd', 'qwe', 'uue', 'yui', 'rrr']
              ^      ^      ^      ^      ^      ^      ^
第二轮     ['abc', 'bda', 'cfd', 'rrr', 'uue', 'yui', 'qwe']
             ^      ^      ^      ^      ^      ^      ^
第三轮     ['abc', 'bda', 'cfd', 'qwe', 'rrr', 'uue', 'yui']
              ^      ^      ^      ^      ^      ^      ^             

最后排完就结束了 ['abc', 'bda', 'cfd', 'qwe', 'rrr', 'uue', 'yui']

从上面2个例子，你应该很清楚基数排序具有什么特点了，像这样把字符串(或数字)元素按位拆分，每一位进行一次计数排序的算法，就是基数排序（Radix Sort）。

实现

let testArr = ['bda', 'cfd', 'qwe', 'yui', 'abc', 'urr', 'uee']

const RadixStrSortLSD = (array) => {
  //ascii码的取值范围
  const ASCII_RANGE = 128
  // 计算出最大的元素长度
  let maxLength = Math.max(...array.map(item => `${item}`.length))
  //排序结果数组，用于存储每一次按位排序的临时结果
  let tempResArr = []
  // LSD 从最低位开始比较，一直比较到最高位
  for(let k = maxLength - 1; k >= 0; k--){
    // 第一步：创建辅助排序的统计数组，并把待排序的字符对号入座
    // 这里为了代码简洁，直接使用ascii码范围作为数组长度
    let countArr = new Array(ASCII_RANGE).fill(0)
    for (let i = 0; i < array.length; i++) {
      // 遍历列表，把元素按『基数』入桶
      let index = getCharAsciiIndex(array[i], k)
      countArr[index]++;
    }

    // 第二步：统计数组做变形，后面的元素等于前面的元素之和
    for (let i = 1; i < countArr.length; i++) {
      countArr[i] = countArr[i] + countArr[i - 1]
    }

    // 第三步：倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
    for (let i = array.length - 1; i >= 0; i--) {
      let index = getCharAsciiIndex(array[i], k)
      let sortedTempIndex = countArr[index] - 1
      tempResArr[sortedTempIndex] = array[i]
      countArr[index]--
    }
    //下一轮排序需要以上一轮的排序结果为基础，因此把结果复制给array
    array = JSON.parse(JSON.stringify(tempResArr))
  }
  return array
}

// 获取字符串第k位字符所对应的ascii码序号，桶是根据ascii码来编号的
const getCharAsciiIndex = (str, k) => {
  if (Object.prototype.toString.call(str) === "[object Number]") {
    str = str + ''
  }
  // 如果字符串长度小于k，直接返回0，相当于给不存在的位置补0
  if (str.length < k + 1) {
    return 0
  } else {
    return str[k].charCodeAt() * 1;
  }
}

console.log(RadixStrSortLSD(testArr))

基数排序 vs 计数排序 vs 桶排序

• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值
• 基数排序：根据键值的每位数字来分配桶

这篇我们深入了解了这三种非比较的排序方式，放松下脑子，下次的主角是分治思想，请期待下篇

---

继续下去，你总会有收获。 上面这句话给你们，同样也给我自己前进的动力。

我是摩尔，数学专业，做过互联网研发，测试，产品 致力用技术改变别人的生活，用梦想改变自己的生活 关注我，找到自己的互联网思路，踏实地打牢固自己的技术体系 点赞、关注、评论、谢谢 有问题求助可私信 1602111431@qq.com 我会尽可能帮助你

参考

• www.runoob.com/w3cnote/sor…
• cloud.tencent.com/developer/a…
• mp.weixin.qq.com/s/qrboxA5Sw…
• mp.weixin.qq.com/s/WLh-ovG_5…