四时宝库

快速排序是一种常见的排序算法，它的基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后对这两部分分别进行排序，以达到整个序列有序的目的。

以下是用 C++ 实现快速排序的代码：

cpp

复制代码

#include

#include

using namespace std;

// 快速排序函数

void quickSort(vector& nums, int left, int right) {

if (left >= right) {

return;

}

int i = left;

int j = right;

int pivot = nums[(left + right) / 2]; // 选择中间元素作为枢轴

while (i <= j) {

while (nums[i] < pivot) { // 在左侧找到第一个大于等于枢轴的元素

i++;

}

while (nums[j] > pivot) { // 在右侧找到第一个小于等于枢轴的元素

j--;

}

if (i <= j) { // 交换左右两个元素

swap(nums[i], nums[j]);

i++;

j--;

}

}

quickSort(nums, left, j); // 对左侧部分进行递归排序

quickSort(nums, i, right); // 对右侧部分进行递归排序

}

int main() {

vector nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

quickSort(nums, 0, nums.size() - 1);

for (int num : nums) {

cout << num << " ";

}

cout << endl;

return 0;

}

在上述代码中，我们首先定义了一个 quickSort 函数，该函数接收一个整数数组 nums，以及待排序区间的左右下标 left 和 right。在函数中，我们首先判断待排序区间是否为空，如果是则直接返回。否则，我们选择数组中间的元素作为枢轴，并使用双指针法将数组分为左右两部分。然后，我们递归地对左右两部分进行快速排序，直到每个子数组的长度为 1 或 0。最后，我们在 main 函数中调用 quickSort 函数对整个数组进行排序，并输出结果。