C++快速排序

「快速排序 quick sort」是一種基于分治策略的排序算法，運行高效，應(yīng)用廣泛。

快速排序的核心操作是“哨兵劃分”，其目標(biāo)是：選擇數(shù)組中的某個元素作為“基準(zhǔn)數(shù)”，將所有小于基準(zhǔn)數(shù)的元素移到其左側(cè)，而大于基準(zhǔn)數(shù)的元素移到其右側(cè)。具體來說，哨兵劃分的流程如圖 11-8 所示。

1. 選取數(shù)組最左端元素作為基準(zhǔn)數(shù)，初始化兩個指針 i 和 j 分別指向數(shù)組的兩端。
2. 設(shè)置一個循環(huán)，在每輪中使用 i（j）分別尋找第一個比基準(zhǔn)數(shù)大（?。┑脑?，然后交換這兩個元素。
3. 循環(huán)執(zhí)行步驟 2. ，直到 i 和 j 相遇時停止，最后將基準(zhǔn)數(shù)交換至兩個子數(shù)組的分界線。

圖 11-8   哨兵劃分步驟

哨兵劃分完成后，原數(shù)組被劃分成三部分：左子數(shù)組、基準(zhǔn)數(shù)、右子數(shù)組，且滿足“左子數(shù)組任意元素 $\le$ 基準(zhǔn)數(shù) $\le$ 右子數(shù)組任意元素”。因此，我們接下來只需對這兩個子數(shù)組進行排序。

快速排序的分治策略

哨兵劃分的實質(zhì)是將一個較長數(shù)組的排序問題簡化為兩個較短數(shù)組的排序問題。

quick_sort.cpp

/* 元素交換 */
void swap(vector<int> &nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵劃分 */
int partition(vector<int> &nums, int left, int right) {
    // 以 nums[left] 作為基準(zhǔn)數(shù)
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--; // 從右向左找首個小于基準(zhǔn)數(shù)的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 從左向右找首個大于基準(zhǔn)數(shù)的元素
        swap(nums, i, j); // 交換這兩個元素
    }
    swap(nums, i, left); // 將基準(zhǔn)數(shù)交換至兩子數(shù)組的分界線
    return i;            // 返回基準(zhǔn)數(shù)的索引
}

算法流程

快速排序的整體流程如圖 11-9 所示。

1. 首先，對原數(shù)組執(zhí)行一次“哨兵劃分”，得到未排序的左子數(shù)組和右子數(shù)組。
2. 然后，對左子數(shù)組和右子數(shù)組分別遞歸執(zhí)行“哨兵劃分”。
3. 持續(xù)遞歸，直至子數(shù)組長度為 1 時終止，從而完成整個數(shù)組的排序。

quick_sort.cpp

