點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”

優(yōu)質(zhì)文章，第一時(shí)間送達(dá)

  作者 |  他好像一條狗啊

來(lái)源 |  urlify.cn/NnAZFj

其實(shí)本人最怕的就是算法，大學(xué)算法課就感覺老師在講天書，而且對(duì)于前端來(lái)說(shuō)，算法在實(shí)際的應(yīng)用中實(shí)在是很有限。畢竟算法要依靠大量的數(shù)據(jù)為基礎(chǔ)才能發(fā)揮出算法的效率，就瀏覽器那性能，......是吧，退一萬(wàn)步說(shuō)，真的有人把這大量的數(shù)據(jù)處理業(yè)務(wù)放到前端，那我只能說(shuō)這是團(tuán)隊(duì)和架構(gòu)師的失職，不說(shuō)頁(yè)面應(yīng)用能不能加載出來(lái)，等你靠前端算出來(lái)，用戶早就跑了。所以，就目前而言，絕大部分的算法使用場(chǎng)景都不在前端，就那么些數(shù)據(jù)量放在那，前端使用算法除了加重代碼邏輯沒有更多的好處。當(dāng)然話又說(shuō)回來(lái)了，我也知道這是個(gè)好東西，所以我也會(huì)去了解一點(diǎn)。這里就不說(shuō)什么高深的算法了，先總結(jié)下相對(duì)簡(jiǎn)單的排序算法吧，以下均為js實(shí)現(xiàn)。

排序算法

1.TimSort算法

　　看到這個(gè)算法名，大多數(shù)前端er都不知道這是什么算法吧，但是我要是說(shuō)這個(gè)是實(shí)現(xiàn)大名鼎鼎v8引擎的sort()的核心算法，你們就應(yīng)該恍然大悟了吧。舊版的排序sort()原理大家應(yīng)該很熟悉了，數(shù)組長(zhǎng)度小于10用插入排序，否則使用快速排序。舊版的排序sort()源碼地址：https://github.com/v8/v8/blob/5.9.221/src/js/array.js#L996

　　而新版的排序sort()源碼使用Torque語(yǔ)言編寫，源碼備注是基于python的某一版本TimSort算法實(shí)現(xiàn)的，大致原理是歸并排序和插入排序的混合排序算法：針對(duì)現(xiàn)實(shí)中需要排序的數(shù)據(jù)分析看，大多數(shù)據(jù)通常是有部分已經(jīng)排好序的數(shù)據(jù)塊，Timsort 稱這些已經(jīng)排好序（不管是升序還是降序）的數(shù)據(jù)塊為 “run”。又因?yàn)樵诤喜⑿蛄械臅r(shí)候，如果run的數(shù)量等于或者略小于2的冪次方的時(shí)候，效率是最高的，所以run要有一定的約束，于是根據(jù)序列長(zhǎng)度定義了一個(gè)minrun，如果原始的run小于minrun的長(zhǎng)度，用插入排序擴(kuò)充run，最后將這些run用歸并排序合并序列，得到最后的run就是排序后的結(jié)果。有興趣的可以了解下源碼，反正我看不懂，說(shuō)到這，突然開始懷念舊版源碼了。新版的排序sort()源碼地址：https://github.com/v8/v8/blob/master/third_party/v8/builtins/array-sort.tq。

　　大多數(shù)前端排序場(chǎng)景用這個(gè)方法就已經(jīng)足夠了，默認(rèn)排序順序（沒有攜帶參數(shù)）是在將元素轉(zhuǎn)換為字符串后，然后比較按照它們的UTF-16字符編碼的順序進(jìn)行排序，如果要比較數(shù)字的話，就需要傳入?yún)?shù)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.冒泡排序算法

　　這個(gè)可以說(shuō)是最基礎(chǔ)的或是最常見的了吧，尤其是其形象的命名“冒泡”深入人心，顧名思義，經(jīng)過不斷的交換，最大的數(shù)會(huì)像水中的泡泡一樣慢慢往上浮動(dòng)，直至頂端。它會(huì)在未排序隊(duì)列內(nèi)，依次比較兩個(gè)相鄰的元素，把較大的元素放置于更靠頂端的位置。

其實(shí)現(xiàn)代碼如下：

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.選擇排序算法

