快速排序就是二叉树的前序遍历
Quick Sort
二叉树前序遍历
- 先处理当前节点，再处理左右子树
void preorder(TreeNode*root){if(root==nullptr){return;}//前序位置preorder(root->left);preorder(root->right);
}
快排
- 先给一个元素排好位置,再给其它元素排位置
怎么确定一个元素的位置？
- 维护该元素 左侧所有元素都小于等于它，右侧元素都大于它 那么它的位置就找到了
初步实现，后文有优化
void quicksort(vector<int>&nums,int left,int right){if(left>right){return;}int piv=nums[left];int i=left+1,j=right;while(1){while(j>=i&&nums[i]<=piv){i++;}while(j>=i&&nums[j]>piv){j--;}if(i>j)break;swap(nums[i],nums[j]);}int p=j;swap(nums[p],nums[left]);quicksort(nums,left,p-1);quicksort(nums,p+1,right);
}
时间复杂度
类比归并排序，如果我们每次选择的 piv = nums[left] 都能将区间二分，那将是理想的n logn
但如果你用上面的代码提交 leetcode 912 会发现 TLE
为什么呢？
引入快速排序的不适用场景
一、原数组有序性强 -> 容易选到最值元素
如果我们每次选择的 piv = nums[left] 都能将区间二分，那将是理想的n logn
但如果我们选到了最值元素，我们只能将区间一分，相当于挑出了当前区间的最值
如果我们每次都选到最值元素，将会退化为 n^2 的选择排序
如果原数组有序性强，我们每次选piv = nums[ left / right ]都不太合适
一种对策是选中点 piv = nums[ (left+right)/2 ]
但更好的姿态是 ：
- 随机选取
srand((unsigned)time(NULL));
piv = nums[left + rand() % (right - left + 1)]
实际实现时我们是将 piv 移到最左侧
也就是在选 piv 前加入swap(nums[left],nums[left+rand()%(right-left+1)])
code
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand((unsigned)time(NULL));quicksort(nums,0,nums.size()-1);return nums;}void quicksort(vector<int>&nums,int left,int right){if(left>right){return;}swap(nums[left],nums[left+rand()%(right-left+1)]);int piv=nums[left];int i=left+1,j=right;while(1){while(j>=i&&nums[i]<=piv){i++;}while(j>=i&&nums[j]>piv){j--;}if(i>j)break;swap(nums[i],nums[j]);}int p=j;swap(nums[p],nums[left]);quicksort(nums,left,p-1);quicksort(nums,p+1,right);
}
};
- 打乱原数组
srand((unsigned)time(NULL));for(int i=0;i<(int)nums.size();++i){swap(nums[i],nums[i+rand()%(nums.size()-i)]);
}
code
class Solution {void shuffle(vector<int>&a){int n=a.size();srand((unsigned)time(NULL));for(int i=0;i<n;++i){swap(a[i],a[i+rand()%(n-i)]);}}
public:vector<int> sortArray(vector<int>& nums) {shuffle(nums);quicksort(nums,0,nums.size()-1);return nums;}void quicksort(vector<int>&nums,int left,int right){if(left>right){return;}int piv=nums[left];int i=left+1,j=right;while(1){while(j>=i&&nums[i]<=piv){i++;}while(j>=i&&nums[j]>piv){j--;}if(i>j)break;swap(nums[i],nums[j]);}int p=j;swap(nums[p],nums[left]);quicksort(nums,left,p-1);quicksort(nums,p+1,right);
}
};
现在，我们已经可以通过leetcode 912
但效率极其低下，这是不能容忍的
我们接着优化
二、大量重复元素
上面我们为一个元素排序的策略是 ：
维护该元素 左侧所有元素都小于等于它，右侧元素都大于它
注意我们将相等的元素都排到了左侧
如果有大量重复元素，这无疑会浪费很多性能
优化二路快排
while(1){while(j>=i&&nums[i]<piv){i++;}while(j>=i&&nums[j]>piv){j--;}if(i>j)break;swap(nums[i],nums[j]);i++,j--;
}
code
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand((unsigned)time(NULL));quicksort(nums,0,nums.size()-1);return nums;}void quicksort(vector<int>&nums,int left,int right){if(left>right){return;}swap(nums[left],nums[left+rand()%(right-left+1)]);int piv=nums[left];int i=left+1,j=right;while(1){while(j>=i&&nums[i]<piv){i++;}while(j>=i&&nums[j]>piv){j--;}if(i>j)break;swap(nums[i],nums[j]);i++,j--;}int p=j;swap(nums[p],nums[left]);quicksort(nums,left,p-1);quicksort(nums,p+1,right);
}
};
我们的quicksort更健壮了
三、要求稳定排序
快速排序是不稳定的，稳定排序请看归并排序
Quick Select
主要场景是寻找第 k 大的元素或者求中位数
不难理解、求第 k 大可以转化为求第 n - k 小 ( n为元素总数 )
在快排中
当我们确定了 piv 的位置后可以知道 ：piv是第p小元素
这时我们比较 p 与 k
这里是找第 k 小
p==k返回nums[p]p > k去左侧找[ left, p-1]p < k去右侧找[ p-1, right]
时间复杂度理想情况可以达到惊人的O(n)
leetcode 215
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand((unsigned)time(NULL));int n=nums.size();return findk(nums,n-k,0,n-1);}int findk(vector<int>&nums,int k,int left,int right){if(left>=right)return nums[left];swap(nums[left],nums[left+rand()%(right-left+1)]);int piv=nums[left];int i=left+1,j=right;while(1){while(i<=j&&nums[i]<piv)i++;while(i<=j&&nums[j]>piv)j--;if(i>j)break;swap(nums[i],nums[j]);i++,j--;}int p=j;swap(nums[left],nums[p]);if(p==k)return nums[p];else if(p<k)return findk(nums,k,p+1,right);else return findk(nums,k,left,p-1);}
};