JavaScript 中的計算機科學：快速排序

大多數關於排序算法的討論都傾向於討論快速排序，因為它的速度很快。正式的計算機科學課程也傾向於涵蓋快速排序 ¹ 最後是因為它的平均複雜度為 O(n log n) 並且相對於其他效率較低的排序算法（例如大數據集的冒泡排序和插入排序）具有相對性能改進。與其他排序算法不同的是，快速排序有許多不同的實現方式，這會導致不同的性能特徵以及排序是否穩定（等價項保持與它們自然發生的相同順序）。

快速排序是一種歸併排序風格的分而治之的算法。基本思想是在數組中找到一個“樞軸”項目來比較所有其他項目，然後移動項目，使得樞軸之前的所有項目都小於樞軸值，並且樞軸之後的所有項目都大於樞軸值樞軸值。之後，遞歸地對樞軸前後的項目執行相同的操作。有許多不同的算法可以實現快速排序，本文僅探討其中一種。

算法中有兩個基本操作，交換項目和分區數組的一部分。對數組進行分區的基本步驟是：

1. 在數組中找到一個“樞軸”項。該項目是單輪比較的依據。
2. 在數組的第一項處開始一個指針（左指針）。
3. 在數組的最後一項處開始一個指針（右指針）。
4. 當數組中左指針的值小於基準值時，將左指針向右移動（加 1）。繼續，直到左指針的值大於或等於樞軸值。
5. 當數組中右指針的值大於樞軸值時，將右指針向左移動（減 1）。繼續直到右指針處的值小於或等於樞軸值。
6. 如果左指針小於或等於右指針，則交換數組中這些位置的值。
7. 左指針右移一位，右指針左移一位。
8. 如果左指針和右指針不相交，則執行步驟 1。

與許多算法一樣，通過查看示例更容易理解分區。假設你有以下數組：

var items = [4, 2, 6, 5, 3, 9];

有許多方法可以計算樞軸值。一些算法選擇第一個項目作為樞軸。這不是最好的選擇，因為它在已經排序的數組上給出了最差的性能。最好在數組中間選擇一個樞軸，因此將 5 視為樞軸值（數組長度除以 2）。接下來，在位置 5（數組中的最後一項）的右指針中的位置 0 處開始左指針。由於 4 小於 5，將左指針移動到位置 1。由於 2 小於 5，將左指針移動到位置 2。現在 6 不小於 5，所以左指針停止移動，右指針值為與樞軸相比。由於 9 大於 5，所以右指針移動到位置 4。值 3 不大於 5，所以右指針停止。由於左指針在位置 2，而右指針在位置 4，所以兩者沒有相遇，應該交換值 6 和 3。

接下來，左指針加一，右指針減一。這導致兩個指針都位於樞軸值 (5)。這表明操作已完成。現在數組中樞軸左側的所有項目都小於樞軸，樞軸右側的所有項目都大於樞軸。請記住，這並不意味著數組現在已排序，只是數組有兩個部分：所有值都小於樞軸的部分和所有值都大於樞軸的部分。見下圖。

分區函數的實現依賴於 swap() 函數，下面是它的代碼：

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

分區函數本身非常簡單，幾乎完全遵循算法：

function partition(items, left, right) {

    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;


    while (i <= j) {

        while (items[i] < pivot) {
            i++;
        }

        while (items[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }

    return i;
}

此函數接受三個參數：items ，這是要排序的值數組，left ，這是左指針開始的索引，以及 right ，這是開始右指針的索引。樞軸值是通過將 left 相加來確定的 和 right 值，然後除以 2。由於該值可能是浮點數，因此有必要進行一些舍入。在這種情況下，我選擇使用 floor 函數，但您也可以使用稍有不同邏輯的 ceiling 函數或 round 函數。 i 變量是左指針和 j 變量是右指針。

整個算法只是一個循環的循環。外部循環確定數組範圍內的所有項目何時都已處理完畢。兩個內部循環控制左右指針的移動。當兩個內部循環都完成時，比較指針以確定是否需要交換。交換之後，兩個指針都會移動，以便外循環在正確的位置繼續。該函數返回左指針的值，因為它用於確定下次從哪裡開始分區。請記住，分區是在原地進行的，沒有創建任何額外的數組。

快速排序算法基本上是通過對整個數組進行分區，然後遞歸地對數組的左右部分進行分區，直到整個數組都被排序。數組的左右部分由每次分區操作後返回的索引確定。該索引有效地成為數組左右部分之間的邊界。在前面的示例中，數組變為 [4, 2, 3, 5, 6, 9] 在一個分區之後，返回的索引是 4（左指針的最後一個點）。之後，對整個數組的左側（第 0 到第 3 項）進行分區，如下圖。

此遍後，數組變為 [3, 2, 4, 5, 6, 9] 並且返回的索引為 1。心律如此繼續，直到數組的所有左側都被排序。然後在陣列的右側進行相同的過程。快速排序的基本對數就變得非常簡單了：

function quickSort(items, left, right) {

    var index;

    if (items.length > 1) {

        index = partition(items, left, right);

        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }

        if (index < right) {
            quickSort(items, index, right);
        }

    }

    return items;
}


// first call
var result = quickSort(items, 0, items.length - 1);

quicksort() 函數接受三個參數，要排序的數組，左指針應該開始的索引，以及右指針應該開始的索引。為了優化性能，如果數組有零個或一個元素，則不會對其進行排序。如果數組中有兩個或更多項，則對其進行分區。如果 left 小於返回的index 減 1 則左側仍有待排序的項目和 quickSort() 在這些項目上遞歸調用。同樣，如果 index 小於 right 指針那麼右邊還有項目要排序。完成所有這些後，將數組作為結果返回。

為了讓這個函數更人性化一點，你可以自動填寫 left 的默認值 和 right 如未提供，如：

function quickSort(items, left, right) {

    var index;

    if (items.length > 1) {

        left = typeof left != "number" ? 0 : left;
        right = typeof right != "number" ? items.length - 1 : right;

        index = partition(items, left, right);

        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }

        if (index < right) {
            quickSort(items, index, right);
        }

    }

    return items;
}

// first call
var result = quickSort(items);

在這個版本的函數中，不需要為 left 傳入初始值 和 right ，因為如果沒有傳入，這些會自動填充。這使得函數比純實現更加用戶友好。

快速排序通常被認為是高效和快速的，因此被 V8 用作 Array.prototype.sort() 的實現 在超過 23 個項目的數組上。對於少於 23 個項目，V8 使用插入排序 ² .合併排序是快速排序的競爭對手，因為它也高效且快速，但具有穩定的額外好處。這就是 Mozilla 和 Safari 使用它來實現 Array.prototype.sort() 的原因 .

更新（2012 年 11 月 30 日）： 修復了代碼中的遞歸錯誤，並添加了關於算法的更多解釋。

參考

1. 快速排序（維基百科）
2. V8 數組源代碼（谷歌代碼）