leetcode-912.排序数组

题目链接

912.排序数组

代码

快速排序

class Solution {
    public int[] sortArray(int[] nums) {

        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        // 快速排序算法偏爱 随机
        // 随机选择一个在 lo, hi 范围内的下标跟 lo 的下标替换
        int rand = ThreadLocalRandom.current().nextInt(lo, hi);
        swap(nums, lo, rand);

        int i = lo;
        int j = hi;
        int pivot = nums[lo];

        while (i < j) {
            // 对于下面两行为什么不能调换位置
            // 什么情况下能调换位置
            // 拉到最下面去看 参考里的 [为什么经典快排先从右往左找]
            while (i < j && nums[j] >= pivot) j--;
            while (i < j && nums[i] <= pivot) i++;

            swap(nums, i, j);
        }

        swap(nums, lo, i);
        qsort(nums, lo, i - 1);
        qsort(nums, i + 1, hi);
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

复杂度分析

• 时间复杂度: 平均时间复杂度 O(NlogN)
• 空间复杂度: 最优为 O(logN)，最坏为 O(N)

参考

• 为什么经典快排先从右往左找