写出快速排序算法。并对它最坏、最好，平均情况进行比较分析。用C/C++实现

好的，下面是快速排序算法的实现（C++）：

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[left];
    int i = left + 1;
    int j = right;
    while (true) {
        while (i <= j && nums[i] < pivot) i++;
        while (i <= j && nums[j] > pivot) j--;
        if (i > j) break;
        swap(nums[i++], nums[j--]);
    }
    swap(nums[left], nums[j]);
    return j;
}

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int pivotIdx = partition(nums, left, right);
    quickSort(nums, left, pivotIdx - 1);
    quickSort(nums, pivotIdx + 1, right);
}

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

快速排序算法的最坏时间复杂度为$O(n^2)$，当待排序的序列已经有序时，每次选择的枢轴都是最大或最小元素，此时快速排序将退化为选择排序或冒泡排序，时间复杂度为$O(n^2)$。

快速排序算法的平均时间复杂度为$O(nlogn)$，证明过程比较复杂，这里就不展开讲解了。

快速排序算法的最好时间复杂度为$O(nlogn)$，当每次选择的枢轴刚好是中位数时，快速排序的效率最高。

综上所述，快速排序算法是一种高效的排序算法，它的平均时间复杂度为$O(nlogn)$，但是在最坏情况下，时间复杂度会退化为$O(n^2)$。