　　在未排序隊(duì)列內(nèi)，選擇其中最小的元素，然后和第一個(gè)元素進(jìn)行位置互換，以此類推，直到所有元素排序完畢。

其實(shí)現(xiàn)代碼如下：

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.插入排序算法

　　這個(gè)算法打過斗地主或是跑的快的應(yīng)該很熟悉，我這樣說(shuō)就明白了：就是抓到牌之后，我們會(huì)先展開牌，然后先把第一張放到左邊（排序隊(duì)列），然后把第二張（可以看為未排序隊(duì)列第一張）從右邊（未排序隊(duì)列）再拿到左邊去按從小到大進(jìn)行排序，放到合適的位置。恩，形象的丫批。上文也說(shuō)到了，這是舊版的排序sort()在數(shù)組長(zhǎng)度小于10的情況下采用的排序算法。

其實(shí)現(xiàn)代碼如下：

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.希爾排序算法

　　希爾排序算法是以其設(shè)計(jì)者shell的名字命名的排序算法，又稱縮小增量排序，算是個(gè)插入排序算法的plus版本。它的本質(zhì)是多個(gè)分組同時(shí)進(jìn)行插入排序算法，所以會(huì)比插入排序算法更加高效。核心是，這個(gè)多個(gè)分組是按照隊(duì)列的下標(biāo)進(jìn)行一定的增量分組。

其實(shí)現(xiàn)代碼如下：

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);

這個(gè)沒有流程圖，只能一步一步解釋了。首先，gap就是增量，通過整個(gè)流程最后可以得出，gap依次取值為：5,2,1,0；

　　一輪排序：根據(jù)增量5，對(duì)數(shù)組[11,8,5,6,3,10,7,8,2]而言就是11和10比較，8和7比較，5和8比較，6和2比較，最后剩下一個(gè)3不動(dòng)；兩兩比較，大小互換位置，得到數(shù)組[10,7,5,2,3,11,8,8,6]；

　　　　　　 注意，這里互換位置的時(shí)候是按照下標(biāo)來(lái)互換的，這樣光說(shuō)看起來(lái)比較蒼白無(wú)力，換成二維的吧

　　二輪排序：此時(shí)增量為2，對(duì)數(shù)組[10,7,5,2,3,11,8,8,6]而言就是分為[10,5,3,8,6]比較，[7,2,11,8]比較，兩組分別進(jìn)行插入算法，大小互換位置，得到[3,5,6,8,10]和[2,7,8,11]，即是[3,2,5,7,6,8,8,11,10]；

        三輪排序：此時(shí)增量為1，對(duì)數(shù)組[3,2,5,7,6,8,8,11,10]直接進(jìn)行插入排序算法，就得到了[2,3,5,6,7,8,8,10,11]。

        我去，突然想起來(lái)為啥不用excel來(lái)排版，算了，將就看吧。

6.歸并排序算法

　　一種典型的分而治之思想的算法應(yīng)用，歸并排序算法的實(shí)現(xiàn)有兩種方法：

1. 自上而下的遞歸

2. 自下而上的迭代

　　分治思想就是把一個(gè)大問題切分為若干個(gè)小問題，然后分別解決小問題，用這些小問題的答案來(lái)解釋大問題。拿到歸并算法來(lái)說(shuō)，我覺得歸并排序算法先是不斷進(jìn)行二分，然后最小單位的兩個(gè)進(jìn)行比較，形成若干個(gè)排序序列，最后再和二分法反著來(lái)將之前分開的若干已排列好的隊(duì)列從最小單位開始慢慢比較頭部然后合并回去。至于迭代和遞歸，以前看到知乎上一大佬這樣形容，用電影來(lái)佐證，迭代是《明日邊緣》，遞歸是《盜夢(mèng)空間》，令人拍案叫絕，至今印象深刻。

其實(shí)現(xiàn)代碼如下（采用第一種自上而下的遞歸方式）：

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.快速排序算法

　　如果說(shuō)希爾排序算法是插入排序算法的plus版本，那么快速排序算法算是冒泡排序的plus版本了吧。其通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序隊(duì)列?？焖倥判蛩惴?，字如其算法，聽說(shuō)是排序算法中數(shù)一數(shù)二的快了，效率非常高。上文也說(shuō)到了，這是舊版的排序sort()在數(shù)組長(zhǎng)度大于等于10的情況下采用的排序算法。

