const arr = [49, 5, 14, 89, 71, 3, 10];

// 一般寫法
arr.sort(function (a, b) {
    return a - b;   // 按照升序排列 
});

// 箭頭函數
arr.sort((a, b) => a - b);

// 結果  [3, 5, 10, 14, 49, 71, 89]

用歸用，照葫蘆畫瓢不難，大家日常也是這麼寫的，沒毛病！但是如果對一個方法不進行深入研究，那麼就很容易踩坑，並且常常會填不了坑！

今天，我們重點聊聊比較函數 compareFunction 相關的知識。

為了接下來的思路能夠更順暢，在學習比較函數之前，我們先來了解一下有關插入排序的原理。

插入排序

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

算法描述：

一般來說，插入排序都採用 in-place 在數組上實現：

• 從第一個元素開始，該元素可以認為已經被排序；
• 取出下一個元素，在已經排序的元素序列中從後向前掃描；
• 如果該元素（已排序）大於新元素，將該元素移到下一位置；
• 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；
• 將新元素插入到該位置後；
• 重複步驟2~5。

動圖演示：

插入排序

其實可以用一句話總結：從數組中第二個元素起（第一個元素已默認排序），每個元素都充當一次游標值，依次和它前面的（已排序）的元素相比較，如果游標值小，則將拿來比較的元素向後移一位，繼續向前比較；否則，將游標值插入比較值的後面，結束比較。

關於比較函數 compareFunction

如果想要 sort() 方法按照一定的規則進行排序（比如數字大小），那麼就需要給它指定比較函數 compareFunction。

如果指明了 compareFunction ，那麼數組會按照調用該函數的返回值排序，它有兩個參數 a 和 b，返回值如下：

• 如果 compareFunction(a, b) 小於 0 ，那麼 a 會被排列到 b 之前。
• 如果 compareFunction(a, b) 等於 0 ， a 和 b 的相對位置不變。
• 如果 compareFunction(a, b) 大於 0 ， b 會被排列到 a 之前。
• compareFunction(a, b) 必須總是對相同的輸入返回相同的比較結果，否則排序的結果將是不確定的。

compareFunction 初步探究

我們暫不做什麼複雜的分析，先使用控制台打印一下看看 a 和 b 到底是什麼：

const arr = [49, 5, 14, 89, 71, 3, 10];
console.log(arr);
let times = 0;
let res = [];
arr.sort((a, b) => {
    res.push({times, a, b, "a - b": a - b});
    times++;
    return a - b;
});
console.log(res);
console.log(arr);

執行結果如下：

通過上圖，我們可以看到：

• a 的值在按照原數組中的順序依次變化，這個排序採用的應該是插入排序法。
• a 代表的應該是游標。
• 從 b 值的變化上又可以看出，a 首次找位置時採用了二分法，a < b 則向前比較， a>b 則向後比較。

那麼，其機理到底是不是我們所看到這樣一個過程，還需要再探究。

compareFunction 深入探究

要想弄清楚一個問題，還有什麼比從根源上着手效率更高的呢？所以我們追根溯源，先來扒一扒 v8引擎 的源碼，看看它內部到底是怎麼實現 sort 接口的。

下面的源碼來自7.2版本之前的 v8，該版本之後的數組排序實現變化較大，暫不予討論。

其中 array.js 文件下，關於 sort 接口實現的代碼如下：

function InnerArraySort(array, length, comparefn) {
    // In-place QuickSort algorithm.
    // For short (length <= 22) arrays, insertion sort is used for efficiency.

    if (!IS_CALLABLE(comparefn)) {
        comparefn = function (x, y) {
            if (x === y) return 0;
            if (% _IsSmi(x) && % _IsSmi(y)) {
                return % SmiLexicographicCompare(x, y);
            }
            // 將數組元素轉換為字符串
            x = TO_STRING(x);
            y = TO_STRING(y);
            if (x == y) return 0;
            else return x < y ? -1 : 1;
        };
    }
    var InsertionSort = function InsertionSort(a, from, to) {
        for (var i = from + 1; i < to; i++) {
            var element = a[i];
            for (var j = i - 1; j >= from; j--) {
                var tmp = a[j];
                // 調用比較函數 a: tmp, b: element
                var order = comparefn(tmp, element);
                if (order > 0) {
                    a[j + 1] = tmp;
                } else {
                    break;
                }
            }
            a[j + 1] = element;
        }
    };

    /*** some code here **/ 

    var QuickSort = function QuickSort(a, from, to) {
        /*** some code here **/ 
    };
}

function ArraySort(comparefn) {
  	CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");

  	var array = TO_OBJECT(this);
  	var length = TO_LENGTH(array.length);
  	return InnerArraySort(array, length, comparefn);
}

// 源碼我就不放了，大家有興趣研究的話，可以點擊上面的鏈接自行查看

代碼分析：

1. v8 中實現 sort() 方法時，採用了 ”插入排序“ 和 ”快速排序“ 兩種排序方式。
2. 對於短數組（長度 <= 22）來說，插入排序效率更高。
3. 如果沒有傳入 comparefn ，則生成一個 comparefn 比較函數。
4. 在自動生成的比較函數中，會將傳入的數組元素通過 TO_STRING 方法轉換為字符串，再行比較。
5. 對比比較函數中的 b 為游標值，這一點和最新版的 chrome 瀏覽器表現不同。

我們在 sort 方法中傳入的函數用在了這裡：

var order = comparefn(tmp, element);

根據我們傳入函數的返回值，數組進行排序操作：

if (order > 0) {
    a[j + 1] = tmp;
} else {
    break;
}

• 如果返回值（a-b）大於0，即 a > b, 則將當前拿來比較的值 a 複製給它的下一位，並繼續使用游標值 b 向前進行比較。
• 如果返回值小於等於 0 ，則結束比較，並將游標值 b 填在最後一次比較值 a 的後面。

總結

不管是舊版本還是最新版本的 v8，它們的 sort() 方法的返回結果都沒有發生變化，只是內部的實現機理有了改變（肯定是向著更優的方向改變）。

為了是 sort() 的返回結果符合預期，我們給它傳入了一個函數作為比較規則。

在比較函數中，因 v8 版本不同，實現機制有差異，導致它的參數意義也不大相同，所以我們暫時無需關心它裡面參數的具體含義。

比較函數如果寫完全的話，應該是：

arr.sort((a,b) => {
    const res = a - b;
    return res > 0 ? 1 : (res < 0 ? -1 : 0 );
});

即比較函數的返回值嚴格來說只有三個：-1、0 和 1 。

我們主需要記住 return a – b 是升序排列，return b – a 是降序排列即可。