该算法就是将待排序序列划分为左中右三部分,左半部分小于枢轴中间部分等于枢轴右半部分小于枢轴再对左半部分和右半部分递归调用算法这样避免了相等的数值在快速排序中引入的比较开销以下算法实现较为复杂没什么参考价值纯属娱乐。实践中还是应当使用以荷兰国旗问题解决思路为指导思想的划分算法源代码在互联网上很容易找到娱乐代码如下(C编写)#includestdafx.h#includevector#includealgorithm#includeiostreamusingnamespacestd;typedefinttype;voidlmove(vectortypelist,type left,type p,typei)//将左侧与基准元素相等的元素移至中间{type tempi;type kleft;while(kp){swap(list[k],list[i]);k;--i;if(ip){itemp-p-1left;break;}}}voidrmove(vectortypelist,type right,type q,typej)//将右侧与基准元素相等的元素移至中间{type tempj;type kright;while(kq){swap(list[k],list[j]);--k;j;if(jq){j3*q-temp-right1;break;}}}voidquicksort(vectortypelist,type left,type right)//三路划分的快速排序算法{if(leftright)return;type pleft-1;type ileft-1;type qright;type jright;intpvlist[right];while(1){if(!(ippleft-1)){if(j-i1){if(ipp!left-1){i;}else{--j;}break;}}type tempii;if((ipp!left-1)||(ippleft-1)){i;}while(list[i]pv){i;if(ij)break;}if(ij)break;if(i1j){if(list[i]pv){if(tempi!pjq){--j;--q;break;}else{if(j1q){swap(list[i],list[j]);--j;--q;break;}else{--q;swap(list[i],list[q]);--j;break;}}}else{--j;break;}}type tempjj;if((tempi!ptempjq)||(tempippleft-1))--j;while(list[j]pv){--j;if(ij)break;}if(ij){if(list[i]pv){if(tempi!ptempjq){if(i2q){swap(list[i],list[j1]);--q;break;}else{--q;swap(list[q],list[i]);break;}}else{--q;swap(list[q],list[i]);break;}}else{break;}}else{swap(list[i],list[j]);type temppp;if(list[i]pv){if(tempip){if(p1i){p;}else{p;swap(list[i],list[p]);}}else{p;swap(list[i],list[p]);}}if(list[j]pv){if((tempi!tempptempjq)||tempitempp(temppleft-1||(tempp!left-1tempjq))){if(j1q){--q;}else{--q;swap(list[j],list[q]);}}else{--q;swap(list[j],list[q]);}}}}if(q-p1)return;else{if(p!left-1){if(ip){ileft-1;j;rmove(list,right,q,j);}else{if(iq){jright1;--i;lmove(list,left,p,i);}else{if(list[i]pv){lmove(list,left,p,i);if(j1q){jright1;}else{j;rmove(list,right,q,j);}}else{rmove(list,right,q,j);if(i-1p){ileft-1;}else{--i;lmove(list,left,p,i);}}}}}else{if(iq){--i;jright1;}else{if(list[i]pv){if(j1q){jright1;}else{j;rmove(list,right,q,j);}}else{rmove(list,right,q,j);if(i-1p){ileft-1;}else{--i;}}}}}quicksort(list,left,i);quicksort(list,j,right);}intmain(){vectortypelist{2,23,6,8,5,25,19,17,25,23,18,13,25,16,23,1,9};cout排序前:;for(consttypem:list){coutm ;}coutendl;quicksort(list,0,list.size()-1);cout排序后:;for(consttypem:list){coutm ;}coutendl;return0;}
