用C++实现一个通用版本的快排

以下是使用 C++ 实现通用版本的快排的示例代码：

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
void quick_sort(vector<T>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    T pivot = arr[left];
    int i = left + 1, j = right;
    while (i <= j) {
        while (i <= j && arr[i] < pivot) {
            ++i;
        }
        while (i <= j && arr[j] > pivot) {
            --j;
        }
        if (i <= j) {
            swap(arr[i++], arr[j--]);
        }
    }
    swap(arr[left], arr[j]);
    quick_sort(arr, left, j - 1);
    quick_sort(arr, j + 1, right);
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

在这个示例中，我们使用了模板来实现一个通用版本的快排。快排的核心思想是选择一个基准元素，将数组分成两部分，其中一部分中的所有元素都小于基准元素，另一部分中的所有元素都大于等于基准元素。然后递归地对两个子数组进行排序，直到整个数组有序。在实现中，我们通过指针移动来进行元素的交换和分区。