CC56.【C++ Cont】分治算法:快排的简要复习(含手撕快排题)-CSDN博客

5.思考题:如果不使用递归算法应该怎么写?

1.核心思想

分治即分而治之,将大问题转化为若干个相似的子问题,子问题又可以转化为若干个相似的子子问题......

典型例子是快速排序和归并排序

2.知识回顾:快速排序

119.【C语言】数据结构之快速排序(调用库函数)

120.【C语言】数据结构之快速排序(详解Hoare排序算法)

121.【C语言】数据结构之快速排序(未优化的Hoare排序存在的问题)以及时间复杂度的分析

122.【C语言】数据结构之快速排序(Hoare排序的优化)

123.【C语言】数据结构之快速排序挖坑法和前后指针法

124.【C语言】数据结构之快速排序的小区间优化和非递归的解决方法

下面的例题会用到之前文章提过的随机选key+三路划分

3.复习例题1:颜色分类

之前在CC30.【C++ Cont】双指针及其衍生算法专题(含移动零、颜色分类)文章讲过了,这里不再赘述

4.复习例题2:排序数组(手撕快排)

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。
提示：

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4

分析

读题发现题目要求"时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小",显然是需要使用快速排序

由于提供的部分测试用例很特殊(例如所有元素都是相同值的数组),导致原版的Hoare排序是超时的.key一直选最左侧或一直选最右侧,时间复杂度过高

这里使用优化过的Hoare排序:随机选key(防止时间复杂度升高)+三路划分

和例题1颜色划分的核心思想一样,分三路:1.<key 2.==key 3.>key

(这是核心步骤:划分Partition)

还是3个指针:left, i, right(left和right分别划分左右区间,i为遍历指针)

因为排升序,则[0,left]为<key的区间,[left+1,i-1]为==key的区间,[i,right-1]为待排序的区间,[right,nums.size()-1]为>key的区间

执行后,则[0,left]为<key的区间,[left+1,right-1]为==key的区间,[right,nums.size()-1]为>key的区间

,其中[0,left]和[right,nums.size()-1]可能无序,需要继续递归排序,直到left>=right停止排序

对于所有元素都是相同值的数组只需要一次递归,左区间和右区间都没有元素

因此需要使用一个递归函数,对区间[left,right]选key后分三路,其中<key和>key区间需要分别递归

代码:

class Solution {
public:
    void parition(vector<int>& nums,int left,int right) 
    {
        if (left>=right)//递归结束
            return;
        int disp=rand()%(right-left+1);//偏移量
        int key=nums[left+disp];//从left和right闭区间内随机选key
        //_left为[left,right]最左侧的左侧,_right为[left,right]最右侧的右侧
        int _left=left-1,_right=right+1;
        for (int i=left;i<_right;i++)
        {
            if (nums[i]<key)
            {
                swap(nums[i],nums[++_left]);
            }
            if (nums[i]>key)
            {
                swap(nums[i--],nums[--_right]);
            }   
        }
        //[left,_left]都<key,[_left,_right-1]都==key,[_right,right]都>key
        //左区间递归
        parition(nums,left,_left);
        //右区间递归
        parition(nums,_right,right);
    }
    
    vector<int> sortArray(vector<int>& nums)//快速排序 
    {
        srand((unsigned int)time(nullptr));//不用写在parition中
        parition(nums,0,nums.size()-1);
        return nums;
    }
};