刷题训练之分治快排

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握分治快排算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：

这个算法在我们学习数据结构中八大排序之快排，但这个快排比起数据结构中的快排简单不少，这个算在C语言中我们也涉及到了，如果大家对这个算法比较陌生的话，可以参考下面两篇博客，一个是数据结构中的另一个是C语言中的：

数据结构：手撕各种排序

C语言：快快快快快快快快快快排

特点：

我们下面题目所采用的方法都是三路划分法思想，这也和我们的标题分治不谋而合。

大致做题流程：

做题前一定要先画图，在写代码，如果能自己画出图来写代码轻松不少。

🌙topic-->1

题目链接：1.分治快- 颜色分类 - 力扣（LeetCode）

题目分析：

题目意思比较简单，把数组中的0 1 2排序。

算法原理：

解法：采用三指针

图解：

细节处理：

left需要指向为 - 1，循环条件为 i < right.

代码演示：

class Solution 
{
public:
    void sortColors(vector<int>& nums) 
    {
        int n = nums.size();
        // 定义三个指针
        int left = -1,right = n,i = 0;
        // 循环
        while(i < right) // 细节
        {
            if(nums[i] == 0) swap(nums[++left],nums[i++]);
            else if(nums[i] == 1) i++;
            else swap(nums[--right],nums[i]);
        }
    }
};

🌙topic-->2

题目链接：2.排序数组 - 力扣（LeetCode）

题目分析：

给你一个整数数组 nums，请你将该数组升序排列。（解法有很多，我们采用快速排序算法）

算法原理：

解法：采用快速排序算法(三指针)

图解：

细节处理：

递归结束标志是 l >= r

代码演示：

class Solution 
{
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(NULL)); // 种下随机种子
        qsort(nums, 0, nums.size() - 1); // 调用快速排序
        return nums; // 返回数组
    }

    // 快排
    void qsort(vector<int>& nums,int l,int r)
    {
        if(l >= r) return; // 递归结束条件

        // 数组分三块
        int key = getRandom(nums, l, r); // 找一个对比值
        int i = l,left = l - 1,right = r + 1; // 三个指针
        // 循环
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right],nums[i]);
        }

        // 划分三个区域 [l ,left]  [left + 1, right - 1]  [right, r]
        qsort(nums ,l ,left);
        qsort(nums ,right ,r);
    }

    // 找对比值
    int getRandom(vector<int>& nums ,int left,int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
};

🌙topic-->3

题目链接：3. 数组中的第K个最大元素 - 力扣（LeetCode）3. 数组中的第K个最大元素 - 力扣（LeetCode）

题目分析：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。（你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。）

算法原理：

解法：采用快速排序算法(三指针)

图解：

细节处理：

递归结束标志是 l == r

代码演示：

class Solution 
{
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL));// 种下随机种子
        return qsort(nums, 0 ,nums.size() - 1, k); // 调用快排
    }

    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if(l == r) return nums[l];// 递归结束条件

        // 随机选择基准元素
        int key = getRandom(nums, l, r);
        // 数组分三块
        int left = l - 1,right = r + 1,i = l;
        // 循环
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }

        // 讨论
        int c = r - right + 1,b = right - left - 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};

🌙topic-->4

题目链接：

题目分析：

输入整数数组 arr，找出其中最小的 k 个数。（跟上面的题目相似，这里不在细致讲解）

算法原理：

解法：采用快速排序算法(三指针)

图解：

细节处理：

递归结束标志是 l >= r

代码演示：

class Solution
{
public:
	vector<int> getLeastNumbers(vector<int>&nums, int k)
	{
		srand(time(NULL));
		qsort(nums, 0, nums.size() - 1, k);
		return { nums.begin(), nums.begin() + k };
	}
	void qsort(vector<int>& nums, int l, int r, int k)
	{
		if (l >= r) return;
		// 1. 随机选择⼀个基准元素 + 数组分三块
		int key = getRandom(nums, l, r);
		int left = l - 1, right = r + 1, i = l;
		while (i < right)
		{
			if (nums[i] < key) swap(nums[++left], nums[i++]);
			else if (nums[i] == key) i++;
			else swap(nums[--right], nums[i]);
		}
		// [l, left][left + 1, right - 1] [right, r]
		// 2. 分情况讨论
		int a = left - l + 1, b = right - left - 1;
		if (a > k) qsort(nums, l, left, k);
		else if (a + b >= k) return;
		else qsort(nums, right, r, k - a - b);
	}
	int getRandom(vector<int>& nums, int l, int r)
	{
		return nums[rand() % (r - l + 1) + l];
	}
};