快速排序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函数：创建测试数组，调用排序函数并输出结果。

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