三路划分的快速排序算法的一种更复杂的娱乐实现

该算法就是将待排序序列划分为左中右三部分,左半部分小于枢轴，中间部分等于枢轴，右半部分小于枢轴

再对左半部分和右半部分递归调用算法，这样避免了相等的数值在快速排序中引入的比较开销

以下算法实现较为复杂，没什么参考价值，纯属娱乐。实践中还是应当使用以荷兰国旗问题解决思路为指导思想的划分算法，源代码在互联网上很容易找到

娱乐代码如下(C++编写)

#include"stdafx.h"#include<vector>#include<algorithm>#include<iostream>usingnamespacestd;typedefinttype;voidlmove(vector<type>&list,type left,type p,type&i)//将左侧与基准元素相等的元素移至中间{type temp=i;type k=left;while(k<=p){swap(list[k],list[i]);++k;--i;if(i==p){i=temp-p-1+left;break;}}}voidrmove(vector<type>&list,type right,type q,type&j)//将右侧与基准元素相等的元素移至中间{type temp=j;type k=right;while(k>=q){swap(list[k],list[j]);--k;++j;if(j==q){j=3*q-temp-right+1;break;}}}voidquicksort(vector<type>&list,type left,type right)//三路划分的快速排序算法{if(left>=right)return;type p=left-1;type i=left-1;type q=right;type j=right;intpv=list[right];while(1){if(!(i==p&&p==left-1)){if(j-i==1){if(i==p&&p!=left-1){++i;}else{--j;}break;}}type tempi=i;if((i==p&&p!=left-1)||(i==p&&p==left-1)){++i;}while(list[i]<pv){++i;if(i==j)break;}if(i==j)break;if(i+1==j){if(list[i]==pv){if(tempi!=p&&j==q){--j;--q;break;}else{if(j+1==q){swap(list[i],list[j]);--j;--q;break;}else{--q;swap(list[i],list[q]);--j;break;}}}else{--j;break;}}type tempj=j;if((tempi!=p&&tempj==q)||(tempi==p&&p==left-1))--j;while(list[j]>pv){--j;if(i==j)break;}if(i==j){if(list[i]==pv){if(tempi!=p&&tempj==q){if(i+2==q){swap(list[i],list[j+1]);--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 tempp=p;if(list[i]==pv){if(tempi==p){if(p+1==i){++p;}else{++p;swap(list[i],list[p]);}}else{++p;swap(list[i],list[p]);}}if(list[j]==pv){if((tempi!=tempp&&tempj==q)||tempi==tempp&&(tempp==left-1||(tempp!=left-1&&tempj==q))){if(j+1==q){--q;}else{--q;swap(list[j],list[q]);}}else{--q;swap(list[j],list[q]);}}}}if(q-p<=1)return;else{if(p!=left-1){if(i==p){i=left-1;++j;rmove(list,right,q,j);}else{if(i==q){j=right+1;--i;lmove(list,left,p,i);}else{if(list[i]<pv){lmove(list,left,p,i);if(j+1==q){j=right+1;}else{++j;rmove(list,right,q,j);}}else{rmove(list,right,q,j);if(i-1==p){i=left-1;}else{--i;lmove(list,left,p,i);}}}}}else{if(i==q){--i;j=right+1;}else{if(list[i]<pv){if(j+1==q){j=right+1;}else{++j;rmove(list,right,q,j);}}else{rmove(list,right,q,j);if(i-1==p){i=left-1;}else{--i;}}}}}quicksort(list,left,i);quicksort(list,j,right);}intmain(){vector<type>list{2,23,6,8,5,25,19,17,25,23,18,13,25,16,23,1,9};cout<<"排序前:";for(consttype&m:list){cout<<m<<" ";}cout<<endl;quicksort(list,0,list.size()-1);cout<<"排序后:";for(consttype&m:list){cout<<m<<" ";}cout<<endl;return0;}