快速排序的一次划分代码如下
int divide(int A[],int left,int right) { int middle = A[left]; while(left<right) { while(left<right&&A[right]>=middle) right--; A[left]=A[right]; while(left<right&&A[left]<=middle) left++; A[right]=A[left]; } A[left]=middle; return left; }
//另一种写法
int divide(vector<int>& nums, int left, int right){
//以最右边为分隔值
int cnt = left;
while(left<right){
if(nums[left]<nums[right]){
//比分隔值小的,依次放到左边排列
swap(nums[left],nums[cnt++]);
}
left++;
}
swap(nums[cnt],nums[right]);
return cnt;
}
调用函数
void quick_sort(int a[],int left,int right) { if(left<right) { int mid=divide(a,left,right); quick_sort(a,left,mid-1); quick_sort(a,mid+1,right); } }
主函数中使用 quick_sort(A,0,n-1);即可完成排序
错误分析
错误1
int divide(vector<int>& nums, int left, int right){ //以最右边为分隔值 int cnt = left; while(left<right){ //下标相同就不用交换了 if(nums[left]<nums[right]&&left!=cnt){ //错误,原本是想优化下标相同的时候不交换,但是内部的cnt++就被短路了,不执行 //比分隔值小的,依次放到左边排列 swap(nums[left],nums[cnt++]); } left++; } swap(nums[cnt],nums[right]); return cnt; }
错误2 int divide(vector<int>& nums, int left, int right){ //以最右边为分隔值 int cnt = left; while(left<right){ if(nums[left]<nums[right]&&left++!=cnt){ //错误,条件与,如果前面nums[left]<nums[right]语句为false,则后面的left++被短路,而left++是必须执行的,造成死循环,超出时间限制 //比分隔值小的,依次放到左边排列 swap(nums[left],nums[cnt++]); } } swap(nums[cnt],nums[right]); return cnt; }
原文链接: https://www.cnblogs.com/lxzbky/p/12493650.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/400059
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!