一 快速排序

快速排序是一種高效且應(yīng)用廣泛的排序算法，它巧妙地運(yùn)用了“分而治之”的策略。下面這張表格能幫你快速把握它的核心特征，之后我們會(huì)深入探討其工作原理和實(shí)現(xiàn)細(xì)節(jié)。

1.1 快速排序特性總結(jié)

1.2 算法工作原理

快速排序的運(yùn)作過程可以清晰地分為“分區(qū)”和“遞歸”兩大階段。下圖以數(shù)組 [6, 2, 7, 3, 8, 9]為例，展示了其核心的分區(qū)操作以及后續(xù)的遞歸過程：

1.2.1 選擇基準(zhǔn)值??

從待排序序列中選取一個(gè)元素作為“基準(zhǔn)”（pivot）。選擇策略多樣，如第一個(gè)元素、最后一個(gè)元素、中間元素或隨機(jī)元素等。上圖示例中選擇了第一個(gè)元素 6作為基準(zhǔn)。
??

1.2.2 分區(qū)操作??

這是快速排序的核心步驟，目標(biāo)是重新排列數(shù)組，使得所有比基準(zhǔn)值小的元素都放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素都放在基準(zhǔn)后面。操作完成后，基準(zhǔn)值就處于其最終的正確位置上。具體過程通常使用雙指針（如上圖中的 i和 j）從數(shù)組兩端向中間掃描，交換不符合條件的元素，直到指針相遇。

1.2.3 遞歸排序

經(jīng)過一趟分區(qū)操作后，基準(zhǔn)值已經(jīng)就位，數(shù)組被分成兩個(gè)子數(shù)組：左子數(shù)組（所有元素小于基準(zhǔn)值）和右子數(shù)組（所有元素大于基準(zhǔn)值）。然后，遞歸地對(duì)左子數(shù)組和右子數(shù)組重復(fù)上述過程，直到子數(shù)組的長(zhǎng)度為1或0（自然有序），此時(shí)整個(gè)數(shù)組便有序了。

1.3 復(fù)雜度分析

1.3.1 時(shí)間復(fù)雜度??：

• 最好情況 O(n log n)??：每次劃分都能將數(shù)組均勻分成兩部分。
• ??最壞情況 O(n2)??：每次劃分產(chǎn)生的兩個(gè)子數(shù)組大小極度不平衡，例如一個(gè)包含 n-1 個(gè)元素，另一個(gè)為空。這在數(shù)組已有序且始終選擇第一個(gè)或最后一個(gè)元素作為基準(zhǔn)時(shí)會(huì)發(fā)生。
• 平均情況 O(n log n)??：對(duì)于隨機(jī)排列的數(shù)組，快速排序的平均性能很好。
• 通過隨機(jī)選擇基準(zhǔn)或“三數(shù)取中”等優(yōu)化方法，可以大幅降低最壞情況出現(xiàn)的概率

1.3.2 空間復(fù)雜度??：主要是遞歸調(diào)用棧的空間。

• ?最好情況 O(log n)??：對(duì)應(yīng)遞歸樹的深度。
• 最壞情況 O(n)??：對(duì)應(yīng)退化的遞歸樹（如數(shù)組已有序）。

1.3.3 穩(wěn)定性??：

快速排序是??不穩(wěn)定??的。在分區(qū)過程中，由于涉及遠(yuǎn)距離的元素交換，可能導(dǎo)致相等元素的相對(duì)順序發(fā)生變化.

1.4 使用場(chǎng)景

