算法分析 ——《快速排序》
文章目录
- 《颜色分类》
- 题目描述：
- 代码演示：
- 代码解析：
- 《排序数组》
- 题目描述：
- 代码演示：
- 代码解析：
- 《数组中的第K个最大元素》
- 题目描述：
- 代码演示：
- 代码解析：
- [《库存管理 III》](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/)
- 题目描述：
- 代码演示：
- 代码解析：
《颜色分类》
题目描述：
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
代码演示：
class Solution
{
public:
void sortColors(vector<int>& nums)
{
// 分区来模拟
for(int i = 0, left = -1, right = nums.size(); i < right; )
{
if(nums[i] == 0) swap(nums[++left], nums[i++]);
else if(nums[i] == 1) ++i;
else swap(nums[--right], nums[i]);
}
}
};
代码解析：
这道题和我们在讲解双指针专题第一题是一样的思路，参考：《移动零》，以及博客：算法分享——《双指针》。
所以对于这道题来说，其实无非就是从双指针转换成三指针，虽然这题与分治无关，但是该题目的底层思路我们还是需要去了解学习的。
具体的算法思路我就不讲了，因为在之前的双指针环节有介绍过，所以我就直接展示出算法核心步骤了。
《排序数组》
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
代码演示：
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
srand(time(nullptr));
qsort(nums, 0, nums.size() - 1);
return nums;
}
void qsort(vector<int>& nums, int l, int r)
{
if(l >= r) return;
int mid = nums[(rand() % (r - l + 1)) + l];
int left = l - 1, right = r + 1, i = l;
while(i < right)
{
if(nums[i] < mid) swap(nums[++left], nums[i++]);
else if(nums[i] == mid) ++i;
else swap(nums[--right], nums[i]);
}
qsort(nums, l, left);
qsort(nums, right, r);
}
};
代码解析：
这道题目就是一道经典的「快速排序」，曾经我在讲解数据结构的博客有聊过快速排序的三种实现方式及其思路，如果不熟悉的话可以回到这篇文章看看：《插入排序》与《选择排序》。
简单来说，快速排序就是基于一个数字mid，然后将小于mid的放在左边，大于mid的放在右边，然后不断分治规划，本质就是一个递归操作。
那现在是在算法题中，解决思路就是“分治”，采取的算法思路就是刚刚讲解的，数组分三块的思路：
因为要划分区域，所以我们还是定义两个指针left和right，然后先进行一次遍历，将数组划分成三块，具体的方法和《颜色分类》的方法一致，但是第一次遍历肯定还是乱序的，因为只是大概的进行排序。
这时候，数组肯定会分成如下的情况：
所以继续使用递归，分别对[l, left]和[right, r]这两个区间去排序即可。
《数组中的第K个最大元素》
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
代码演示：
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 = nums[rand() % (r - l + 1) + l]; // 找基准数
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);
}
};
代码解析：
题目的意思特别好理解，这无非就是一个经典的 top - k 问题，而针对该问题，我们第一次是用堆排序的算法来解决的，可是题目要求我们设计一个$ O(n) $的时间复杂度，那么堆排序肯定就pass掉了，所以在这里我们尝试使用： “数组分三块”的快排思路来解决。
第一步我们需要进行一个经典的数组分三块
这一步很好理解，因为我们已经动手实现过很多次了，不过这里我们的最终目标是找到第k大的那个数字，如果上面的数组已经排好序了，那么想找到第k大的数，就是从最右往左开始，数第k个，那么停下来的数，就是我们所需要找到的数字。
所以有：
这类的算法思路，就叫做「快速选择排序」算法
《库存管理 III》
题目描述：
仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
示例 1：
输入：stock = [2,5,7,4], cnt = 1
输出：[2]
示例 2：
输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]
代码演示：
class Solution
{
public:
vector<int> inventoryManagement(vector<int>& stock, int cnt)
{
srand(time(nullptr));
qsort(stock, 0, stock.size() - 1, cnt);
return {stock.begin(), stock.begin() + cnt};
}
void qsort(vector<int>& stock, int l, int r, int cnt)
{
if(l >= r) return;
int key = stock[(rand() % (r - l + 1)) + l];
int left = l - 1, right = r + 1, i = l;
while(i < right)
{
if(stock[i] < key) swap(stock[++left], stock[i++]);
else if(stock[i] == key) ++i;
else swap(stock[--right], stock[i]);
}
int a = left - l + 1, b = right - left - 1;
if(a >= cnt) qsort(stock, l, left, cnt);
else if(a + b >= cnt) return;
else qsort(stock, right, r, cnt - a - b);
}
};
代码解析：
该题目的算法思路与上题一致，无非就是从取大的转变为取小的，在这里我也不做过的赘述。