貌似前端圈一直以來流傳著一種誤解：前端用不到算法知識。長久以來，大家或許都曾受這種說法的影響。直到前陣子遇到一個產品需求，回過頭來看，發現事實並非如此。
前端排序
前端排序的場景
前端將排序條件作為請求參數傳遞給後端，後端將排序結果作為請求響應返回前端，這是一種常見設計。但是對於有些產品則不是那麼適用。
試想一個場景：你在使用美食類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(nn)。但是在運行環境，小數組使用插入排序的效率反而比快速排序會更高，這裡不再展開。
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 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 的軟件中直接使用算法，等待對方的後續回复
總結
以上就是大家在前端排序中遇到的問題總結和解決方案，這幾年越來越多的項目正在往富客戶端應用方向轉變，前端在項目中的佔比變大。隨著未來瀏覽器計算能力的進一步提升，它允許進行一些更複雜的計算。伴隨職責的變更，前端的形態也可能會發生一些重大變化。行走江湖，總要有一技傍身。