• 大規(guī)模數(shù)據(jù)排序??：當(dāng)平均時(shí)間復(fù)雜度為 O(n log n) 時(shí)，快速排序通常是處理大量隨機(jī)數(shù)據(jù)的最優(yōu)選擇之一，性能優(yōu)異。
• ??對(duì)緩存友好??：由于快速排序是原地排序（主要操作在原始數(shù)組上進(jìn)行），其內(nèi)存訪問模式通常具有良好的局部性，能有效利用CPU緩存。
• ??通用排序需求??：是許多編程語言標(biāo)準(zhǔn)庫(kù)（如C的qsort，C++的std::sort）的默認(rèn)或備選實(shí)現(xiàn)算法。
• 注意事項(xiàng)??：若數(shù)據(jù)量很小或基本有序，且未做優(yōu)化，性能可能不如簡(jiǎn)單排序（如插入排序）。在要求穩(wěn)定性的場(chǎng)景下需謹(jǐn)慎使用。

1.5 代碼實(shí)現(xiàn)

以下是快速排序的一個(gè)典型C語言實(shí)現(xiàn)，采用了“挖坑填數(shù)”的分區(qū)方法，并選擇第一個(gè)元素作為基準(zhǔn)。

1.5.1 c 語言實(shí)現(xiàn)

#include <stdio.h>

// 分區(qū)操作函數(shù)，返回基準(zhǔn)值的最終位置
int Partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 選擇第一個(gè)元素為基準(zhǔn)值
    while (low < high) {
        // 從右向左找第一個(gè)小于pivot的元素
        while (low < high && arr[high] >= pivot) {
            --high;
        }
        arr[low] = arr[high]; // 將小于pivot的元素移到左邊low的位置
        // 從左向右找第一個(gè)大于pivot的元素
        while (low < high && arr[low] <= pivot) {
            ++low;
        }
        arr[high] = arr[low]; // 將大于pivot的元素移到右邊high的位置
    }
    arr[low] = pivot; // 基準(zhǔn)值歸位
    return low;       // 返回基準(zhǔn)值的位置
}

// 快速排序遞歸函數(shù)
void QuickSort(int arr[], int low, int high) {
    if (low < high) { // 遞歸終止條件：子數(shù)組長(zhǎng)度為1或0
        int pivotPos = Partition(arr, low, high); // 獲取基準(zhǔn)值位置
        QuickSort(arr, low, pivotPos - 1);  // 遞歸排序左子數(shù)組
        QuickSort(arr, pivotPos + 1, high); // 遞歸排序右子數(shù)組
    }
}

// 打印數(shù)組函數(shù)
void PrintArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函數(shù)測(cè)試
int main() {
    int arr[] = {6, 2, 7, 3, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前的數(shù)組: \n");
    PrintArray(arr, n);
    
    QuickSort(arr, 0, n - 1);
    
    printf("排序后的數(shù)組: \n");
    PrintArray(arr, n);
    return 0;
}

1.5.2 ?代碼關(guān)鍵點(diǎn)解釋??：

• Partition函數(shù)是核心，它通過雙指針 low和 high的移動(dòng)和賦值完成一輪分區(qū)，使得基準(zhǔn)值 pivot找到其正確位置，并返回該位置索引。
• QuickSort函數(shù)是遞歸主體。先調(diào)用 Partition分區(qū)，然后基于基準(zhǔn)值位置遞歸調(diào)用自身排序左右兩個(gè)子區(qū)間。
• 優(yōu)化提示：若要避免最壞情況，可在 Partition函數(shù)開始前，隨機(jī)交換第一個(gè)元素與 low到 high間的一個(gè)隨機(jī)位置的元素，或使用“三數(shù)取中法”選擇基準(zhǔn)值。

1.6 技術(shù)對(duì)比

排序算法技術(shù)特性對(duì)比

1.7 總結(jié)

快速排序憑借其優(yōu)越的平均時(shí)間復(fù)雜度、原地排序的特性以及對(duì)CPU緩存的友好性，成為處理??大規(guī)模隨機(jī)數(shù)據(jù)排序任務(wù)??時(shí)最常被考慮的算法之一。理解其分治思想和分區(qū)過程是關(guān)鍵。通過隨機(jī)化基準(zhǔn)選擇或三數(shù)取中等策略優(yōu)化，可以有效規(guī)避最壞情況，使其在實(shí)踐中更加可靠。