C++ 写一个快速排序

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

下面是一个基于递归的快速排序的实现：

#include <stdio.h>

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

// 测试函数
int main() {
    int arr[] = { 3, 9, 7, 1, 8, 2, 6, 5, 4 };
    int len = sizeof(arr) / sizeof(arr[0]);
    quick_sort(arr, 0, len - 1);
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

在上面的代码中，`quick_sort` 函数接收三个参数：待排序数组 `arr`，排序区间左端点 `left` 和排序区间右端点 `right`。在函数内部，首先判断左右端点是否相遇，如果相遇则表示排序已经完成，直接返回；否则，选择区间的第一个元素 `pivot` 作为基准值，从右端点开始向左扫描，找到第一个小于 `pivot` 的元素，将其放到左端点上，然后从左端点开始向右扫描，找到第一个大于 `pivot` 的元素，将其放到右端点上，重复上述过程，直到左右端点相遇，然后将基准值 `pivot` 放到相遇的位置上，此时数组被分成了两个部分，左边的元素都小于等于 `pivot`，右边的元素都大于等于 `pivot`。最后，对左右两个部分分别调用 `quick_sort` 函数进行递归排序即可。

在测试函数中，我们首先定义了一个待排序数组 `arr`，然后计算出数组的长度，调用 `quick_sort` 函数对数组进行排序，最后输出排序后的结果。