C++快速排序

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

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

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

圖 11-8   哨兵劃分步驟

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

快速排序的分治策略

哨兵劃分的實(shí)質(zhì)是將一個(gè)較長(zhǎng)數(shù)組的排序問(wèn)題簡(jiǎn)化為兩個(gè)較短數(shù)組的排序問(wèn)題。

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--; // 從右向左找首個(gè)小于基準(zhǔn)數(shù)的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 從左向右找首個(gè)大于基準(zhǔn)數(shù)的元素
        swap(nums, i, j); // 交換這兩個(gè)元素
    }
    swap(nums, i, left); // 將基準(zhǔn)數(shù)交換至兩子數(shù)組的分界線(xiàn)
    return i;            // 返回基準(zhǔn)數(shù)的索引
}

算法流程

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

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

quick_sort.cpp

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

算法特性

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

快排為什么快？

從名稱(chēng)上就能看出，快速排序在效率方面應(yīng)該具有一定的優(yōu)勢(shì)。盡管快速排序的平均時(shí)間復(fù)雜度與“歸并排序”和“堆排序”相同，但通?？焖倥判虻男矢?，主要有以下原因。

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

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

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

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

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

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

quick_sort.cpp

/* 選取三個(gè)元素的中位數(shù) */
int medianThree(vector<int> &nums, int left, int mid, int right) {
    // 此處使用異或運(yùn)算來(lái)簡(jiǎn)化代碼
    // 異或規(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) {
    // 選取三個(gè)候選元素的中位數(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--; // 從右向左找首個(gè)小于基準(zhǔn)數(shù)的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 從左向右找首個(gè)大于基準(zhǔn)數(shù)的元素
        swap(nums, i, j); // 交換這兩個(gè)元素
    }
    swap(nums, i, left); // 將基準(zhǔn)數(shù)交換至兩子數(shù)組的分界線(xiàn)
    return i;            // 返回基準(zhǔn)數(shù)的索引
}

尾遞歸優(yōu)化

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

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

quick_sort.cpp

/* 快速排序（尾遞歸優(yōu)化） */
void quickSort(vector<int> &nums, int left, int right) {
    // 子數(shù)組長(zhǎng)度為 1 時(shí)終止
    while (left < right) {
        // 哨兵劃分操作
        int pivot = partition(nums, left, right);
        // 對(duì)兩個(gè)子數(shù)組中較短的那個(gè)執(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]
        }
    }
}