快速排序C++实现

下面是一个更简洁、更容易理解的快速排序C++实现。这个版本使用了更直观的方式选择基准值，并通过单独的辅助函数简化了分区过程：

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

// 交换两个元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 分区函数：将数组分为两部分，左边小于基准值，右边大于基准值
int partition(vector<int>& arr, int left, int right) {
    // 选择中间元素作为基准值（更直观的选择）
    int pivot = arr[(left + right) / 2];
    int i = left;    // 左指针
    int j = right;   // 右指针
    
    while (true) {
        // 找到左边第一个大于等于基准值的元素
        while (arr[i] < pivot) i++;
        // 找到右边第一个小于等于基准值的元素
        while (arr[j] > pivot) j--;
        
        // 如果指针交叉，分区完成
        if (i >= j) return j;
        
        // 交换左右指针指向的元素
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
}

// 快速排序主函数
void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        // 分区并获取基准值位置
        int pivotIndex = partition(arr, left, right);
        
        // 递归排序左右两部分
        quickSort(arr, left, pivotIndex);
        quickSort(arr, pivotIndex + 1, right);
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {3, 6, 8, 10, 1, 2, 1};
    
    cout << "排序前的数组: ";
    printArray(arr);
    
    quickSort(arr, 0, arr.size() - 1);
    
    cout << "排序后的数组: ";
    printArray(arr);
    
    return 0;
}

这个实现的特点：

1. 基准值选择：使用中间元素作为基准值，更容易理解和实现
2. 双指针法：通过左右两个指针相向移动，将数组分为两部分
3. 简洁的分区逻辑：使用while(true)循环和指针交叉判断，使分区过程更清晰
4. 递归调用：清晰地将数组分为左右两部分进行递归排序

代码解释：

• partition函数：选择中间元素作为基准值，左右指针分别向中间移动，将比基准值小的元素交换到左边，比基准值大的元素交换到右边，直到指针交叉。
• quickSort函数：递归地对基准值左右两部分进行排序。
• main函数：创建测试数组，调用排序函数并输出结果。

这个版本的快速排序代码更适合初学者理解算法的核心思想，同时保持了良好的性能特性。