摘要：比較函數應該具有兩個參數和，其返回值如下若小于，在排序后的數組中應該出現在之前，則返回一個小于的值。把這個安排好，再繼續之前的冒泡排序。

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

關于Sort()這個函數，決定研究它是因為在看阮老師的箭頭函數時，最后有一個小練習：
請使用箭頭函數簡化排序時傳入的函數：

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

因為之前js基礎也不扎實，沒有get到這個題的核心，想了想寫了寫，最后放棄了，看了評論里的答案。我的天，就一句——return x - y;，當時我就覺得這個函數太神奇了，這么簡單的解決了數組排序。（上大學那會，懶惰致死的我所有排序算法原理都明明白白，但是從來沒有寫過，于是就...后悔莫及阿）

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

定義和用法: sort() 方法用于對數組的元素進行排序。

語法: arrayObject.sort(sortby)

返回值: 對數組的引用。請注意，數組在原數組上進行排序，不生成副本。

說明:

如果調用該方法時沒有使用參數，將按字母順序對數組中的元素進行排序，說得更精確點，是按照字符編碼的順序進行排序。要實現這一點，首先應把數組的元素都轉換成字符串（如有必要），以便進行比較。

如果想按照其他標準進行排序，就需要提供比較函數，該函數要比較兩個值，然后返回一個用于說明這兩個值的相對順序的數字。比較函數應該具有兩個參數 a 和 b，其返回值如下：
若 a 小于 b，在排序后的數組中 a 應該出現在 b 之前，則返回一個小于 0 的值。
若 a 等于 b，則返回 0。
若 a 大于 b，則返回一個大于 0 的值。

怎么查看sort()方法是如果實現排序的呢？此處參考了前輩的文章《sort排序到底怎么排序》。因為我就特別傻，斷點打到sort()函數這一行，然后step-into執行，不斷在console里打印arr。。。傻的一p
前輩如下實現的：我們可以在比較函數里把a,b及數組輸出一下，看看是否能夠看出使用的排序算法。

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

控制臺輸出
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，不需要調整位置。 ??

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

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

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

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

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

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

第二輪及之后：好啦，現在最后一個元素（即最大的元素）確定了，將其排除在外，我們再來從頭對比除它之外的元素，將倒數第二大的元素移到倒數第二個位置。以此類推，每一輪確定一個元素的位置，就像小魚吐泡泡一樣，大的泡泡一點一點往上移

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.第一輪：將第一個元素看成只有一個元素的有序數組，拿第二個元素和它比較，比它小就插到它前面，比它大就插到它后面。
2.第二輪：經過第一輪，前兩個元素已為有序數組。再拿第三個元素和前兩個元素比較，看插在哪合適。以此類推。一般會新建一個數組記錄排序后的數組。

// 插入排序 從下標1開始每增1項排序一次，越往后遍歷次數越多
function sort1(array) {
  var len = array.length,
      i, j, tmp, result;
  
  // 設置數組副本
  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;
}

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

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

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

這里還有一個前輩寫的sort()實現，我對比一下，我的運行速度18ms，前輩的25ms。其實我感覺我寫的沒有前輩的簡潔，但不知道為什么我的快一些。之后再仔細研究研究。

            [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
其實，寫到這里，應該結束了！但是我忽然想起來，大學《數據結構》課上，我最喜歡的魏萊老師好像給我們說過這個混合排序算法的。老師一步步引導我們思考的場景還歷歷在目，我甚至都可以回想起老師說話時的語氣?？墒?，我卻還的差不多了，實在是可惡?。?！