Leetcode No.912 排序数组（快速排序）

一、题目描述

给你一个整数数组 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 <= 50000 -50000 <= nums[i] <= 50000

二、解题思路

快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。

我们定义函数 randomized_quicksort(nums, left, right) 为对 nums 数组里[left,right]的部分进行排序，每次先调用 randomized_partition 函数对 nums 数组里 [left,right] 的部分进行划分，并返回分界值的下标 pos，然后按上述将的递归调用

randomized_quicksort(nums, left, pos - 1)

和 randomized_quicksort(nums, pos + 1, right) 即可。

那么核心就是划分函数的实现了，划分函数一开始需要确定一个分界值（我们称之为主元 pivot)，然后再进行划分。而主元的选取有很多种方式，这里我们采用随机的方式，对当前划分区间 [left,right] 里的数等概率随机一个作为我们的主元，再将主元放到区间末尾，进行划分。

整个划分函数 partition 主要涉及两个指针 i 和 j，一开始 i = j = left。我们需要实时维护两个指针使得任意时候，对于任意数组下标 k，我们有如下条件成立：

left≤k≤i-1 时，nums[k]≤pivot。

i≤k≤j−1 时，nums[k]>pivot。

k==right 时，nums[k]=pivot。

我们每次移动指针 j ，如果 nums[j]>pivot，我们只需要继续移动指针 j ，即能使上述三个条件成立，否则我们需要交换 nums[i] 和nums[j]，然后将指针 i 加一，再移动指针 j 才能使得三个条件成立。

当 j 移动到right−1 时结束循环，此时我们可以由上述三个条件知道 [left,i) 的数都小于等于主元 pivot，[i,right-1]的数都大于主元 pivot，那么我们只要交换nums[i] 和nums[right] ，即能使得 [left,i) 区间的数都小于[i,right] 区间的数，完成一次划分，且分界值下标为i，返回即可。

如下的动图展示了一次划分的过程，刚开始随机选了 4作为主元，与末尾元素交换后开始划分：

三、代码

class Solution {
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j <= right - 1; ++j) {
            if (nums[j] <= pivot) {
                swap(nums[i++], nums[j]);
            }
        }
        swap(nums[i], nums[right]);
        return i;
    }
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

四、复杂度分析

时间复杂度：基于随机选取主元的快速排序时间复杂度为期望O(nlogn)，其中 n 为数组的长度。详细证明过程可以见《算法导论》第七章，这里不再大篇幅赘述。

空间复杂度：O(h)，其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n) 的空间，最优情况下每次都平衡，此时整个递归树高度为 logn，空间复杂度为 O(logn)。