紙上得來終覺淺，絕知此事要躬行！

在上一篇文章中，我們簡單介紹了 arr.sort() 方法的基本使用：

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);}// 源碼我就不放了，大家有興趣研究的話，可以點擊上面的連結自行查看

代碼分析：

v8 中實現 sort() 方法時，採用了」插入排序「和」快速排序「兩種排序方式。
對於短數組（長度 <= 22）來說，插入排序效率更高。
如果沒有傳入 comparefn ，則生成一個 comparefn 比較函數。
在自動生成的比較函數中，會將傳入的數組元素通過 TO_STRING 方法轉換為字符串，再行比較。
對比比較函數中的 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 是降序排列即可。

~本文完

學習有趣的知識，結識有趣的朋友，塑造有趣的靈魂！

大家好！我是〖編程三昧〗的作者 隱逸王，我的公眾號是『編程三昧』，歡迎關注，希望大家多多指教！

知識與技能並重，內力和外功兼修，理論和實踐兩手都要抓、兩手都要硬！