- 快排利用标兵的思想，但每一次都是比较范围大小，没有精确排序。
- 同样适用于快速求解 需要定性的范围问题，例如：第k大(将前后定性大小，但不用排序).
- 求解第k大：通过判断下标，只计算有k的那一半。
- 快排是从广到窄的递归。
-
快排：a.枢轴要回归.b.i总是指向偏大的值.
void quick_sort(int *A,int x,int y)//左闭右闭 { if(x < y)//当有1或0个元素是退出 { int i = x; int j = y; //取中值，优化快排速度,优化效果明显，4%~5%。 int m = x + (y-x)/2; if(A[x] > A[m]) if(A[x] > A[y]) if(A[m] > A[y]) swap(A[m],A[y]); else swap(A[x],A[y]); else//A[x]<A[m] if(A[x] > A[y]) swap(A[x],A[y]); else if(A[y] > A[m]) swap(A[m],A[y]); //优化结束 int key = A[y]; while(true) { while(i < j && A[i] <= key)//因为先从左开始遍历，所以A[i]一定是偏大的值 ++i; while(i < j && A[j] >= key) --j; if(i < j) swap(A[i],A[j]); else break; ++i;//不能同时--j,否则会有bug。 } swap(A[i],A[y]);//将枢纽归位 quick_sort( A,x,i-1); quick_sort( A,i+1,y); } }
由 dawei
【声明】：北京站长网内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。