1.题目介绍

给你一个整数数组 \(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 * 10^{4}\)
• \(-5 * 10^{4} <= nums[i] <= 5 * 10^{4}\)

2.题解

2.1随机化快速排序

思路

代码

2.2双路快速排序

思路

使用两个索引值（i、j）用来遍历我们的序列，将 <=v 的元素放在索引 i 所指向位置的左边，而将 >=v 的元素放在索引 j 所指向位置的右边，平衡左右两边子数组。

代码

class Solution {
    public int[] sortArray(int[] nums) {
        quicksort(nums,0,nums.length-1);
        return nums;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void quicksort(int[] nums, int start, int end){
        if (start > end) return;
        int v =  new Random().nextInt(end-start+1)+start;
        swap(nums,v,start);
        int ans = nums[start];
        int i = start, j = end;
        // 进行一轮循环
        while (start != end){
            // end开始逆向寻找比基准数小的
            while (true){
                if (start >= end || nums[end] < ans) break;
                end--;
            }
            // start开始正向寻找比基准数大的
            while (true){
                if (start >= end || nums[start] > ans) break;
                start++;
            }
            // 交换两数
            swap(nums,start,end);
        }
        // 结束一轮循环，将基准数与start/end当前所在位置交换
        swap(nums,i, start);
        quicksort(nums,i,start-1);
        quicksort(nums,start+1,j);
    }
}

2.3三路快速排序

思路

我们分三种情况进行讨论 partiton 过程，i 表示遍历的当前索引位置：

（1）当前处理的元素 e=V，元素 e 直接纳入蓝色区间，同时i向后移一位。

（2）当前处理元素 e<v，e 和等于 V 区间的第一个位置数值进行交换，同时索引 lt 和 i 都向后移动一位

（3）当前处理元素 e>v，e 和 gt-1 索引位置的数值进行交换，同时 gt 索引向前移动一位。

最后当 i=gt 时，结束遍历，同时需要把 v 和索引 lt 指向的数值进行交换，这样这个排序过程就完成了，然后对 <V 和 >V 的数组部分用同样的方法再进行递归排序。

代码

class Solution {
    public int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void quicksort(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }

        int pivot = nums[low];
        int lt = low;   // less than pivot
        int gt = high;  // greater than pivot
        int i = low + 1;

        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums, i, lt);
                lt++;
                i++;
            } else if (nums[i] > pivot) {
                swap(nums, i, gt);
                gt--;
            } else {
                i++;
            }
        }

        quicksort(nums, low, lt - 1);
        quicksort(nums, gt + 1, high);
    }
}