摘要：比較函數(shù)應(yīng)該具有兩個(gè)參數(shù)和，其返回值如下若小于，在排序后的數(shù)組中應(yīng)該出現(xiàn)在之前，則返回一個(gè)小于的值。把這個(gè)安排好，再繼續(xù)之前的冒泡排序。

受大學(xué)室友的鼓動(dòng)，我也打算利用公眾平臺(tái)來記錄自己的前端知識(shí)積累，同時(shí)呢，自己總結(jié)的東西，總歸會(huì)有局限性，希望小伙伴能給我指點(diǎn)迷津。知識(shí)就是一張巨大的網(wǎng)，作為一名摸不清頭緒的入學(xué)者，唯一能做的事情就是吐好每一根絲，絲擰成線，線再織成網(wǎng)。好啦，開機(jī)儀式over，廢話不多說了啦...

關(guān)于Sort()這個(gè)函數(shù)，決定研究它是因?yàn)樵诳慈罾蠋煹募^函數(shù)時(shí)，最后有一個(gè)小練習(xí)：
請(qǐng)使用箭頭函數(shù)簡(jiǎn)化排序時(shí)傳入的函數(shù)：

var arr = [10, 20, 1, 2];
arr.sort((x, y) => {
    ???
});
console.log(arr); // [1, 2, 10, 20]

因?yàn)橹癹s基礎(chǔ)也不扎實(shí)，沒有g(shù)et到這個(gè)題的核心，想了想寫了寫，最后放棄了，看了評(píng)論里的答案。我的天，就一句——return x - y;，當(dāng)時(shí)我就覺得這個(gè)函數(shù)太神奇了，這么簡(jiǎn)單的解決了數(shù)組排序。（上大學(xué)那會(huì)，懶惰致死的我所有排序算法原理都明明白白，但是從來沒有寫過，于是就...后悔莫及阿）

了解原理先從函數(shù)定義入手，于是乎...從W3C上搬了一段解釋：

定義和用法: sort() 方法用于對(duì)數(shù)組的元素進(jìn)行排序。

語法: arrayObject.sort(sortby)

返回值: 對(duì)數(shù)組的引用。請(qǐng)注意，數(shù)組在原數(shù)組上進(jìn)行排序，不生成副本。

說明:

如果調(diào)用該方法時(shí)沒有使用參數(shù)，將按字母順序?qū)?shù)組中的元素進(jìn)行排序，說得更精確點(diǎn)，是按照字符編碼的順序進(jìn)行排序。要實(shí)現(xiàn)這一點(diǎn)，首先應(yīng)把數(shù)組的元素都轉(zhuǎn)換成字符串（如有必要），以便進(jìn)行比較。

如果想按照其他標(biāo)準(zhǔn)進(jìn)行排序，就需要提供比較函數(shù)，該函數(shù)要比較兩個(gè)值，然后返回一個(gè)用于說明這兩個(gè)值的相對(duì)順序的數(shù)字。比較函數(shù)應(yīng)該具有兩個(gè)參數(shù) a 和 b，其返回值如下：
若 a 小于 b，在排序后的數(shù)組中 a 應(yīng)該出現(xiàn)在 b 之前，則返回一個(gè)小于 0 的值。
若 a 等于 b，則返回 0。
若 a 大于 b，則返回一個(gè)大于 0 的值。

怎么查看sort()方法是如果實(shí)現(xiàn)排序的呢？此處參考了前輩的文章《sort排序到底怎么排序》。因?yàn)槲揖吞貏e傻，斷點(diǎn)打到sort()函數(shù)這一行，然后step-into執(zhí)行，不斷在console里打印arr。。。傻的一p
前輩如下實(shí)現(xiàn)的：我們可以在比較函數(shù)里把a(bǔ),b及數(shù)組輸出一下，看看是否能夠看出使用的排序算法。

var arr=[1, 8, 3, 5, -1];
function compare(a,b){
    console.log(a,b,arr);
    return a-b;
}
arr.sort(compare);

控制臺(tái)輸出
1 8 [1, 8, 3, 5, -1]
8 3 [1, 8, 3, 5, -1]
1 3 [1, 8, 8, 5, -1]
8 5 [1, 3, 8, 5, -1]
3 5 [1, 3, 8, 8, -1]
8 -1 [1, 3, 5, 8, -1]
5 -1 [1, 3, 5, 8, 8]
3 -1 [1, 3, 5, 5, 8]
1 -1 [1, 3, 3, 5, 8]
[-1,1, 3, 5, 8]
*/
? 第一次1和8比較，1<8，不需要調(diào)整位置。 ??

　　第二次8和3比較，8>3，需要調(diào)整位置。但是這里沒有交換位置，僅僅是8覆蓋了3位置。這里就可以推斷出不是單純的使用了冒泡算法。
??第三是1和3比較，1<3，3替換了8的位置。什么鬼，幾個(gè)意思？？？看到這里我也是表示不懂呀。那就繼續(xù)往下看咯。 ??

