貌似前端圈一直以來流傳著一種誤解：前端用不到算法知識。長久以來，大家或許都曾受這種說法的影響。直到前陣子遇到一個產品需求，回過頭來看，發現事實並非如此。
前端排序
前端排序的場景
前端將排序條件作為請求參數傳遞給後端，後端將排序結果作為請求響應返回前端，這是一種常見設計。但是對於有些產品則不是那麼適用。
試想一個場景：你在使用美食類APP時，是否會經常切換排序方式，一會兒按照價格排序，一會兒按照評分排序。
實際生產中，受限於服務器成本等因素，當單次數據查詢成為整體性能瓶頸時，也會考慮通過將排序在前端完成的方式來優化性能。
排序算法
感覺這個沒什麼介紹的必要，作為計算機科學的一種基礎算法，描述就直接照搬 Wikipedia。
這裡存在這一段內容純粹是為了承(cou)上(man)啟(zi)下(shu)。
JavaScript的排序
既然說到前端排序，自然首先會想到JavaScript的原生接口 Array.prototype.sort。
這個接口自 ECMAScript 1st Edition 起就存在。讓我們看看最新的規范中關於它的描述是什麼樣的。
Array.prototype.sort規范
Array.prototype.sort(compareFn)
復制代碼 代碼如下:
The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.
顯然，規范並沒有限定 sort 內部實現的排序算法是什麼。甚至接口的實現都不需要是 穩定排序 的。這一點很關鍵，接下來會多次涉及。
在這樣的背景下，前端排序這件事其實取決於各家浏覽器的具體實現。那麼，當今主流的浏覽器關於排序是怎麼實現的呢？接下來，我們分別簡單對比一下 Chrome、Firefox 和 Microsoft Edge。
Chrome中的實現
Chrome 的JavaScript引擎是 v8。由於它是開源的，所以可以直接看源代碼。
整個 array.js 都是用 JavaScript 語言實現的。排序方法部分很明顯比曾經看到過的快速排序要復雜得多，但顯然核心算法還是 快速排序。算法復雜的原因在於 v8 出於性能考慮進行了很多優化。(接下來會展開說)
Firefox中的實現
暫時無法確定Firefox的JavaScript引擎即將使用的數組排序算法會是什麼。[3]
按照現有的信息，SpiderMoney 內部實現了 歸並排序。
Microsoft Edge中的實現
Microsoft Edge 的JavaScript引擎 Chakra 的核心部分代碼已經於2016年初在Github開源。
通過看源代碼可以發現，Chakra 的數組排序算法實現的也是 快速排序。而且相比較於 v8，它就只是實現了純粹的快速排序，完全沒有 v8 中的那些性能優化的蹤影。
JavaScript數組排序的問題
眾所周知，快速排序 是一種不穩定的排序算法，而 歸並排序 是一種穩定的排序算法。由於不同引擎在算法選擇上的差異，導致前端依賴 Array.prototype.sort 接口實現的JavaScript代碼，在浏覽器中實際執行的排序效果是不一致的。
排序穩定性的差異需要有特定的場景觸發才會存在問題；在很多情況下，不穩定的排序也不會造成影響。
假如實際項目開發中，對於數組的排序沒有穩定性的需求，那麼其實看到這裡為止即可，浏覽器之間的實現差異不那麼重要。
但是若項目要求排序必須是穩定的，那麼這些差異的存在將無法滿足需求。我們需要為此進行一些額外的工作。
舉個例子：
某市的機動車牌照拍賣系統，最終中標的規則為：
1. 按價格進行倒排序；
2. 相同價格則按照競標順位（即價格提交時間）進行正排序。
排序若是在前端進行，那麼采用快速排序的浏覽器中顯示的中標者很可能是不符合預期的
探究差異的背後
尋找解決辦法之前，我們有必要先探究一下出現問題的原因。
Chrome為什麼采用快速排序
其實這個情況從一開始便存在。
Chrome測試版 於2008年9月2日發布，然而發布後不久，就有開發者向 Chromium 開發組提交#90 Bug反饋v8的數組排序實現不是穩定排序的。
這個Bug ISSUE討論的時間跨度很大。一直到2015年11月10日，仍然有開發者對v8的數組排序實現問題提出評論。
同時我們還注意到，該ISSUE曾經已被關閉。但是於2013年6月被開發組成員重新打開，作為 ECMAScript Next 規范討論的參考。
而es-discuss的最後結論是這樣的
復制代碼 代碼如下:
It does not change. Stable is a subset of unstable. And vice versa, every unstable algorithm returns a stable result for some inputs. Mark's point is that requiring “always unstable” has no meaning, no matter what language you chose.
/Andreas
正如本文前段所引用的已定稿 ECMAScript 2015 規范中的描述。
時代特點
IMHO，Chrome發布之初即被報告出這個問題可能是有其特殊的時代特點。
上文已經說到，Chrome第一版 是 2008年9月 發布的。根據statcounter的統計數據，那個時期市場占有率最高的兩款浏覽器分別是 IE(那時候只有IE6和IE7) 和 Firefox，市場占有率分別達到了67.16%和25.77%。也就是說，兩個浏覽器加起來的市場占有率超過了90%。
而根據另一份浏覽器排序算法穩定性的統計數據顯示，這兩款超過了90%市場占有率的浏覽器都采用了穩定的數組排序。所以Chrome發布之初被開發者質疑也是合情合理的。
符合規范
從Bug ISSUE討論的過程中，可以大概理解開發組成員對於引擎實現采用快速排序的一些考量。
其中一點，他們認為引擎必須遵守ECMAScript規范。由於規范不要求穩定排序的描述，故他們認為 v8 的實現是完全符合規范的。
性能考慮
另外，他們認為 v8 設計的一個重要考量在於引擎的性能。
快速排序 相比較於 歸並排序，在整體性能上表現更好：
更高的計算效率。快速排序 在實際計算機執行環境中比同等時間復雜度的其他排序算法更快（不命中最差組合的情況下）
更低的空間成本。前者僅有O(㏒n)的空間復雜度，相比較後者O(n)的空間復雜度在運行時的內存消耗更少
v8在數組排序算法中的性能優化
既然說 v8 非常看中引擎的性能，那麼在數組排序中它做了哪些事呢？
通過閱讀源代碼，還是粗淺地學習了一些皮毛。
混合插入排序
快速排序 是分治的思想，將大數組分解，逐層往下遞歸。但是若遞歸深度太大，為了維持遞歸調用棧的內存資源消耗也會很大。優化不好甚至可能造成棧溢出。
目前v8的實現是設定一個阈值，對最下層的10個及以下長度的小數組使用 插入排序。
根據代碼注釋以及 Wikipedia 中的描述，雖然插入排序的平均時間復雜度為 O(n²) 差於快速排序的 O(n㏒n)。但是在運行環境，小數組使用插入排序的效率反而比快速排序會更高，這裡不再展開。
v8代碼示例
var QuickSort = function QuickSort(a, from, to) {
......
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
......
}
......
};
三數取中
正如已知的，快速排序的阿克琉斯之踵在於，最差數組組合情況下會算法退化。
快速排序的算法核心在於選擇一個基准 (pivot)，將經過比較交換的數組按基准分解為兩個數區進行後續遞歸。試想如果對一個已經有序的數組，每次選擇基准元素時總是選擇第一個或者最後一個元素，那麼每次都會有一個數區是空的，遞歸的層數將達到 n，最後導致算法的時間復雜度退化為 O(n²)。因此 pivot 的選擇非常重要。
v8采用的是 三數取中(median-of-three) 的優化：除了頭尾兩個元素再額外選擇一個元素參與基准元素的競爭。
第三個元素的選取策略大致為：
當數組長度小於等於1000時，選擇折半位置的元素作為目標元素。
當數組長度超過1000時，每隔200-215個(非固定，跟著數組長度而變化)左右選擇一個元素來先確定一批候選元素。接著在這批候選元素中進行一次排序，將所得的中位值作為目標元素
最後取三個元素的中位值作為 pivot。
v8代碼示例
var GetThirdIndex = function(a, from, to) {
var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
};
var QuickSort = function QuickSort(a, from, to) {
......
while (true) {
......
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
third_index = from + ((to - from) >> 1);
}
}
......
};
原地排序
在溫習快速排序算法時，我在網上看到了很多用JavaScript實現的例子。
但是發現一大部分的代碼實現如下所示
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
以上代碼的主要問題在於：利用 left 和 right 兩個數區存儲遞歸的子數組，因此它需要 O(n) 的額外存儲空間。這與理論上的平均空間復雜度 O(㏒n) 相比差距較大。
額外的空間開銷，同樣會影響實際運行時的整體速度。這也是快速排序在實際運行時的表現可以超過同等時間復雜度級別的其他排序算法的其中一個原因。所以一般來說，性能較好的快速排序會采用原地 (in-place) 排序的方式。
v8 源代碼中的實現是對原數組進行元素交換。
Firefox為什麼采用歸並排序
它的背後也是有故事的。
Firefox其實在一開始發布的時候對於數組排序的實現並不是采用穩定的排序算法，這塊有據可考。
Firefox(Firebird)最初版本 實現的數組排序算法是 堆排序，這也是一種不穩定的排序算法。因此，後來有人對此提交了一個Bug。
Mozilla開發組內部針對這個問題進行了一系列討論。
從討論的過程我們能夠得出幾點
1.同時期 Mozilla 的競爭對手是 IE6，從上文的統計數據可知IE6是穩定排序的
2.JavaScript之父 Brendan Eich 覺得 Stability is good
3.Firefox在采用 堆排序 之前采用的是 快速排序
基於開發組成員傾向於實現穩定的排序算法為主要前提，Firefox3 將 歸並排序 作為了數組排序的新實現。
解決排序穩定性的差異
以上說了這麼多，主要是為了講述各個浏覽器對於排序實現的差異，以及解釋為什麼存在這些差異的一些比較表層的原因。
但是讀到這裡，讀者可能還是會有疑問：如果我的項目就是需要依賴穩定排序，那該怎麼辦呢？
解決方案
其實解決這個問題的思路比較簡單。
浏覽器出於不同考慮選擇不同排序算法。可能某些偏向於追求極致的性能，某些偏向於提供良好的開發體驗，但是有規律可循。
從目前已知的情況來看，所有主流浏覽器（包括IE6，7，8）對於數組排序算法的實現基本可以枚舉：
1.歸並排序 / Timsort
2.快速排序
所以，我們將快速排序經過定制改造，變成穩定排序的是不是就可以了？
一般來說，針對對象數組使用不穩定排序會影響結果。而其他類型數組本身使用穩定排序或不穩定排序的結果是相等的。因此方案大致如下：
將待排序數組進行預處理，為每個待排序的對象增加自然序屬性，不與對象的其他屬性沖突即可。
自定義排序比較方法compareFn，總是將自然序作為前置判斷相等時的第二判斷維度。
面對歸並排序這類實現時由於算法本身就是穩定的，額外增加的自然序比較並不會改變排序結果，所以方案兼容性比較好。
但是涉及修改待排序數組，而且需要開辟額外空間用於存儲自然序屬性，可想而知 v8 這類引擎應該不會采用類似手段。不過作為開發者自行定制的排序方案是可行的。
方案代碼示例
'use strict';
const INDEX = Symbol('index');
function getComparer(compare) {
return function (left, right) {
let result = compare(left, right);
return result === 0 ? left[INDEX] - right[INDEX] : result;
};
}
function sort(array, compare) {
array = array.map(
(item, index) => {
if (typeof item === 'object') {
item[INDEX] = index;
}
return item;
}
);
return array.sort(getComparer(compare));
}
以上只是一個簡單的滿足穩定排序的算法改造示例。
之所以說簡單，是因為實際生產環境中作為數組輸入的數據結構冗雜，需要根據實際情況判斷是否需要進行更多樣的排序前類型檢測。
標注
1.前端現在已經是一個比較寬泛的概念。本文中的前端主要指的是以浏覽器作為載體，以 JavaScript 作為編程語言的環境
2.本文無意於涉及算法整體，謹以常見的排序算法作為切入點
3.在確認 Firefox 數組排序實現的算法時，搜到了 SpiderMoney 的一篇排序相關的Bug。大致意思是討論過程中有人建議用極端情況下性能更好的 Timsort 算法替換 歸並排序，但是 Mozilla 的工程師表示由於 Timsort 算法存在License授權問題，沒辦法在 Mozilla 的軟件中直接使用算法，等待對方的後續回復
總結
以上就是大家在前端排序中遇到的問題總結和解決方案，這幾年越來越多的項目正在往富客戶端應用方向轉變，前端在項目中的占比變大。隨著未來浏覽器計算能力的進一步提升，它允許進行一些更復雜的計算。伴隨職責的變更，前端的形態也可能會發生一些重大變化。行走江湖，總要有一技傍身。