题解 | #牛群的排序# 快排

#include <vector>
class Solution {
  public:
    void quickSort(vector<int>& nums, int left, int right) {
        int i = left, j = right;
        int pivot = nums[(left + right) / 2];
        while (i <= j) {
            while (nums[i] < pivot) {
                i++;
            }
            while (nums[j] > pivot) {
                j--;
            }
            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j--;
            }
        }
        if (i < right) {
            quickSort(nums, i, right);
        }
        if (j > left) {
            quickSort(nums, left, j);
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector
     */
    vector<int> sortCows(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

时间复杂度：

最优情况：O(n log n)

平均情况：O(n log n)

最坏情况：O(n^2)（在数组已经有序或者所有元素相同的情况下）

空间复杂度：

最优情况：O(log n)（使用递归调用栈的深度）

最坏情况：O(n)（在最坏情况下，递归调用栈的深度为n）