912. 排序数组

刷题 leetcode

题目：给你一个整数数组 nums，请你将该数组升序排列

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

链接：https://leetcode.cn/problems/sort-an-array

题目中数组长度范围比较大，考虑使用快速排序，因为它快呀

class Solution {
    //数组长度范围比较大，考虑使用快速排序
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }
    Random random = new Random();
    //对数组nums的区间[left,right]的元素进行排序
    private void quickSort(int[] nums, int left, int right){
        if(left>=right) return;
        int index = left+random.nextInt(right-left+1);//随机化，避免极端情况效率低下
        int pivot=nums[index];  //先把基准元素提出来
        nums[index]=nums[left]; //最左边产生一个坑位
        int L=left, R=right;
        while(L<R){
            while(L<R && nums[R]>=pivot) R--;   //找到右边第一个小于基准的元素
            nums[L]=nums[R];                    //将此元素填入左边的坑中(基准左侧)
            while(L<R && nums[L]<=pivot) L++;   //找到右边第一个大于基准的元素
            nums[R]=nums[L];                    //将此元素填入右边的坑中(基准右侧)
        }
        nums[L]=pivot;  //左右指针重合后，将基准元素放回重合位置
        //基于分治思想对左右区间排序
        quickSort(nums,left,L-1);
        quickSort(nums,L+1,right);
    }
}