快速排序（Quick Sort）作为排序算法中的"王者"，以其高效的性能和优雅的实现方式，成为程序员必须掌握的核心算法之一。

---

一、快速排序

快速排序由C.R.A.Hoare于1962年提出，是一种基于分治策略（Divide-and-Conquer）的高效排序算法。它通过对数组进行划分，将大问题分解为小问题，递归解决，最终实现排序。

• 平均时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n²)
• 空间复杂度：O(logn)（递归栈空间）
• 不稳定排序（相同元素的相对位置可能改变）

---

二、算法核心思想

快速排序的精髓可以用三步概括：

1. 选择基准值（Pivot）：从数组中选择一个元素作为分界点
2. 分区操作（Partition）：将数组分为两部分，左边≤基准值，右边≥基准值
3. 递归排序：对左右两个子数组重复上述过程

---

三、详细步骤

3.1 基准值选择策略

常见的基准值选择方式有：

• 首元素法：选择数组第一个元素
• 尾元素法：选择数组最后一个元素
• 中间元素法：选择中间位置的元素
• 随机数选择：使用random随机数选择元素

Sort排序可视化

3.2 分区操作详解

分区是快速排序的核心，主要有两种实现方式：

方式一：双指针交换法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 分区函数：双指针交换法
int partition(vector<int>& arr, int left, int right) {
    // 选择中间元素作为基准值（避免最坏情况）
    int mid = left + (right - left) / 2;//防止(left + right)超过int上限
    int pivot = arr[mid];
    
    // 将基准值移到最右边
    swap(arr[mid], arr[right]);
    
    int i = left - 1;  // i指向小于等于pivot的区域末尾
    
    //交换，保证左侧的数都比基准值小
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    // 将pivot放到正确位置
    swap(arr[i + 1], arr[right]);
    return i + 1;  // 返回pivot的最终位置
}

方式二：填坑法

int partition2(vector<int>& arr, int left, int right) {
    int pivot = arr[left];  // 选择第一个元素作为基准
    int i = left, j = right;
    
    while (i < j) {
        // 从右向左找第一个小于等于pivot的元素
        while (i < j && arr[j] > pivot) j--;
        if (i < j) arr[i++] = arr[j];
        
        // 从左向右找第一个大于pivot的元素
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    
    arr[i] = pivot;  // 填坑
    return i;
}

四、完整快速排序实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

class QuickSort {
public:
    // 主排序函数
    void quickSort(vector<int>& arr) {
        if (arr.empty()) return;
        quickSortHelper(arr, 0, arr.size() - 1);
    }
    
    // 三路快速排序（优化重复元素）
    void quickSort3Way(vector<int>& arr) {
        if (arr.empty()) return;
        quickSort3WayHelper(arr, 0, arr.size() - 1);
    }
    
    // 非递归实现（使用栈）
    void quickSortIterative(vector<int>& arr) {
        if (arr.empty()) return;
        
        stack<pair<int, int>> stk;
        stk.push({0, (int)arr.size() - 1});
        
        while (!stk.empty()) {
            auto [left, right] = stk.top();
            stk.pop();
            
            if (left >= right) continue;
            
            int pivotIndex = partition(arr, left, right);
            
            // 先压入较大的区间（优化栈空间）
            if (pivotIndex - left > right - pivotIndex) {
                stk.push({left, pivotIndex - 1});
                stk.push({pivotIndex + 1, right});
            } else {
                stk.push({pivotIndex + 1, right});
                stk.push({left, pivotIndex - 1});
            }
        }
    }
    
private:
    // 标准快速排序递归函数
    void quickSortHelper(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        
        // 优化部分在下文
        // 优化1：小数组使用插入排序
        if (right - left < 10) {
            insertionSort(arr, left, right);
            return;
        }
        
        // 优化2：三数取中选择pivot
        int pivotIndex = medianOfThree(arr, left, right);
        pivotIndex = partition(arr, left, right);
        
        // 优化3：尾递归优化
        if (pivotIndex - left < right - pivotIndex) {
            quickSortHelper(arr, left, pivotIndex - 1);
            quickSortHelper(arr, pivotIndex + 1, right);
        } else {
            quickSortHelper(arr, pivotIndex + 1, right);
            quickSortHelper(arr, left, pivotIndex - 1);
        }
    }
    
    // 三路快速排序（处理大量重复元素）
    void quickSort3WayHelper(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        
        int pivot = arr[left];
        int lt = left;   // arr[left..lt-1] < pivot
        int gt = right;  // arr[gt+1..right] > pivot
        int i = left + 1; // arr[lt..i-1] == pivot
        
        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr[lt++], arr[i++]);
            } else if (arr[i] > pivot) {
                swap(arr[i], arr[gt--]);
            } else {
                i++;
            }
        }
        
        quickSort3WayHelper(arr, left, lt - 1);
        quickSort3WayHelper(arr, gt + 1, right);
    }
    
    // 三数取中法选择pivot（选择首尾元素时，查找选取中位数作为基准值，避免最坏情况）
    int medianOfThree(vector<int>& arr, int left, int right) {
        int mid = left + (right - left) / 2;
        
        if (arr[left] > arr[mid]) swap(arr[left], arr[mid]);
        if (arr[left] > arr[right]) swap(arr[left], arr[right]);
        if (arr[mid] > arr[right]) swap(arr[mid], arr[right]);
        
        swap(arr[mid], arr[right - 1]);  // 将中位数放到right-1位置
        return right - 1;
    }
    
    // 插入排序（用于小数组优化）
    void insertionSort(vector<int>& arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    // 标准分区函数
    int partition(vector<int>& arr, int left, int right) {
        // 随机选择pivot（避免最坏情况）
        random_device rd;
        mt19937 gen(rd());
        uniform_int_distribution<> dis(left, right);//在left-right中随机选择一元素
        int randomIndex = dis(gen);
        swap(arr[randomIndex], arr[right]);
        
        int pivot = arr[right];
        int i = left - 1;
        
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        
        swap(arr[i + 1], arr[right]);
        return i + 1;
    }
};

