JavaScript 排序算法匯總
前言
關于排序算法的有關文章已經很多了，然而網絡上用 Javascript 語言來作為示例并詳實介紹的文章貌似還是不太多。這里主要是我來嘗試自己針對網上各式的排序算法進行一份詳實的個人總結，從而溫故知新。
基本概念
算法優劣評價術語
穩定性
- 穩定：如果 a 原本在 b 前面，而 a = b ，排序之后 a 仍然在 b 的前面；
- 不穩定：如果 a 原本在 b 的前面，而 a = b ，排序之后 a 可能會出現在 b 的后面；
排序方式
- 內排序：所有排序操作都在內存中完成，占用常數內存，不占用額外內存。
- 外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行，占用額外內存。
復雜度
- 時間復雜度: 一個算法執行所耗費的時間。
- 空間復雜度: 運行完一個程序所需內存的大小。
排序算法圖片總結
名詞解釋： n : 數據規模 k : 桶的個數
| 排序算法 | 平均時間復雜度 | 最好情況 | 最壞情況 | 空間復雜度 | 排序方式 | 穩定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 內排序 | 穩定 |
| 選擇排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 內排序 | 不穩定 |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 內排序 | 穩定 |
| 希爾排序 | $O(n\log n)$ | $O(n(\log_2^2 n))$ | $O(n(\log_2^2 n))$ | $O(1)$ | 內排序 | 不穩定 |
| 歸并排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | 外排序 | 穩定 |
| 快速排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | 內排序 | 不穩定 |
| 堆排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | 內排序 | 不穩定 |
| 計數排序 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | 外排序 | 穩定 |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | 外排序 | 穩定 |
| 基數排序 | $O(n × k)$ | $O(n × k)$ | $O(n × k)$ | $O(n + k)$ | 外排序 | 穩定 |
從分類上來講：
| 排序算法 | 交換排序 | 冒泡排序 | 快速排序 |
| 選擇排序 | 選擇排序 | 堆排序 | |
| 插入排序 | 插入排序 | 希爾排序 | |
| 歸并排序 | 歸并排序 | ||
| 分布排序 | 計數排序 | 桶排序 | 基數排序 |
算法原理
冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復地走訪要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換時，此時該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
圖解如下:
算法描述與實現
- 具體算法描述如下：
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；
- 針對所有的元素重復以上的步驟，除了最后一個；
- 重復步驟 $1~3$，直到排序完成。
- 代碼實現如下：
const bubbleSort = (arr) => {
let len = arr.length;
for(let i = 0;i < len;i++){
for(let j = 0;j < len - 1 - i;j++){
if(arr[j] > arr[j+1]){
let temp = arr[j+1];
arr[j+1] = arr[j]
arr[j] = temp;
}
}
}
return arr;
}
let arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
</code></pre>
改進冒泡排序： 我們設置一個標志性變量 pos ，用于記錄每趟排序中最后一次進行交換的位置。由于 pos 位置之后的元素均已交換到位，故在進行下一趟排序時只要掃描到 pos 位置即可。 這樣的優化方式可以在最好情況下把復雜度降到 $O(n)$。
const bubbleSort2 = (arr) => {
let i = arr.length - 1;
while(i > 0){
let pos = 0;
for(let j = 0; j < i; j++){
if (arr[j] > arr[j+1]){
pos = j; //記錄交換的位置
let tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
i = pos; //為下一趟排序作準備
}
return arr;
}
另外傳統冒泡排序中每一趟排序操作只能找到一個最大值或最小值，我們可以考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法來一次得到兩個最終值(最大者和最小者)，從而繼續優化使排序趟數幾乎減少一半。
const cooktailSort = (arr) => {
let min = 0;
let max = arr.length - 1;
while(min < max){
for(let j = min;j < max;j++){
if(arr[j] > arr[j+1]){
let tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
-- max;
for(let j = max;j > min;j--){
if(arr[j] < arr[j-1]){
let tmp = arr[j]
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
++ min;
}
return arr;
}
算法分析
冒泡排序對有 $n$ 個元素的項目平均需要 $O(n^2)$ 次比較次數，它可以原地排序，并且是能簡單實現的幾種排序算法之一，但是它對于少數元素之外的數列排序是很沒有效率的。
- 最佳情況： $T(n) = O(n)$
- 最差情況： $T(n) = O(n^2)$
- 平均情況： $T(n) = O(n^2)$
算法原理
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
圖解如下:
算法描述與實現
- 具體算法描述如下：
$n$ 個記錄的直接選擇排序可經過 $n - 1$ 趟直接選擇排序得到有序結果。具體算法描述如下：
- 初始狀態：無序區為 R[1 ... n] ，有序區為空；
- 第 $i$ 趟排序$(i = 1, 2, 3 ... n - 1)$開始時，當前有序區和無序區分別為 $R[1 ... i - 1]$ 和 $R(i ... n)$。該趟排序從當前無序區中選出關鍵字最小的記錄 $R[k]$，將它與無序區的第 1 個記錄 $R$ 交換，使 $R[1 ... i]$ 和 $R[i + 1 ... n]$ 分別變為記錄個數增加 1 個的新有序區和記錄個數減少 1 個的新無序區；
- $n - 1$ 趟結束后，數組有序化。
- 代碼實現如下：
const SelectionSort = (arr) => {
let len = arr.length;
let minIndex, tmp;
console.time('選擇排序耗時');
for (let i = 0;i < len - 1; i++){
minIndex = i;
for(let j = i + 1;j < len;j++){
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
console.timeEnd('選擇排序耗時');
return arr;
}
算法分析
選擇排序的主要優點與數據移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對 $n$ 個元素的表進行排序總共進行至多 $n - 1$ 次交換。在所有的 完全依靠交換 去移動元素的排序方法中，選擇排序屬于非常好的一種。 但原地操作幾乎是選擇排序的唯一優點，當空間復雜度要求較高時，可以考慮選擇排序；實際適用的場合非常罕見。
- 最佳情況： $T(n) = O(n^2)$
- 最差情況： $T(n) = O(n^2)$
- 平均情況： $T(n) = O(n^2)$
算法原理
插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前s掃描，找到相應位置并插入。插入排序在實現上，通常采用 in-place 排序（即只需用到 $O(1)$ 的額外空間的排序），因而在從后向前的掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
圖解如下:
算法描述與實現
- 具體算法描述如下：
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
- 從第一個元素開始，該元素可以認為已經被排序
- 取出下一個元素，在已經排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復步驟 3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟 $2~5$
如果 比較操作 的代價比 交換操作大 的話，可以采用 二分查找法 來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為。
- 代碼實現如下：
const insertionSort = (arr) => {
let len = arr.length;
console.time('插入排序耗時');
for (let i = 1;i < len; i++){
let key = arr[i];
let j = i - 1;
while(j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
console.timeEnd('插入排序耗時');
return arr;
}
改進插入排序：查找插入位置時使用二分查找的方式。
具體思路如下：
- 在插入第 $i$ 個元素時，對前面的 $0 ~ i-1$ 元素進行折半。
- 與前面的 $0 ~ i-1$ 個元素中間的元素進行比較，如果小，則對前半再進行折半，否則對后半進行折半。
- 直到 left > right，再把第 $i$ 個元素前 1 位和目標位置間的所有元素后移，把第 $i$ 個元素放在目標位置上。
- 代碼實現如下：
const binaryInsertionSort = (arr) => {
console.time('二分插入排序耗時：');
for (let i = 1; i < arr.length; i++){
let key = arr[i], left = 0, right = i - 1;
while (left <= right){
let middle = parseInt((left + right) / 2);
if (key < arr[middle]){
right = middle - 1;
}else{
left = middle + 1;
}
}
for (let j = i - 1; j >= left; j--){
arr[j + 1] = arr[j];
}
arr[left] = key;
}
console.timeEnd('二分插入排序耗時：');
return arr;
}
算法分析
- 最佳情況： $T(n) = O(n)$
- 最差情況： $T(n) = O(n^2)$
- 平均情況： $T(n) = O(n^2)$
算法原理
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。它是非穩定排序算法。
希爾排序基于插入排序的以下兩點性質提出了改進方法：
- 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。
- 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。
它與插入排序的不同之處在于，它會優先比較距離較遠的元素。因此希爾排序又叫縮小增量排序。
圖解如下:
算法描述與實現
- 具體算法描述如下：
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述：
- 選擇一個增量序列$t1，t2，…，tk$，其中 $ti > tj(i > j)$，$tk = 1$；
- 按增量序列個數 $k$，對序列進行 $k$ 趟排序；
- 每趟排序，根據對應的增量 $ti$，將待排序列分割成若干長度為 $m$ 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
- 代碼實現如下：
const shellSort = (arr) => {
console.time('希爾排序耗時:');
let len = arr.length,temp,gap = 1;
while(gap < len / 5) { // 動態定義間隔序列步長為 5
gap = gap * 5 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 5)) {
for (let i = gap; i < len; i++) {
temp = arr[i];
let j;
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
console.timeEnd('希爾排序耗時:');
return arr;
}
算法分析
- 最佳情況： $T_(n) = O_(n\log_2 n)$
- 最差情況： $T_(n) = O_(n\log_2 n)$
- 平均情況： $T_(n) = O_(n\log n)$
算法原理
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序是一種穩定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
圖解如下：
算法描述與實現
- 具體算法描述如下：
- 把長度為 n 的輸入序列分成兩個長度為 n/2 的子序列；
- 對這兩個子序列分別采用歸并排序；
- 將兩個排序好的子序列合并成一個最終的排序序列。
- 代碼實現如下：
"use strict"
const mergeSort = (arr) =>{ //采用自上而下的遞歸方法
let len = arr.length;
if(len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
let arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.time('歸并排序耗時');
console.log(mergeSort(arr));
console.timeEnd('歸并排序耗時');
</code></pre>
算法分析
和選擇排序一樣，歸并排序的性能不受輸入數據的影響，但它的表現比選擇排序要好，因為它始終都是 $O_(n\log n)$ 的時間復雜度。但代價是需要額外的內存空間。
- 最佳情況： $T_(n) = O_(n)$
- 最差情況： $T_(n) = O_(n\log n)$
- 平均情況： $T_(n) = O_(n\log n)$
算法原理
通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
算法描述與實現
- 具體算法描述如下：
快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：
- 從數列中挑出一個元素，稱為 “基準”（pivot）；
- 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
- 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
- 代碼實現如下：
'use strict'
const quickSort = (arr) => {
if (arr.length <= 1) { return arr; }
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let 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));
};
let arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.time('快速排序耗時');
console.log(quickSort(arr));
console.timeEnd('快速排序耗時');
算法分析
- 最佳情況： $T_(n) = O_(n\log n)$
- 最差情況： $T_(n) = O_(n^2)$
- 平均情況： $T_(n) = O_(n\log n)$
算法原理
堆排序可以說是一種利用堆的概念來排序的選擇排序。它利用堆這種數據結構所設計。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
算法描述與實現
- 具體算法描述如下：
- 將初始待排序關鍵字序列 $(R1,R2…,Rn)$ 構建成大頂堆，此堆為初始的無序區；
- 將堆頂元素 $R[1]$ 與最后一個元素 $R[n]$ 交換，此時得到新的無序區 $(R1,R2,……,Rn-1)$ 和新的有序區 $(Rn)$ ，且滿足 $R[1,2…,n-1] <= R[n]$；
- 由于交換后新的堆頂 $R[1]$ 可能違反堆的性質，因此需要對當前無序區 $(R1,R2,……,Rn-1)$ 調整為新堆，然后再次將 $R[1]$ 與無序區最后一個元素交換，得到新的無序區 $(R1,R2…,Rn-2)$ 和新的有序區 $(Rn-1,Rn)$。不斷重復此過程直到有序區的元素個數為 n-1，則整個排序過程完成。
- 代碼實現如下：
"use strict"
const heapSort = (array) => {
console.time('堆排序耗時');
//建堆
let heapSize = array.length, temp;
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
heapify(array, i, heapSize);
}
//堆排序
for (let j = heapSize - 1; j >= 1; j--) {
temp = array[0];
array[0] = array[j];
array[j] = temp;
heapify(array, 0, --heapSize);
}
console.timeEnd('堆排序耗時');
return array;
}
/*方法說明：維護堆的性質
@param arr 數組
@param x 數組下標
@param len 堆大小*/
const heapify = (arr, x, len) => {
let l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
heapify(arr, largest, len);
}
}
let arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));
算法分析
- 最佳情況： $T_(n) = O_(n\log n)$
- 最差情況： $T_(n) = O_(n\log n)$
- 平均情況： $T_(n) = O_(n\log n)$
算法原理
計數排序(Counting sort)是一種穩定的排序算法。計數排序使用一個額外的數組 C，其中第 i 個元素是待排序數組 A 中值等于 i 的元素的個數。然后根據數組 C 來將 A 中的元素排到正確的位置。它只能對整數進行排序。
算法描述與實現
- 具體算法描述如下：
- 找出待排序的數組中最大和最小的元素；
- 統計數組中每個值為 i 的元素出現的次數，存入數組 C 的第 i 項；
- 對所有的計數累加（從 C 中的第一個元素開始，每一項和前一項相加）；
- 反向填充目標數組：將每個元素 i 放在新數組的第 $C(i)$ 項，每放一個元素就將 $C(i)$ 減去 1。
- 代碼實現如下：
'use strict'
const countingSort = (array) => {
let len = array.length,
result = [],
C = [],
min,max;
min = max = array[0];
console.time('計數排序耗時');
for (let i = 0; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
}
for (let j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
}
for (let k = len - 1; k >= 0; k--) {
result[C[array[k]] - 1] = array[k];
C[array[k]]--;
}
console.timeEnd('計數排序耗時');
return result;
}
let arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr));
算法分析
計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。
當輸入的元素是 n 個 0 到 k 之間的整數時，它的運行時間是 O(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。由于用來計數的數組 C 的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上 1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。
- 最佳情況： $T_(n) = O_(n+k)$
- 最差情況： $T_(n) = O_(n+k)$
- 平均情況： $T_(n) = O_(n+k)$
算法原理
工作的原理是將數組分到有限數量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）
算法描述與實現
- 具體算法描述如下：
- 設置一個定量的數組當作空桶；
- 遍歷輸入數據，并且把數據一個一個放到對應的桶里去；
- 對每個不是空的桶進行排序；
- 從不是空的桶里把排好序的數據拼接起來。
- 代碼實現如下：
"use strict"
const bucketSort = (array, num) => {
if (array.length <= 1) {
return array;
}
var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0;
num = num || ((num > 1 && regex.test(num)) ? num : 10);
console.time('桶排序耗時');
for (var i = 1; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
}
space = (max - min + 1) / num;
for (var j = 0; j < len; j++) {
var index = Math.floor((array[j] - min) / space);
if (buckets[index]) { // 非空桶，插入排序
var k = buckets[index].length - 1;
while (k >= 0 && buckets[index][k] > array[j]) {
buckets[index][k + 1] = buckets[index][k];
k--;
}
buckets[index][k + 1] = array[j];
} else { //空桶，初始化
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
console.timeEnd('桶排序耗時');
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bucketSort(arr,4));
算法分析
桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。 桶排序最好情況下使用線性時間 $O(n)$，桶排序的時間復雜度，取決與對各個桶之間數據進行排序的時間復雜度，因為其它部分的時間復雜度都為 $O(n)$。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的空間消耗就會增大。
- 最佳情況： $T_(n) = O_(n+k)$
- 最差情況： $T_(n) = O_(n+k)$
- 平均情況： $T_(n) = O_(n^2)$
算法原理
基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分別排序，分別收集，所以是穩定的。
算法描述與實現
- 具體算法描述如下：
- 取得數組中的最大數，并取得位數；
- arr 為原始數組，從最低位開始取每個位組成 radix 數組；
- 對 radix 進行計數排序（利用計數排序適用于小范圍數的特點）；
- 代碼實現如下：
'use strict'
const radixSort = (arr, maxDigit) => {
var mod = 10;
var dev = 1;
var counter = [];
console.time('基數排序耗時');
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]== null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
console.timeEnd('基數排序耗時');
return arr;
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr,2));
算法分析
基數排序有兩種方法：
MSD 從高位開始進行排序 LSD 從低位開始進行排序
- 最佳情況： $T_(n) = O_(n^2)$
- 最差情況： $T_(n) = O_(n^2)$
- 平均情況： $T_(n) = O_(n^2)$
基數排序 vs 計數排序 vs 桶排序
這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶 計數排序：每個桶只存儲單一鍵值 桶排序：每個桶存儲一定范圍的數值
JS 原生函數中的排序
說到前端排序，自然首先會想到 JavaScript 的原生接口 Array.prototype.sort
這個接口自 ECMAScript 1st Edition 起就被設計存在。而在規范中關于它的描述是這樣的：
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 的實現
Chrome 的 JavaScript 引擎是 v8。由于它是開源的，所以可以直接看 源代碼 。
整個 array.js 都是用 JavaScript 語言實現的。排序方法部分很明顯比通常看到的快速排序要復雜得多，但顯然核心算法還是快速排序的思想。算法復雜的原因在于 v8 出于性能考慮進行了很多優化。(后續會展開說)
Firefox中的實現
暫時無法確定 Firefox 的 JavaScript 引擎即將使用的數組排序算法會是什么。
按照現有的信息，SpiderMoney 內部實現了歸并排序。（這里不多做敘述）
Microsoft Edge中的實現
Microsoft Edge 的 JavaScript 引擎 Chakra 的核心部分代碼已經于 2016 年初在 Github 開源。
Chakra 的數組排序算法也主要是以快速排序為主。并針對其他具體特殊情況進行具體優化。
排序的差異
如上所述，快速排序是一種不穩定的排序算法，而歸并排序是一種穩定的排序算法。由于不同引擎在算法選擇上可能存在差異，導致前端如果依賴 Array.prototype.sort 接口實現的 JavaScript 代碼，在瀏覽器中實際執行的排序效果是不一致的。
而排序穩定性的差異其實也只是在特定的場景才會體現出問題；在很多情況下，不穩定的排序也并不會造成什么影響。所以假如實際項目開發中，對于數組的排序沒有穩定性的需求，那么看到這里就可以了。
但是若項目要求排序必須是穩定的，那么這些差異的存在將無法滿足需求。我們需要為此進行一些額外的工作。
舉個例子：
某市的機動車牌照拍賣系統，最終中標的規則為：
1. 按價格進行倒排序；
- 相同價格則按照競標順位（即價格提交時間）進行正排序。
</code></pre>
排序若是在前端進行，那么采用快速排序的瀏覽器中顯示的中標者很可能是不符合預期的。
此外例如： MySQL 5.6 的 limit M,N 語句實現 等情況都是不穩定排序的特征。
背后的原因
Chrome為什么采用快速排序
其實這個情況從一開始便存在。
Chrome測試版于 2008年9月2日發布 (這里附上當時隨版本發布的漫畫，還是很有意思的 Google on Google Chrome - comic book )，然而發布后不久，就有開發者向 Chromium 開發組提交 #90 Bug V8 doesn't stable sort 反饋 v8 的數組排序實現不是穩定排序的。
這個 Bug ISSUE 討論的時間跨度很大。時至今日，仍然有開發者對 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.
這也正如本文前段所引用的已定稿 ECMAScript 2015 規范中的描述一樣。
時代特點
IMHO，Chrome 發布之初即被報告出這個問題可能是有其特殊的時代特點。
上文已經說到，Chrome 第一版是 2008 年 9 月發布的。根據 statcounter 的統計數據，那個時期市場占有率最高的兩款瀏覽器分別是 IE(那時候只有 IE6 和 IE7) 和 Firefox，市場占有率分別達到了 67.16% 和 25.77%。也就是說，兩個瀏覽器加起來的市場占有率超過了 90%。
而根據另一份 瀏覽器排序算法穩定性的統計 數據顯示，這兩款超過了 90% 市場占有率的瀏覽器都采用了穩定的數組排序。所以 Chrome 發布之初被開發者質疑也是合情合理的。
我們從 ISSUE 討論的過程中，可以大概理解開發組成員對于引擎實現采用快速排序的一些考量。他們認為引擎必須遵守 ECMAScript 規范。由于規范不要求穩定排序的描述，故他們認為 v8 的實現也是完全符合規范的。
性能考慮
另外，他們認為 v8 設計的一個重要考量在于引擎的性能。
快速排序相比較于 歸并排序 ，在整體性能上表現更好：
- 更高的計算效率。快速排序在實際計算機執行環境中比同等時間復雜度的其他排序算法更快（不命中最差組合的情況下）
- 更低的空間成本。前者僅有 $O(logn)$ 的空間復雜度，相比較后者 $O(n)$ 的空間復雜度在運行時的內存消耗更少
v8 在數組排序算法中的性能優化
既然說 v8 非常看中引擎的性能，那么在數組排序中它做了哪些事呢？
通過閱讀源代碼，還是粗淺地學習了一些皮毛。
- 混合插入排序 快速排序是分治的思想，將大數組分解，逐層往下遞歸。但是若遞歸深度太大，為了維持遞歸，調用棧的內存資源消耗也會很大。優化不好甚至可能造成棧溢出。
目前 v8 的實現是設定一個閾值，對最下層的 10 個及以下長度的小數組使用插入排序。
根據代碼注釋以及 Wikipedia 中的描述，雖然插入排序的平均時間復雜度為 $O(n^2)$ 差于快速排序的 $O(nlogn)$。但是在運行環境，小數組使用插入排序的效率反而比快速排序會更高，這里不再展開。
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;
}
......
}
......
};
</code></pre>
- 三數取中
正如已知的，快速排序的阿克琉斯之踵在于，最差數組組合情況下會算法退化。
快速排序的算法核心在于選擇一個基準( pivot )，將經過比較交換的數組按基準分解為兩個數區進行后續遞歸。試想如果對一個已經有序的數組，每次選擇基準元素時總是選擇第一個或者最后一個元素，那么每次都會有一個數區是空的，遞歸的層數將達到 n ，最后導致算法的時間復雜度退化為 $O(n^2)$。因此 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);
}
}
......
};
</code></pre>
- 原地排序
目前，大多數快速排序算法中大部分的代碼實現如下所示：
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(logn)$ 相比差距較大。
額外的空間開銷，同樣會影響實際運行時的整體速度。（這也是快速排序在實際運行時的表現可以超過同等時間復雜度級別的其他排序算法的其中一個原因。）所以一般來說，性能較好的快速排序會采用原地(in-place)排序的方式。
v8 源代碼中的實現是對原數組進行元素交換。
Firefox 為什么采用歸并排序
它的背后也是有故事的。
Firefox 其實在一開始發布的時候對于數組排序的實現并不是采用穩定的排序算法，這塊有據可考。
Firefox(Firebird) 最初版本實現的數組排序算法是堆排序，這也是一種不穩定的排序算法。因此，后來有人對此提交了一個 Bug 。
Mozilla開發組內部針對這個問題進行了一系列 討論 。
從討論的過程我們能夠得出幾點
- 同時期 Mozilla 的競爭對手是 IE6 ，從上文的統計數據可知 IE6 是穩定排序的
- JavaScript 之父 Brendan Eich 覺得 Stability is good
- Firefox在采用 堆排序 之前采用的是 快速排序
基于開發組成員傾向于實現穩定的排序算法為主要前提， Firefox3 將 歸并排序 作為了數組排序的新實現。
解決排序穩定性的差異
以上說了這么多，主要是為了講述各個瀏覽器對于排序實現的差異，以及解釋為什么存在這些差異的一些比較表層的原因。
但是讀到這里，讀者可能還是會有疑問：如果我的項目就是需要依賴穩定排序，那該怎么辦呢？
解決方案
其實解決這個問題的思路比較簡單。
瀏覽器出于不同考慮選擇不同排序算法。可能某些偏向于追求極致的性能，某些偏向于提供良好的開發體驗，但是有規律可循。
從目前已知的情況來看，所有主流瀏覽器（包括IE6，7，8）對于數組排序算法的實現基本可以枚舉：
- 歸并排序 / Timsort
- 快速排序
所以，我們將快速排序經過定制改造，變成穩定排序的是不是就可以了？
一般來說，針對對象數組使用不穩定排序會影響結果。而其他類型數組本身使用穩定排序或不穩定排序的結果是相等的。因此方案大致如下：
- 將待排序數組進行預處理，為每個待排序的對象增加自然序屬性，不與對象的其他屬性沖突即可。
- 自定義排序比較方法 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));
}
</code></pre>
以上只是一個簡單的滿足穩定排序的算法改造示例。
之所以說簡單，是因為實際生產環境中作為數組輸入的數據結構冗雜，需要根據實際情況判斷是否需要進行更多樣的排序前類型檢測。
選擇排序算法的參考方法：
影響排序的因素有很多，平均時間復雜度低的算法并不一定就是最優的。相反，有時平均時間復雜度高的算法可能更適合某些特殊情況。同時，選擇算法時還得考慮它的可讀性，以利于軟件的維護。一般而言，需要考慮的因素有以下四點：
-
待排序的記錄數目 n 的大小；
-
記錄本身數據量的大小，也就是記錄中除關鍵字外的其他信息量的大小；
-
關鍵字的結構及其分布情況；
-
對排序穩定性的要求。
設待排序元素的個數為 n。選擇的大致方案如下：
- 當 n 較大，則應采用時間復雜度為 $O(nlogn)$ 的排序方法：快速排序、堆排序或歸并排序。
- 快速排序：是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
- 堆排序：如果內存空間允許且要求穩定性的，
- 歸并排序：它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并，在效率上將有所提高。
-
當 n 較大，內存空間允許，且要求穩定性則選擇歸并排序
-
當 n 較小，可采用直接插入或直接選擇排序。
直接插入排序：當元素分布有序，直接插入排序將大大減少比較次數和移動記錄的次數。
直接選擇排序：元素分布有序，如果不要求穩定性，選擇直接選擇排序
-
一般不使用或不直接使用傳統的冒泡排序。
-
基數排序： 它是一種穩定的排序算法，但有一定的局限性，最好滿足：
- 關鍵字可分解。
- 記錄的關鍵字位數較少，如果密集更好
- 如果是數字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。
參考資料 & 拓展閱讀
Array.prototype.sort 隨機排列數組的錯誤實現
來自：http://www.qcyoung.com/2016/12/18/JavaScript 排序算法匯總/