阅读量:0
C++中的快速排序（Quick Sort）是一种高效的排序算法，其基本思想是通过选取一个基准元素，将数组分为两部分，使得一部分的元素都小于基准元素，另一部分的元素都大于基准元素，然后对这两部分递归地进行快速排序。
以下是一个简单的C++快速排序实现：
#include<iostream> #include<vector> using namespace std; // 快速排序的分区函数 int partition(vector<int>& arr, int low, int high) { int pivot = arr[low]; // 选取第一个元素作为基准 while (low< high) { while (low< high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; // 将比基准小的元素移到左边 while (low< high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; // 将比基准大的元素移到右边 } arr[low] = pivot; // 把基准元素放到正确的位置 return low; // 返回基准元素的索引 } // 快速排序的递归函数 void quickSort(vector<int>& arr, int low, int high) { if (low< high) { int pivotIndex = partition(arr, low, high); // 获取基准元素的索引 quickSort(arr, low, pivotIndex - 1); // 对左侧子数组进行快速排序 quickSort(arr, pivotIndex + 1, high); // 对右侧子数组进行快速排序 } } int main() { vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; quickSort(arr, 0, arr.size() - 1); for (int i = 0; i < arr.size(); i++) { cout<< arr[i] << " "; } cout<< endl; return 0; } 这个实现中，partition函数用于将数组划分为两部分，quickSort函数则是递归地对这两部分进行排序。在main函数中，我们创建了一个包含一些整数的向量，并调用quickSort函数对其进行排序。最后，我们打印出排序后的结果。
