总结下js排序算法和乱序算法

作者 | 他好像一条狗啊

来源 | urlify.cn/NnAZFj

其实本人最怕的就是算法，大学算法课就感觉老师在讲天书，而且对于前端来说，算法在实际的应用中实在是很有限。毕竟算法要依靠大量的数据为基础才能发挥出算法的效率，就浏览器那性能，......是吧，退一万步说，真的有人把这大量的数据处理业务放到前端，那我只能说这是团队和架构师的失职，不说页面应用能不能加载出来，等你靠前端算出来，用户早就跑了。所以，就目前而言，绝大部分的算法使用场景都不在前端，就那么些数据量放在那，前端使用算法除了加重代码逻辑没有更多的好处。当然话又说回来了，我也知道这是个好东西，所以我也会去了解一点。这里就不说什么高深的算法了，先总结下相对简单的排序算法吧，以下均为js实现。

排序算法

1.TimSort算法

　　看到这个算法名，大多数前端er都不知道这是什么算法吧，但是我要是说这个是实现大名鼎鼎v8引擎的sort()的核心算法，你们就应该恍然大悟了吧。旧版的排序sort()原理大家应该很熟悉了，数组长度小于10用插入排序，否则使用快速排序。旧版的排序sort()源码地址：https://github.com/v8/v8/blob/5.9.221/src/js/array.js#L996

　　而新版的排序sort()源码使用Torque语言编写，源码备注是基于python的某一版本TimSort算法实现的，大致原理是归并排序和插入排序的混合排序算法：针对现实中需要排序的数据分析看，大多数据通常是有部分已经排好序的数据块，Timsort 称这些已经排好序（不管是升序还是降序）的数据块为 “run”。又因为在合并序列的时候，如果run的数量等于或者略小于2的幂次方的时候，效率是最高的，所以run要有一定的约束，于是根据序列长度定义了一个minrun，如果原始的run小于minrun的长度，用插入排序扩充run，最后将这些run用归并排序合并序列，得到最后的run就是排序后的结果。有兴趣的可以了解下源码，反正我看不懂，说到这，突然开始怀念旧版源码了。新版的排序sort()源码地址：https://github.com/v8/v8/blob/master/third_party/v8/builtins/array-sort.tq。

　　大多数前端排序场景用这个方法就已经足够了，默认排序顺序（没有携带参数）是在将元素转换为字符串后，然后比较按照它们的UTF-16字符编码的顺序进行排序，如果要比较数字的话，就需要传入参数compareFunction。

使用代码短小精悍，如下：

var arr = [11,8,5,6,3,10,7,8,2];
function compareNumbers(a,b){
return a - b;
}
console.log(arr.sort());//[10, 11, 2, 3, 5, 6, 7, 8, 8]
console.log(arr.sort(compareNumbers));//[2, 3, 5, 6, 7, 8, 8, 10, 11]

2.冒泡排序算法

　　这个可以说是最基础的或是最常见的了吧，尤其是其形象的命名“冒泡”深入人心，顾名思义，经过不断的交换，最大的数会像水中的泡泡一样慢慢往上浮动，直至顶端。它会在未排序队列内，依次比较两个相邻的元素，把较大的元素放置于更靠顶端的位置。

其实现代码如下：

