快熟排序 C++

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

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

// 快速排序函数
void quick_sort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left], i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] < pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

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

在实现中，我们首先选定数组中的第一个元素作为基准值 `pivot`，然后定义两个指针 `i` 和 `j` 分别指向数组的左右两端。接下来，我们从右端开始往左遍历数组，找到第一个小于 `pivot` 的元素，将其赋值给 `arr[i]`，然后从左端开始往右遍历数组，找到第一个大于等于 `pivot` 的元素，将其赋值给 `arr[j]`。重复上述步骤，直到 `i` 和 `j` 相遇。最后，将 `pivot` 的值赋值给 `arr[i]`，然后递归地对左右两个子序列进行快速排序。