912. 排序数组

解法一：随机快排

随机快排。

class Solution {
    private int[] arr;
    public int[] sortArray(int[] nums) {
        arr = nums.clone();
        sort();
        return arr;
    }
    public void sort() {
        _sort(0, arr.length - 1);
    }
    private void _sort(int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition(left, right);
        _sort(left, mid - 1);
        _sort(mid + 1, right);
    }
    private int partition(int left, int right) {
        int index = new Random().nextInt(right - left + 1) + left;
        int temp = arr[index];
        arr[index] = arr[left];
        arr[left] = temp;
        int mid = arr[left];
        while (left < right) {
            while ((left < right) && (arr[right] >= mid)) {
                --right;
            }
            arr[left] = arr[right];
            while ((left < right) && (arr[left] <= mid)) {
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[left] = mid;
        return left;
    }
}