快速选择排序

"你经过我每个灿烂时刻，我才真正学会如你般自由" 

---

         前些天有些无聊，想试试自己写的快排能否过leetcode上的排序算法题。结果是，不用截图可想而知，肯定是没过的，否则也不会有这篇文章的产出。

        这份快排算法代码在面对大量重复数的时候，时间复杂度会下降到O(n^2)，这也是为什么leetcode显示最后会超时。所以如何解决呢？也许在此之前，可以先回顾回顾快排三步核心算法步骤。

——前言

---

快排的三个核心算法 ● HOARE版

        这是最早的版本，也叫做左右指针法。不过这个算法需要值得注意的是一个地方。排升序时，一定是需要右指针先动，相反如果是排降序，则是左指针先动。        

int PartSort1(vector<int>& 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]); } } // 处理keyi swap(nums[left], nums[l]); return left; }

        我们对上述例子进行排序后的代码为:

● 挖坑法          int PartSort2(vector<int>& 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(vector<int>& 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(vector<int>& nums, int l, int r) { int keyi = rand(); return nums[keyi % (r-l+1) + l]; } void qsort(vector<int>& nums, int l, int r) { if(l < r) { int key = getRandom(nums,l,r); // 数组分三块 // 先让left、right指向非法区域 int i = l,left = l-1,right = r+1; // [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); } }

        我们终于是可以通过啦~

---

本篇到此结束，感谢你的阅读。

祝你好运，向阳而生~