算法對于前端工程師來說總有一層神秘色彩，這篇文章通過解讀V8源碼，帶你探索Array.prototype.sort函數下的算法實現。
<!-- more -->
來，先把你用過的和聽說過的排序算法都列出來：
答題環節到了， sort 函數使用的以上哪一種算法？
如果你在網上搜索過關于 sort 源碼的文章，可能會告訴你數組長度小于10用插入排序，否則用快速排序。
開始我也是這么認為的，可當我帶著答案去 GitHub 驗證的時候發現并非如此。
首先我并沒有找到對應的 js 源碼（文章說實現邏輯是用js寫的），因為但新版本的V8源碼已經修改，改用V8 Torque。V8 Torque是專門用來開發V8而創造的語言，語法類似TypeScript（再一次證明TypeScript的價值），它的編譯器使用CodeStubAssembler轉換成高效的匯編代碼。
簡單理解起來就是創造了一個類似TypeScript的高效的高級語言，這個語言的文件后綴是tq。
這里需要感謝 justjavac 大神指點~
其次當我開始閱讀源碼的時候，并沒有找到使用快速排序的代碼，也沒有找到判斷數組長度的常數值10。
所有的證據表明，之前的源碼解讀文章很可能已經過時。
那么最新版本的 V8 用的是什么排序算法呢？
V8引擎在xx版本之后就舍棄了快速排序，因為它不是穩定的排序算法，在最壞情況下，時間復雜度會降級到O(n^2)。
而是采用了一種混合排序的算法：TimSort。
這種功能算法最初用于Python語言中，嚴格地說它t不屬于以上10種排序算法中的任何一種，屬于一種混合排序算法：
在數據量小的子數組中使用插入排序，然后再使用歸并排序將有序的子數組進行合并排序，時間復雜度為 O(nlogn) 。
結合V8源碼，具體實現步驟如下：
/thrid_party/v8/builtins/array-sort.tq
1386 ArrayPrototypeSort
1403 ArrayTimSort
1369 ArrayTimSortImpl
1260 ComputeMinRunLength // 計算 minRunLength
// while循環
1262 CountAndMakeRun // 計算當前 run 的長度
1267 BinaryInsertionSort // 用插入排序補足 run 長度
1274 MergeCollapse // 放入 pendingRuns 并根據需要進行調整
// 循環結束
1281 MergeForceCollapse // 合并 pendingRuns 中所有 runtq語言雖然有些不一樣，但如果有TypeScript基礎的話閱讀起來應該不成問題。
下面重點解讀3個函數的源碼：
// 在while循環之前調用，每次排序只調用一次，用來計算 minRunLength
macro ComputeMinRunLength(nArg: Smi): Smi {
let n: Smi = nArg;
let r: Smi = 0;
assert(n >= 0);
// 不斷除以2，得到結果在 32~64 之間
while (n >= 64) {
r = r | (n & 1);
n = n >> 1;
}
const minRunLength: Smi = n + r;
assert(nArg < 64 || (32 <= minRunLength && minRunLength <= 64));
return minRunLength;
}// 計算第一個 run 的長度
macro CountAndMakeRun(implicit context: Context, sortState: SortState)(
lowArg: Smi, high: Smi): Smi {
assert(lowArg < high);
// 這里保存的才是我們傳入的數組數據
const workArray = sortState.workArray;
const low: Smi = lowArg + 1;
if (low == high) return 1;
let runLength: Smi = 2;
const elementLow = UnsafeCast<JSAny>(workArray.objects[low]);
const elementLowPred = UnsafeCast<JSAny>(workArray.objects[low - 1]);
// 調用比對函數來比對數據
let order = sortState.Compare(elementLow, elementLowPred);
const isDescending: bool = order < 0 ? true : false;
let previousElement: JSAny = elementLow;
// 遍歷子數組并計算 run 的長度
for (let idx: Smi = low + 1; idx < high; ++idx) {
const currentElement = UnsafeCast<JSAny>(workArray.objects[idx]);
order = sortState.Compare(currentElement, previousElement);
if (isDescending) {
if (order >= 0) break;
} else {
if (order < 0) break;
}
previousElement = currentElement;
++runLength;
}
if (isDescending) {
ReverseRange(workArray, lowArg, lowArg + runLength);
}
return runLength;
}// 調整 pendingRuns ，使棧長度大于3時，所有 run 都滿足 run[n]>run[n+1]+run[n+2] 且 run[n+1]>run2[n+2]
transitioning macro MergeCollapse(context: Context, sortState: SortState) {
const pendingRuns: FixedArray = sortState.pendingRuns;
while (GetPendingRunsSize(sortState) > 1) {
let n: Smi = GetPendingRunsSize(sortState) - 2;
if (!RunInvariantEstablished(pendingRuns, n + 1) ||
!RunInvariantEstablished(pendingRuns, n)) {
if (GetPendingRunLength(pendingRuns, n - 1) <
GetPendingRunLength(pendingRuns, n + 1)) {
--n;
}
MergeAt(n); // 將第 n 個 run 和第 n+1 個 run 進行合并
} else if (
GetPendingRunLength(pendingRuns, n) <=
GetPendingRunLength(pendingRuns, n + 1)) {
MergeAt(n); // 將第 n 個 run 和第 n+1 個 run 進行合并
} else {
break;
}
}
}下次面試前端崗位的時候，如果面試官問你算法題，你可以莞爾一笑地問他/她：
知道 Array 的 sort 函數使用了什么算法嗎？TimSort要不要了解一下？
當然如果因此搞得面試官難堪而導致拿不到offer可別怪作者~
參考：
一部由眾多技術專家推薦，幫你成為具有全面能力和全局視野工程師的進階利器——《了不起的JavaScript工程師》已經在京東、當當、淘寶各大平臺上架了~
點擊下方鏈接即刻踏上屬于你的進階之路吧！
https://u.jd.com/nETVMh
向AI問一下細節
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
