c++实现一个快速排序

快速排序是一种常用的排序算法，基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。以下是C++实现快速排序的代码：

#include <iostream>
#include <vector>

using namespace std;

// 快速排序
void quick_sort(vector<int>& nums, int left, int right) {
    if (left >= right) return; // 递归终止条件

    int i = left, j = right, pivot = nums[left];
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数
        if (i < j) nums[i++] = nums[j];
        while (i < j && nums[i] < pivot) i++; // 从左往右找到第一个大于等于pivot的数
        if (i < j) nums[j--] = nums[i];
    }
    nums[i] = pivot;
    quick_sort(nums, left, i-1); // 对pivot左边部分排序
    quick_sort(nums, i+1, right); // 对pivot右边部分排序
}

int main() {
    vector<int> nums = {9, 5, 7, 2, 3, 6, 8, 1, 4};
    quick_sort(nums, 0, nums.size()-1);
    for (auto num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

在上面的代码中，我们使用了vector存储待排序的数列，并实现了一个quick_sort函数来进行排序。函数的参数包括待排序数列nums、左右边界left和right。当left >= right时，递归终止，否则将数列分为两部分，对左右两部分分别进行排序即可。在分割数列时，我们选择左端点作为枢纽元，对数列进行划分，将小于枢纽元的数放在左边，大于等于枢纽元的数放在右边，最后将枢纽元放到数列中间，即可完成一次划分。在这个过程中，使用双指针分别从左右两端开始向中间扫描，找到需要交换的数进行交换。