如何构建一个网站,短视频营销策划方案,手机网站大全免费下载,北京南站地铁你经过我每个灿烂时刻#xff0c;我才真正学会如你般自由 前些天有些无聊#xff0c;想试试自己写的快排能否过leetcode上的排序算法题。结果是#xff0c;不用截图可想而知#xff0c;肯定是没过的#xff0c;否则也不会有这篇文章的产出。 这份快排算法代码…
你经过我每个灿烂时刻我才真正学会如你般自由 前些天有些无聊想试试自己写的快排能否过leetcode上的排序算法题。结果是不用截图可想而知肯定是没过的否则也不会有这篇文章的产出。 这份快排算法代码在面对大量重复数的时候时间复杂度会下降到O(n^2)这也是为什么leetcode显示最后会超时。所以如何解决呢也许在此之前可以先回顾回顾快排三步核心算法步骤。
——前言 快排的三个核心算法
● HOARE版 这是最早的版本也叫做左右指针法。不过这个算法需要值得注意的是一个地方。排升序时一定是需要右指针先动相反如果是排降序则是左指针先动。
int PartSort1(vectorint nums, int l, int r)
{// 左右指针法int key nums[l];int left l;int right r;while (left right){// 这里需要注意取等 // 如果不取等可能陷入死循环while (left right nums[right] key){right--;}while (left right nums[left] key){left;}if (left right) {swap(nums[left], nums[right]);}}// 处理keyiswap(nums[left], nums[l]);return left;
} 我们对上述例子进行排序后的代码为: ● 挖坑法 int PartSort2(vectorint nums, int l, int r)
{int key nums[l];int hole l;int left l, right r;while (left right){// 右边找小 填左坑while (left right nums[right] key){right--;}// 填坑swap(nums[right], nums[hole]);hole right; // 新坑while (left right nums[left] key){left;}swap(nums[left], nums[hole]);hole left; // 新坑}// hole即为最终落脚点return hole;
} ● 前后指针法 最后的前后指针法也在前言中用到这里不做多的解释。
int PartSort3(vectorint nums, int l, int r)
{int key nums[l];int prev l, cur l 1;while (cur r){// 找小if (nums[cur] key prev ! cur){// prev指向的一定是比key大的数swap(nums[prev], nums[cur]);}cur;}swap(nums[prev], nums[l]);return prev;
} 快速选择排序 可是你使用上述的不管哪种算法都无法跑过leetcode上面的题都会在重复数的情况下超时这里我们可以用到归并分治的思想如果将一个无序数组排序成有序数组选定其中一个数作为key可以将这个数组分为三部分: int getRandom(vectorint nums, int l, int r){int keyi rand();return nums[keyi % (r-l1) l];} void qsort(vectorint nums, int l, int r){if(l r){int key getRandom(nums,l,r);// 数组分三块// 先让left、right指向非法区域int i l,left l-1,right r1;// [i,right]是未处理区域while(i right){if(nums[i] key) swap(nums[left],nums[i]);else if(nums[i] key) i;else swap(nums[--right],nums[i]);}// 递归处理其他区间qsort(nums,l,left);qsort(nums,right,r);}} 我们终于是可以通过啦~ 本篇到此结束感谢你的阅读。
祝你好运向阳而生~
