做网站是用的那个开发软件,建设手机银行,电子商务网站创业计划书,定兴网站建设快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、颜色分类二、排序数组三、数组中的第k个数四、最小的k个数总结 引言
本节主要介绍快速排序#xf… 快乐的流畅个人主页 个人专栏《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、颜色分类二、排序数组三、数组中的第k个数四、最小的k个数总结 引言
本节主要介绍快速排序三路划分随机取key以及它的变形算法——快速选择算法
一、颜色分类 细节快速排序中标准的partition三路划分
设置三个指针 leftcurright划分为三个区域[0, left - 1][left, right][right 1, n-1][0, left - 1]元素小于key[left, right]元素等于key[right 1, n-1]元素大于keyleft和right用来维护等于key的中路元素区域的左右两端cur用来扫描数组
class Solution
{
public:void sortColors(vectorint nums){int left 0, cur 0, right nums.size() - 1;while(cur right){if(nums[cur] 0) swap(nums[left], nums[cur]);else if(nums[cur] 2) swap(nums[right--], nums[cur]);else cur;}}
};二、排序数组 思路
递归出口区间只有一个元素或者不存在随机选key利用rand函数记得提前srand种下随机数种子三路划分三指针维护区间分治继续递归[begin, left - 1][right 1, end]两个区间
class Solution
{
public:int getKey(vectorint nums, int left, int right){int keyi rand() % (right - left 1) left;return nums[keyi];}void quickSort(vectorint nums, int begin, int end){if(begin end) return;int key getKey(nums, begin, end);//随机选keyint cur begin, left begin, right end;while(cur right){if(nums[cur] key) swap(nums[left], nums[cur]);else if(nums[cur] key) swap(nums[right--], nums[cur]);else cur;}quickSort(nums, begin, left - 1);quickSort(nums, right 1, end);}vectorint sortArray(vectorint nums){srand(0);//种下随机数种子quickSort(nums, 0, nums.size() - 1);return nums;}
};三、数组中的第k个数 思路TopK问题有三种解法
排序——O(NlogN)堆——O(NlogK)快速选择——O(N)
堆版本
细节建大堆 k-1次删除
class Solution
{
public:void AdjustDown(vectorint nums, int parent){int n nums.size(), child 2 * parent 1;while(child n){if(child 1 n nums[child] nums[child 1]) child;if(nums[parent] nums[child])//建大堆{swap(nums[parent], nums[child]);parent child;child 2 * parent 1;}else break;}}int findKthLargest(vectorint nums, int k){int n nums.size();for(int i(n-1-1)/2; i0; --i){AdjustDown(nums, i);}while(--k)//执行k-1次{swap(nums[0], nums[nums.size() - 1]);nums.pop_back();AdjustDown(nums, 0);}return nums[0];}
};快速选择版本 细节
从最右边开始数k落在右区域则继续递归找第k大k落在中区域则直接更新结果k落在左区域则继续递归找第k-b-c大
class Solution
{int ret;
public:int GetKey(vectorint nums, int begin, int end){int keyi rand() % (end - begin 1) begin;return nums[keyi];}void qucikSelect(vectorint nums, int begin, int end, int k){if(begin end) return;int key GetKey(nums, begin, end);int left begin, cur begin, right end;while(cur right){if(nums[cur] key) swap(nums[left], nums[cur]);else if(nums[cur] key) swap(nums[right--], nums[cur]);else cur;}if(k end - right) qucikSelect(nums, right 1, end, k);else if(k end - left 1) ret key;else qucikSelect(nums, begin, left - 1, k - (end - left 1));}int findKthLargest(vectorint nums, int k){srand(0);qucikSelect(nums, 0, nums.size() - 1, k);return ret;}
};四、最小的k个数 细节
从最左边开始数k落在左区域则继续递归找最小的k个元素k落在中区域则直接返回前k个元素k落在右区域则继续递归找最小的k-a-b个元素
class Solution
{
public:int getKey(vectorint nums, int begin, int end){int keyi rand() % (end - begin 1) begin;return nums[keyi];}void quickSelect(vectorint nums, int begin, int end, int k){if(begin end) return;int key getKey(nums, begin, end);int left begin, cur begin, right end;while(cur right){if(nums[cur] key) swap(nums[left], nums[cur]);else if(nums[cur] key) swap(nums[right--], nums[cur]);else cur;}if(k left - begin) quickSelect(nums, begin, left - 1, k);else if(k right 1 - begin) return;else quickSelect(nums, right 1, end, k - (right 1 - begin));}vectorint inventoryManagement(vectorint nums, int k){srand(0);quickSelect(nums, 0, nums.size() - 1, k);return {nums.begin(), nums.begin() k};}
};总结
快速排序随机选key保证了时间复杂度逼近O(NlogN)三路划分是为了处理重复大量元素。
快速选择是基于快速排序的变形算法在解决TopK问题有着O(N)的时间复杂度极其高效 真诚点赞手有余香