// 测试代码
int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90, 88, 45, 50};
    
    cout << "原始数组: ";
    for (int num : arr) cout << num << " ";
    cout << endl;
    
    // 快速排序
    QuickSort qs;
    qs.quickSort(arr);
    
    cout << "排序后: ";
    for (int num : arr) cout << num << " ";
    cout << endl;
    
    // 测试三路快排（重复元素多的情况）
    vector<int> arr2 = {4, 2, 2, 8, 3, 3, 1, 2, 4, 4};
    cout << "\n重复元素测试 - 原始: ";
    for (int num : arr2) cout << num << " ";
    
    qs.quickSort3Way(arr2);
    
    cout << "\n排序后: ";
    for (int num : arr2) cout << num << " ";
    cout << endl;
    
    return 0;
}

五、复杂度分析

5.1 时间复杂度

情况	时间复杂度	说明
最好情况	O(nlogn)	每次分区都均匀，递归树平衡
平均情况	O(nlogn)	随机数据的期望复杂度
最坏情况	O(n²)	数组已排序，每次分区极不均匀

5.2 空间复杂度

• 递归栈空间：O(logn) ~ O(n)
  • 最好/平均：O(logn)（平衡递归树）
  • 最坏：O(n)（退化为链表）

六、优化

6.1 避免最坏情况

// 1. 随机化pivot选择
int randomIndex = left + rand() % (right - left + 1);

// 2. 三数取中法（总体排序程度高时，取头取尾时间复杂度都会很高，递归函数栈深）
int mid = (left + right) / 2;
// 选择left、mid、right的中位数

6.2 小数组优化

当子数组长度小于阈值（通常10-20）时，改用插入排序：

if (right - left < 10) {
    insertionSort(arr, left, right);
    return;
}

6.3 三路快速排序

针对大量重复元素的场景，使用三路快排：

// lt: 小于pivot的边界
// gt: 大于pivot的边界  
// i: 当前处理位置
while (i <= gt) {
    if (arr[i] < pivot) swap(arr[lt++], arr[i++]);
    else if (arr[i] > pivot) swap(arr[i], arr[gt--]);
    else i++;
}

6.4 尾递归优化

减少递归深度，避免栈溢出：

// 先递归处理较小的子数组
if (pivotIndex - left < right - pivotIndex) {
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
} else {
    quickSort(arr, pivotIndex + 1, right);
    quickSort(arr, left, pivotIndex - 1);
}