其實(shí)現(xiàn)代碼如下：

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);

排序流程圖（這個(gè)流程圖是按照array[i] < base[0]，主要是注意數(shù)組[11,8,5,6,3,10,7,8,2]中兩個(gè)元素8的站位問題）：

是不是還是看不懂？再上一個(gè)圖，這下看懂了吧，就是逼著你站隊(duì)，以每輪的第一個(gè)元素為基準(zhǔn)，你比它大就站到右邊隊(duì)伍去，比它小就站到左邊隊(duì)伍去，直到最后每個(gè)隊(duì)伍都只剩自己孤單一元素的時(shí)候，排序就完成了。（這個(gè)圖是按照array[i] <= base[0]分析的，主要是注意數(shù)組[11,8,5,6,3,10,7,8,2]中兩個(gè)元素8的站位問題）

8.其他的排序算法

　　其實(shí)還有其他的排序算法，像什么堆排序、計(jì)數(shù)排序、基數(shù)排序、桶排序，這里就不展開了，我也不會(huì)，手動(dòng)狗頭。

亂序算法

　　說(shuō)了辣么多排序算法，再來(lái)點(diǎn)亂序算法，先說(shuō)點(diǎn)題外話，肯定很多人覺得利用sort方法就能實(shí)現(xiàn)亂序，其實(shí)現(xiàn)代碼如下：

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

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

　　以前我也是這么認(rèn)為的，但是之后看到一篇文章說(shuō)，Math.random()是個(gè)偽隨機(jī)，于是我去官網(wǎng)看了下api：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Math/random

 也就是說(shuō)random其實(shí)是以初始種子作為基準(zhǔn)，一般都是默認(rèn)取時(shí)間戳為種子，然后進(jìn)行一系列固定的算法最終得到一個(gè)介于0和1之間的浮點(diǎn)數(shù)，也就是說(shuō)只要知道種子的值，最后的結(jié)果是可以復(fù)刻的。最后我還是不死心，想自己測(cè)試下，于是就有了以下代碼：

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是隨機(jī)的，那么數(shù)組[0,1,2,3,4,5,6,7,8,9]經(jīng)過n次之后的randomSort方法，那么最后每次每個(gè)位置上的值應(yīng)該會(huì)無(wú)限趨同于平均值4.5，但是從上圖我們可以看出，明顯數(shù)值越大的出現(xiàn)的機(jī)率會(huì)更高，所以它確實(shí)是個(gè)偽隨機(jī)數(shù)。所以，真正的亂序算法在下面。

1.Fisher–Yates（費(fèi)舍爾耶茨）算法，洗牌算法

　　恩，這個(gè)名字就很直接了，和插入排序算法可以搞一桌子了。洗牌的動(dòng)作嘛我不說(shuō)都很熟悉，就是拿出一坨牌隨機(jī)插入牌堆的位置，不斷重復(fù)幾次順序就亂了。

其實(shí)現(xiàn)代碼如下：

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);

　　最后把我寫的測(cè)試方法修改一下，將var tempArr=[...arr].sort(randomSort);替換為var tempArr=shuffle([...arr]);得出的結(jié)果如下，大部分都接近于4.5，甚至在1000000次的運(yùn)算中，幾乎每個(gè)位置都等于4.5了。

2.隨機(jī)抽取算法

　　這個(gè)就和洗牌算法差不多了，異曲同工，看下代碼就懂了。

其實(shí)現(xiàn)代碼如下：

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);

 測(cè)試的結(jié)果也挺不錯(cuò)。

 　　不知不覺，就碼了這么多字了，子曰：溫故而知新，總結(jié)這些js排序算法和亂序算法，不僅是對(duì)自己過往認(rèn)知的總結(jié)，也是對(duì)之前的模糊不清的地方進(jìn)行了梳理，感覺又深刻了億內(nèi)內(nèi)了呢，告辭。

粉絲福利：Java從入門到入土學(xué)習(xí)路線圖

??????

??長(zhǎng)按上方微信二維碼 2 秒

感謝點(diǎn)贊支持下哈