function bubbleSort(array) {
var length = array.length;
for(var i = length - 1; i > 0; i--) {
for(var j = 0; j < i; j++) {
if(array[j] > array[j+1]) {
var temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
console.log(array);
}
return array;
}


var arr = [11,8,5,6,3,10,7,8,2];
var result = bubbleSort(arr);

再放上一张形象的排序流程图，搭配上面的log图食用更佳。

3.选择排序算法

　　在未排序队列内，选择其中最小的元素，然后和第一个元素进行位置互换，以此类推，直到所有元素排序完毕。

其实现代码如下：

function selectionSort(array) {
var length = array.length;
for(var i = 0; i < length; i++) {
var min = array[i];
var index = i;
for(var j = i + 1; j < length; j++) {
if(array[j] < min) {
min = array[j];
index = j;
}
}
if(index != i) {
var temp = array[i];
array[i] = array[index];
array[index] = temp;
}
console.log(array);
}
return array;
}

var arr = [11,8,5,6,3,10,7,8,2];
var result = selectionSort(arr);

排序流程图：

4.插入排序算法

　　这个算法打过斗地主或是跑的快的应该很熟悉，我这样说就明白了：就是抓到牌之后，我们会先展开牌，然后先把第一张放到左边（排序队列），然后把第二张（可以看为未排序队列第一张）从右边（未排序队列）再拿到左边去按从小到大进行排序，放到合适的位置。恩，形象的丫批。上文也说到了，这是旧版的排序sort()在数组长度小于10的情况下采用的排序算法。

其实现代码如下：

function insertionSort(array) {
var length = array.length;
for(var i = 0; i < length - 1; i++) {
var insert = array[i+1];
var index = i + 1;
for(var j = i; j >= 0; j--) {
if(insert < array[j]) {
array[j+1] = array[j];
index = j;
}
}
array[index] = insert;
console.log(array);
}
return array;
}

var arr = [11,8,5,6,3,10,7,8,2];
var result = insertionSort(arr);

排序流程图：

5.希尔排序算法

　　希尔排序算法是以其设计者shell的名字命名的排序算法，又称缩小增量排序，算是个插入排序算法的plus版本。它的本质是多个分组同时进行插入排序算法，所以会比插入排序算法更加高效。核心是，这个多个分组是按照队列的下标进行一定的增量分组。

其实现代码如下：

function shellSort(array) {
var length = array.length;
var gap = Math.round(length / 2);
while(gap > 0) {
for(var i = gap; i < length; i++) {
var insert = array[i];
var index = i;
for(var j = i; j >= 0; j-=gap) {
if(insert < array[j]) {
array[j+gap] = array[j];
index = j;
}
}
array[index] = insert;
}
console.log(array);
gap = Math.round(gap/2 - 0.1);
}
return array;
}

var arr = [11,8,5,6,3,10,7,8,2];
var result = shellSort(arr);

这个没有流程图，只能一步一步解释了。首先，gap就是增量，通过整个流程最后可以得出，gap依次取值为：5,2,1,0；

　　一轮排序：根据增量5，对数组[11,8,5,6,3,10,7,8,2]而言就是11和10比较，8和7比较，5和8比较，6和2比较，最后剩下一个3不动；两两比较，大小互换位置，得到数组[10,7,5,2,3,11,8,8,6]；

　　　　　　 注意，这里互换位置的时候是按照下标来互换的，这样光说看起来比较苍白无力，换成二维的吧

　　二轮排序：此时增量为2，对数组[10,7,5,2,3,11,8,8,6]而言就是分为[10,5,3,8,6]比较，[7,2,11,8]比较，两组分别进行插入算法，大小互换位置，得到[3,5,6,8,10]和[2,7,8,11]，即是[3,2,5,7,6,8,8,11,10]；

三轮排序：此时增量为1，对数组[3,2,5,7,6,8,8,11,10]直接进行插入排序算法，就得到了[2,3,5,6,7,8,8,10,11]。

我去，突然想起来为啥不用excel来排版，算了，将就看吧。

6.归并排序算法

　　一种典型的分而治之思想的算法应用，归并排序算法的实现有两种方法：

1. 自上而下的递归
2. 自下而上的迭代

　　分治思想就是把一个大问题切分为若干个小问题，然后分别解决小问题，用这些小问题的答案来解释大问题。拿到归并算法来说，我觉得归并排序算法先是不断进行二分，然后最小单位的两个进行比较，形成若干个排序序列，最后再和二分法反着来将之前分开的若干已排列好的队列从最小单位开始慢慢比较头部然后合并回去。至于迭代和递归，以前看到知乎上一大佬这样形容，用电影来佐证，迭代是《明日边缘》，递归是《盗梦空间》，令人拍案叫绝，至今印象深刻。

其实现代码如下（采用第一种自上而下的递归方式）：

function mergeSort(arr) {
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());
console.log(result)
return result;
}

var arr = [11,8,5,6,3,10,7,8,2];
var result = mergeSort(arr);

排序流程图;

7.快速排序算法

　　如果说希尔排序算法是插入排序算法的plus版本，那么快速排序算法算是冒泡排序的plus版本了吧。其通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序队列。快速排序算法，字如其算法，听说是排序算法中数一数二的快了，效率非常高。上文也说到了，这是旧版的排序sort()在数组长度大于等于10的情况下采用的排序算法。

其实现代码如下：

function quickSort(array) {
var length = array.length;
if(length <= 1) {
return array;
}else{
var smaller = [];
var bigger = [];
var base = [array[0]];
for(var i = 1; i < length; i++) {
if(array[i] <= base[0]) {
smaller.push(array[i]);
}else{
bigger.push(array[i]);
}
}
console.log(smaller.concat(base.concat(bigger)));
return quickSort(smaller).concat(base.concat(quickSort(bigger)));
}
}


var arr = [11,8,5,6,3,10,7,8,2];
var result = quickSort(arr);

排序流程图（这个流程图是按照array[i] < base[0]，主要是注意数组[11,8,5,6,3,10,7,8,2]中两个元素8的站位问题）：

是不是还是看不懂？再上一个图，这下看懂了吧，就是逼着你站队，以每轮的第一个元素为基准，你比它大就站到右边队伍去，比它小就站到左边队伍去，直到最后每个队伍都只剩自己孤单一元素的时候，排序就完成了。（这个图是按照array[i] <= base[0]分析的，主要是注意数组[11,8,5,6,3,10,7,8,2]中两个元素8的站位问题）

8.其他的排序算法

　　其实还有其他的排序算法，像什么堆排序、计数排序、基数排序、桶排序，这里就不展开了，我也不会，手动狗头。

乱序算法

　　说了辣么多排序算法，再来点乱序算法，先说点题外话，肯定很多人觉得利用sort方法就能实现乱序，其实现代码如下：

function randomSort() {
return Math.random()-0.5;
}

var arr = [1,2,3,4,5,6,7,8,9];
var result = arr.sort(randomSort);

　　以前我也是这么认为的，但是之后看到一篇文章说，Math.random()是个伪随机，于是我去官网看了下api：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Math/random

也就是说random其实是以初始种子作为基准，一般都是默认取时间戳为种子，然后进行一系列固定的算法最终得到一个介于0和1之间的浮点数，也就是说只要知道种子的值，最后的结果是可以复刻的。最后我还是不死心，想自己测试下，于是就有了以下代码：

function test(num){
var arr = [0,1,2,3,4,5,6,7,8,9];
var total=[0,0,0,0,0,0,0,0,0,0];
var result=[];
for(var i=0;i<num;i++){
var tempArr=[...arr].sort(randomSort);
for(var j=0;j<tempArr.length;j++){
total[j]+=tempArr[j];
}
}
total.forEach(item=>{
item=parseFloat((item/num).toFixed(3));
result.push(item)
})
return result;
}

var num=1000;
var result=test(num);
console.log(result);

　　先解释下，如果random是随机的，那么数组[0,1,2,3,4,5,6,7,8,9]经过n次之后的randomSort方法，那么最后每次每个位置上的值应该会无限趋同于平均值4.5，但是从上图我们可以看出，明显数值越大的出现的机率会更高，所以它确实是个伪随机数。所以，真正的乱序算法在下面。

1.Fisher–Yates（费舍尔耶茨）算法，洗牌算法

　　恩，这个名字就很直接了，和插入排序算法可以搞一桌子了。洗牌的动作嘛我不说都很熟悉，就是拿出一坨牌随机插入牌堆的位置，不断重复几次顺序就乱了。

其实现代码如下：

function shuffle(array) {
for(var i = array.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = array[randomIndex];
array[randomIndex] = array[i];
array[i] = itemAtIndex;
console.log(array);
}
return array;
}
var arr = [2,3,5,6,7,8,8,10,11];
var result = shuffle(arr);

　　最后把我写的测试方法修改一下，将var tempArr=[...arr].sort(randomSort);替换为var tempArr=shuffle([...arr]);得出的结果如下，大部分都接近于4.5，甚至在1000000次的运算中，几乎每个位置都等于4.5了。

2.随机抽取算法

　　这个就和洗牌算法差不多了，异曲同工，看下代码就懂了。

其实现代码如下：

function randomlySelected(arr) {
var array= [];
while (arr.length) {
var randomIndex = Math.floor(Math.random()*arr.length);
array.push(arr[randomIndex]);
arr.splice(randomIndex, 1); console.log(array);
}
return array;
}

var arr = [2,3,5,6,7,8,8,10,11];
var result = randomlySelected(arr);

测试的结果也挺不错。

　　不知不觉，就码了这么多字了，子曰：温故而知新，总结这些js排序算法和乱序算法，不仅是对自己过往认知的总结，也是对之前的模糊不清的地方进行了梳理，感觉又深刻了亿内内了呢，告辞。