快速排序算法详解：C++实现与优化技巧

什么是快速排序？

快速排序（Quick Sort） 是由英国计算机科学家Tony Hoare于1959年发明的一种高效的分治排序算法。它是目前最常用的排序算法之一，平均时间复杂度为 O(n log n)，在实际应用中表现优异。

快速排序的核心思想

快速排序采用分治（Divide and Conquer）策略：

分解（Divide）：从数组中选择一个基准元素（pivot），将数组分成两部分：

左侧：所有小于基准的元素
右侧：所有大于基准的元素

递归（Conquer）：对左右两部分分别递归进行快速排序
合并（Combine）：由于排序是就地进行的，递归结束时数组已经有序

partition 划分方式

最常用的是 Lomuto 划分 和 Hoare 划分：

#include <iostream>
#include <vector>
using namespace std;

// Lomuto 划分方式
int partition_lomuto(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Hoare 划分方式（更高效）
int partition_hoare(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

// 快速排序主函数
void quick_sort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition_lomuto(arr, low, high);
        
        // 递归排序左右两部分
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

// 优化版本：三数取中选取基准
int median_of_three(vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
    
    return mid;  // 返回中间值的索引
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    
    cout << "排序前: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    quick_sort(arr, 0, n - 1);
    
    cout << "排序后: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    return 0;
}

快速排序的优化技巧

三数取中法：选择low、mid、high三个位置的中值作为基准，避免最坏情况
小数组使用插入排序：当数组长度小于10时，使用插入排序更高效
尾递归优化：减少递归深度
三路划分：处理大量重复元素的数组

复杂度分析

情况	时间复杂度	空间复杂度
最好	O(n log n)	O(log n)
平均	O(n log n)	O(log n)
最坏	O(n²)	O(n)

最坏情况发生在数组已经有序或完全逆序时，可以通过上述优化技巧避免。

快速排序 vs 其他排序

特性	快速排序	归并排序	堆排序
平均时间	O(n log n)	O(n log n)	O(n log n)
最坏时间	O(n²)	O(n log n)	O(n log n)
空间复杂度	O(log n)	O(n)	O(1)
稳定性	❌ 不稳定	✅ 稳定	❌ 不稳定
原地排序	✅ 是	❌ 否	✅ 是

总结

快速排序之所以广泛应用，是因为：

平均性能优秀
原地排序，空间效率高
缓存命中率高

掌握快速排序是理解分治思想和算法优化的绝佳例子。