[算法拆解] 一文说透排序算法的特点（中）
说透排序算法(中)
系列开篇
为进入前端的你建立清晰、准确、必要的概念和这些概念的之间清晰、准确、必要的关联, 让你不管在什么面试中都能淡定从容。没有目录，而是通过概念关联形成了一张知识网络，往下看你就明白了。当你遇到【关联概念】时，可先从括号中的(强/弱)判断简单这个关联是对你正在理解的概念是强相关(得先理解你才能继续往下)还是弱相关(知识拓展)从而提高你的阅读效率。我也会定期更新相关关联概念。
算法拆解是带你分析算法，掌握算法规律，体会概念与关联的力量。更重要的是让你不害怕算法题，利用分治思维拆解它，你会发现，又是回到了 概念 和 关联 上。下面来看看我们遇到问题，如何去拆解, 并举一反三的吧。
算法是逃不掉的，它是你最直接的实现程序能力的体现。你写的每一句代码，每一种架构思考，每一种优化方式，都是你编程路上的硬核能力，所幸这个能力下'功夫'就能得到。
这几篇说什么，你能获得什么
这几篇重点是：
- 详细描述各种排序算法的使用方式，实现方式，特点，复杂度分析。
- 让你能清晰的了解这些排序的区别与联系、掌握排序思想的精髓。
先说下为什么分上中下3篇，因为一篇的话篇幅太长，人的接受能力、程度还有耐心分成2篇比一篇更容易吸收，而且读下篇的时候能很好的用上篇的一些基础知识来做铺垫，流水账列出全部的排序方式只会让你读一遍就忘，收藏然后永远就不看了。
我们不要流水账列举这些算法，一个个拆解他们，从简单的开始，一步步走向更复杂的逻辑。
下面我们就一个个看这些个排序算法，不要急，一个个吃透了就不担心忘记，因为理解了，忘了就直接跳到中间看就好，右边有目录，随时查阅。
先列下上篇链接
大纲-由浅入深
上：
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
中：
- 计数排序
- 桶排序
- 基数排序
下
- 快速排序
- 归并排序
- 堆排序
- Timsort
总结
- 先了解各种排序后再看看动画图加深印象
- 各种排序的各维度对比
- 时间空间复杂度如何分析
- 排序的深水区拓展
中篇我们来介绍下3种非比较型的排序。
直接进入主题
1.计数排序
拆解过程
这种排序不是基于元素的比较，而是利用数组的下标来计算元素正确位置。
我们举个例子来说明它的核心思想：
我们首先假设规定了这10个数取数范围是从 0 ~ 10。
-
我们知道数字范围从0 ~ 10共
11个数字，或者说你的这数列里总共就这11种数字。 -
那我们根据这个范围，建立一个长度为
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
- 假定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
看明白了吗，很简单，这个数组的每一个值，就是表示这个下标的数字在列表里出现了几次。
- 有了这个
统计结果，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次就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))
下面来说下缺陷，虽然下篇会总结，现在先说下
-
当数列最大最小值差距过大时，并不适用计数排序。 比如给定20个随机整数，范围在0到1亿之间，这时候如果使用计数排序，需要创建长度1亿的数组。不但严重浪费空间，而且时间复杂度也随之升高。
-
当数列元素不是整数，并不适用计数排序。 如果数列中的元素都是小数，比如25.213，或是0.00001这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。
那么有没方式来解决呢，看下一种排序
2.桶排序
拆解过程
桶排序是计数排序的升级版，我们可以用来解决小数问题。
桶排序当中所谓的“桶”（bucket）其实就是代表一个个 区间范围，每一个桶里面可以承载一个或多个元素。
- 桶排序的第一步，就是创建这些桶，如何确定桶的"大小"，有很多不同的方式，我们先假设一个 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 桶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 桶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
- 遍历所有的桶，输出所有元素：
[ 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]
简单来说就是，先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小......每一位其实就是一轮排序。
- 第一步我们以每轮"基数"建立桶，首先个位数的数值为基数，遍历将它们分配
0到9的桶中，因为数值只能从中选择。得到下面情况，注意个位数为基数
基数 桶
[0] -> []
[1] -> [81]
[2] -> [22]
[3] -> [73 -> 93 -> 43]
[4] -> [14]
[5] -> [55 -> 65]
[6] -> []
[7] -> []
[8] -> [28]
[9] -> [39]
- 接下来将这些桶中的数值重新串接起来，也就是从上往下依次遍历，得到下面数列:
[81, 22, 73, 93, 43, 14, 55, 65, 28, 39] 注意看这些数其实就是走了一遍个位数的计数排序，个位数是有序的。
- 下面再来以下一位，十位数作为基数依次遍历放进桶里，注意这里的依次，由于上一轮排序已经把个位数排好了，所以依次排十位时个位数大的就会后面遍历到放进桶里。得到下面情况
基数 桶
[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]
- 第一轮：最高位十位数排序，结果如下:
基数 桶
[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轮：
- 第一轮：按照最低位字符排序。排序过程使用计数排序，把字母的ascii码对应到数组下标，第一轮排序结果如下：
原数组 ['bda', 'cfd', 'qwe', 'yui', 'abc', 'rrr', 'uue' // 中间过程跟上面一样，其实用字母作为"桶"，来利用字母的ascii码对应到数组下标第一轮 ['bda', 'abc', 'cfd', 'qwe', 'uue', 'yui', 'rrr']
^ ^ ^ ^ ^ ^ ^
- 第二轮：在第一轮排序结果的基础上，按照第二位字符排序：
原数组 ['bda', 'cfd', 'qwe', 'yui', 'abc', 'rrr', 'uue'第一轮 ['bda', 'abc', 'cfd', 'qwe', 'uue', 'yui', 'rrr']
^ ^ ^ ^ ^ ^ ^
第二轮 ['abc', 'bda', 'cfd', 'rrr', 'uue', 'yui', 'qwe']
^ ^ ^ ^ ^ ^ ^
需要注意的是，这里使用的计数排序必须是稳定排序，这样才能保证第一轮排出的先后顺序在第二轮还能继续保持。比如在第一轮排序后，元素uue在元素yui之前。那么第二轮排序时，两者的第二位字符虽然同样是u，但先后顺序万万不能变，否则第一轮排序就白做了。
- 第三轮：在第二轮排序结果的基础上，按照最高位字符排序。
原数组 ['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 我会尽可能帮助你