力扣刷题实录（大厂用题）3 —— 912. 排序数组

912. 排序数组

力扣题目地址：https://leetcode.cn/problems/sort-an-array/

题目描述

给你一个整数数组 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$

分析过程

看起来是一个毫无新意的老题，心里轻蔑的一想，不就是写个快排吗。

接着几分钟就写好了快排代码，提交便提示超时。

问题何在？因为这个问题要求更加严格，因此简单的两路快排是完全不够的。三路快排甚至也不满足要求，最后查了一下，发现官方教程中提到添加随机选数进而优化效果。

最后添加了一个随机索引的过程，总算解决了这个问题。花的时间也比较多。

所以总结下来这道题目本身不复杂，非常常见的快速排序题目，但是需要注意的细节就两个：

三路快排
随机取数

此处的随机取数是指每轮排序的时候，需要选择一个 key，将数组中的元素划分为 3 类，大于 key 的，等于 key 的，以及小于 key 的。

代码实现

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    /**
    * 根据 nums[low] 作为参考，将数组划分为两组
    * @param nums 原数组
    * @param low 需要排序的子数组的索引开始
    * @param high 需要排序的子数组的索引结束
    * @return low 或者 high 因为二者相等，以后将会根据这个索引将原数组分为两个子数组
    */
    pair<int,int> partition(vector<int>& nums, int low, int high) {
        int index = rand() % (high - low) + low;
        swap(nums[index], nums[low]);
        // 作为比较的对象，接下根据大小关系把数组分为三类
        int key = nums[low];
        // 记录一下开始的位置，最后需要用到
        int start = low;
        // mid 指针走的比 low 快，会更快找到 high 然后停止
        int mid = low + 1;
        // 注意这里的停止条件是 mid 找到 high
        while (mid <= high) {
            // 如果 nums[mid] 小于 key，就放到左边 的 low + 1 的位置
            if (nums[mid] < key) {
                swap(nums[++low], nums[mid++]);
            } else if (nums[mid] > key) {
                // 如果大于 key 的话这里和两路排序没有区别，但是之前的low换成了现在的mid，注意mid指针不需要移动
                swap(nums[mid], nums[high--]);
            } else {
                // 如果相等的话，那么只需要移动mid指针，因为其他的两端已经基本有序，本地的移动跟它们没有关系
                mid++;
            }
        }
        // 最后一定要把最开始选择的 key 移动中间去，换完成后
        swap(nums[start], nums[low]);
        return {low, high};
    }

    /**
    * 快速排序
    * @param nums 待排序的数组
    * @param low 待排序的数组的开始索引
    * @param high 待排序的数组的结束索引
    */
    void quickSort(vector<int>& nums, int low, int high) {
        if (low < high) {
            pair<int, int> part = partition(nums, low, high);
            quickSort(nums, low, part.first - 1);
            quickSort(nums, part.second + 1, high);
        }
    }
};