/* 快速排序 */
void quickSort(vector<int> &nums, int left, int right) {
    // 子數(shù)組長度為 1 時終止遞歸
    if (left >= right)
        return;
    // 哨兵劃分
    int pivot = partition(nums, left, right);
    // 遞歸左子數(shù)組、右子數(shù)組
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

算法特性

• 時間復(fù)雜度 O(nlog?n)、自適應(yīng)排序：在平均情況下，哨兵劃分的遞歸層數(shù)為 log?n ，每層中的總循環(huán)數(shù)為 n ，總體使用 O(nlog?n) 時間。在最差情況下，每輪哨兵劃分操作都將長度為 n 的數(shù)組劃分為長度為 0 和 n?1 的兩個子數(shù)組，此時遞歸層數(shù)達到 n 層，每層中的循環(huán)數(shù)為 n ，總體使用 O(n2) 時間。
• 空間復(fù)雜度 O(n)、原地排序：在輸入數(shù)組完全倒序的情況下，達到最差遞歸深度 n ，使用 O(n) 棧幀空間。排序操作是在原數(shù)組上進行的，未借助額外數(shù)組。
• 非穩(wěn)定排序：在哨兵劃分的最后一步，基準(zhǔn)數(shù)可能會被交換至相等元素的右側(cè)。

快排為什么快？

從名稱上就能看出，快速排序在效率方面應(yīng)該具有一定的優(yōu)勢。盡管快速排序的平均時間復(fù)雜度與“歸并排序”和“堆排序”相同，但通?？焖倥判虻男矢撸饕幸韵略?。

• 出現(xiàn)最差情況的概率很低：雖然快速排序的最差時間復(fù)雜度為 O(n2) ，沒有歸并排序穩(wěn)定，但在絕大多數(shù)情況下，快速排序能在 O(nlog?n) 的時間復(fù)雜度下運行。
• 緩存使用效率高：在執(zhí)行哨兵劃分操作時，系統(tǒng)可將整個子數(shù)組加載到緩存，因此訪問元素的效率較高。而像“堆排序”這類算法需要跳躍式訪問元素，從而缺乏這一特性。
• 復(fù)雜度的常數(shù)系數(shù)低：在上述三種算法中，快速排序的比較、賦值、交換等操作的總數(shù)量最少。這與“插入排序”比“冒泡排序”更快的原因類似。

基準(zhǔn)數(shù)優(yōu)化

快速排序在某些輸入下的時間效率可能降低。舉一個極端例子，假設(shè)輸入數(shù)組是完全倒序的，由于我們選擇最左端元素作為基準(zhǔn)數(shù)，那么在哨兵劃分完成后，基準(zhǔn)數(shù)被交換至數(shù)組最右端，導(dǎo)致左子數(shù)組長度為 n?1、右子數(shù)組長度為 0 。如此遞歸下去，每輪哨兵劃分后的右子數(shù)組長度都為 0 ，分治策略失效，快速排序退化為“冒泡排序”。

為了盡量避免這種情況發(fā)生，我們可以優(yōu)化哨兵劃分中的基準(zhǔn)數(shù)的選取策略。例如，我們可以隨機選取一個元素作為基準(zhǔn)數(shù)。然而，如果運氣不佳，每次都選到不理想的基準(zhǔn)數(shù)，效率仍然不盡如人意。

需要注意的是，編程語言通常生成的是“偽隨機數(shù)”。如果我們針對偽隨機數(shù)序列構(gòu)建一個特定的測試樣例，那么快速排序的效率仍然可能劣化。

為了進一步改進，我們可以在數(shù)組中選取三個候選元素（通常為數(shù)組的首、尾、中點元素），并將這三個候選元素的中位數(shù)作為基準(zhǔn)數(shù)。這樣一來，基準(zhǔn)數(shù)“既不太小也不太大”的概率將大幅提升。當(dāng)然，我們還可以選取更多候選元素，以進一步提高算法的穩(wěn)健性。采用這種方法后，時間復(fù)雜度劣化至 O(n2) 的概率大大降低。

quick_sort.cpp

/* 選取三個元素的中位數(shù) */
int medianThree(vector<int> &nums, int left, int mid, int right) {
    // 此處使用異或運算來簡化代碼
    // 異或規(guī)則為 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
    if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
        return left;
    else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
        return mid;
    else
        return right;
}

/* 哨兵劃分（三數(shù)取中值） */
int partition(vector<int> &nums, int left, int right) {
    // 選取三個候選元素的中位數(shù)
    int med = medianThree(nums, left, (left + right) / 2, right);
    // 將中位數(shù)交換至數(shù)組最左端
    swap(nums, left, med);
    // 以 nums[left] 作為基準(zhǔn)數(shù)
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--; // 從右向左找首個小于基準(zhǔn)數(shù)的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 從左向右找首個大于基準(zhǔn)數(shù)的元素
        swap(nums, i, j); // 交換這兩個元素
    }
    swap(nums, i, left); // 將基準(zhǔn)數(shù)交換至兩子數(shù)組的分界線
    return i;            // 返回基準(zhǔn)數(shù)的索引
}

尾遞歸優(yōu)化

在某些輸入下，快速排序可能占用空間較多。以完全倒序的輸入數(shù)組為例，由于每輪哨兵劃分后右子數(shù)組長度為 0 ，遞歸樹的高度會達到 n?1 ，此時需要占用 O(n) 大小的棧幀空間。

為了防止棧幀空間的累積，我們可以在每輪哨兵排序完成后，比較兩個子數(shù)組的長度，僅對較短的子數(shù)組進行遞歸。由于較短子數(shù)組的長度不會超過 n/2 ，因此這種方法能確保遞歸深度不超過 log?n ，從而將最差空間復(fù)雜度優(yōu)化至 O(log?n) 。

quick_sort.cpp

/* 快速排序（尾遞歸優(yōu)化） */
void quickSort(vector<int> &nums, int left, int right) {
    // 子數(shù)組長度為 1 時終止
    while (left < right) {
        // 哨兵劃分操作
        int pivot = partition(nums, left, right);
        // 對兩個子數(shù)組中較短的那個執(zhí)行快排
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // 遞歸排序左子數(shù)組
            left = pivot + 1;                 // 剩余未排序區(qū)間為 [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // 遞歸排序右子數(shù)組
            right = pivot - 1;                 // 剩余未排序區(qū)間為 [left, pivot - 1]
        }
    }
}