　　第四是8和5比較，8>5，又僅僅是覆蓋，沒有交換位置。還是不懂，繼續(xù)往下！
??第五是3和5比較，3<5，5替換了8的位置，不懂，繼續(xù)往下！ ??

　　第六是8和-1比較，8>-1， 還僅僅是覆蓋，繼續(xù)往下！
??第七、八、九次，-1依次和5，3，1做了比較，并且5，3，1都移動(dòng)了一次位置。

　　我們得出了結(jié)論：sort()方法是使用的冒泡和插入兩種方式結(jié)合進(jìn)行排序的。

這里我用自己的話總結(jié)一下：
冒泡排序：

第一輪：從第一個(gè)元素開始，相鄰元素比較，前者比后者大，互換位置，下標(biāo)加一；再繼續(xù)相鄰元素比較，大的元素移到后面，下標(biāo)加一再比較...這樣一輪比較下來，最后一個(gè)元素一定是數(shù)組里最大的元素。

第二輪及之后：好啦，現(xiàn)在最后一個(gè)元素（即最大的元素）確定了，將其排除在外，我們?cè)賮韽念^對(duì)比除它之外的元素，將倒數(shù)第二大的元素移到倒數(shù)第二個(gè)位置。以此類推，每一輪確定一個(gè)元素的位置，就像小魚吐泡泡一樣，大的泡泡一點(diǎn)一點(diǎn)往上移

function bubbel(arr) {
    var len=arr.length;
    for(var i=0; i arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

插入排序：
1.第一輪：將第一個(gè)元素看成只有一個(gè)元素的有序數(shù)組，拿第二個(gè)元素和它比較，比它小就插到它前面，比它大就插到它后面。
2.第二輪：經(jīng)過第一輪，前兩個(gè)元素已為有序數(shù)組。再拿第三個(gè)元素和前兩個(gè)元素比較，看插在哪合適。以此類推。一般會(huì)新建一個(gè)數(shù)組記錄排序后的數(shù)組。

// 插入排序 從下標(biāo)1開始每增1項(xiàng)排序一次，越往后遍歷次數(shù)越多
function sort1(array) {
  var len = array.length,
      i, j, tmp, result;
  
  // 設(shè)置數(shù)組副本
  result = array.slice(0);
  for(i=1; i < len; i++){
    tmp = result[i];
    j = i - 1;
    while(j>=0 && tmp < result[j]){
      result[j+1] = result[j];
      j--;
    }
    result[j+1] = tmp;
  }
  return result;
}

前面鋪墊了這么多，終于到了今天的重點(diǎn)——冒泡排序和插入排序是如何混合使用的？即sort()實(shí)現(xiàn)的原理。先上我的代碼！! 時(shí)隔多年，我終于不再懶惰，勇敢寫出我的代碼。希望努力不要太晚~

var arr = [1, 8, 3, 5, -1];
    var len = arr.length;
    function compareSet(temp, compare_i){
        for(var i = compare_i; i > 0; i--){
            if(temp > arr[i-1]){
                arr[i] = temp;
                break;
            }
            else{
                arr[i] = arr[i-1];
                arr[i-1] = temp;
            }
        }
    }
    for(var i = 0; i < len; i++){
        if(arr[i] > arr[i+1]){
            var temp = arr[i+1];
            arr[i+1] = arr[i];
            console.log(arr);            
            compareSet(temp, i);
        }
        
    }
    console.log(arr);

根據(jù)之前分析sort()排序控制臺(tái)輸出，先是像冒泡排序那樣相鄰的元素比較。但是，一旦出現(xiàn)需要換位置的操作時(shí)，不再是像插入排序那樣直接交換。而是先用變量temp暫存arr[i+1]，再將較大的arr[i]移到[i+1]位置上，對(duì)暫存變量temp使用插入排序，將其插入前0 ~ [i-1]有序數(shù)組中。把這個(gè)temp安排好，再繼續(xù)之前的冒泡排序。
**冒泡排序是元素對(duì)調(diào)后這一輪就不管事了，要重復(fù)i-1輪冒泡。
插入排序是不管現(xiàn)有元素的順序是否正確，都給你在已有序數(shù)組從頭比較到尾。**
所以，混合起來666。

這里還有一個(gè)前輩寫的sort()實(shí)現(xiàn)，我對(duì)比一下，我的運(yùn)行速度18ms，前輩的25ms。其實(shí)我感覺我寫的沒有前輩的簡(jiǎn)潔，但不知道為什么我的快一些。之后再仔細(xì)研究研究。

            [function findMinIndex(arr,start){
                var iMin=arr[start];
                var iMinIndex=start;
                for(var i=start;iarr[i]){
                        iMin=arr[i];
                        iMinIndex=i;
                    }
                }
                return iMinIndex;
            }
            for(var i=0;i
其實(shí)，寫到這里，應(yīng)該結(jié)束了！但是我忽然想起來，大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課上，我最喜歡的魏萊老師好像給我們說過這個(gè)混合排序算法的。老師一步步引導(dǎo)我們思考的場(chǎng)景還歷歷在目，我甚至都可以回想起老師說話時(shí)的語氣。可是，我卻還的差不多了，實(shí)在是可惡?。?！