快速排序⭐⭐⭐

[HealUP]

理论基础：快速排序是一种常见的排序算法，使用分治的思想来排序一个数组或列表。它的基本思想是选择一个基准数，将数组分成两个部分，一部分是小于基准数的，另一部分是大于等于基准数的，然后再对这两部分递归地进行排序

时间复杂度：nlogn

具体步骤如下：

1. 选择一个基准数（pivot），可以选择第一个数、最后一个数、中间的数或者随机数。
2. 将数组中小于等于基准数的元素放在基准数的左边，大于基准数的元素放在基准数的右边，这一步称为**“划分**”（partition）操作。
3. 对基准数左边的子数组进行递归排序，对基准数右边的子数组进行递归排序，直到每个子数组的长度为 0 或 1，排序完成。

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    // 快速排序函数
    public static int[] quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return null;
        }
        int partition = partition(nums, left, right);
        quickSort(nums, left, partition - 1);//在划分位置的左边子区域再划分，直到不可划分left >= right不能进循环条件
        quickSort(nums, partition + 1, right); //在划分位置的右边子区域再划分，直到不可划分left >= right不能进循环条件
        return nums;
    }

    public static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot; //当前left，right 指向同一个位置了 nums[right] = pivot也行
        return left;// 返回划分的位置
    }
}