//quick sort//STL中也有现成的高速排序算法。内部实现採用了下面技巧//1）枢轴的选择採取三数取中的方式//2）后半段採取循环的方式实现//3）高速排序与插入排序结合#include
     
      #include
      
       #include
       
        using namespace std;//这一版本号是最简单实现版本号。对于高速排序的优化主要有下面几个方面：//1）枢轴的选择。若枢轴选取不全适。比方，若每次递归时，两个子区间中的一个为空，则高速排序将退化为冒泡排序//关于枢轴的选择有多种：取最后一个元素、取第一个元素、三数取中、九数取中、随机值等//2）还有一方面是对迭代过程的优化。降低交换次数，降低递归深度等；template
        
         int partion1(vector
         
          & vec,int start,int end){//高速排序的核心部分	//取最后一个作为枢轴和第一个作为枢轴程序相似，下面是取最后一个元素作为枢轴	int key=vec[end];	int fast,slow;	fast=slow=start;	//用两个指针的移动实现	for(;fast
          
           int midNumber(type a,type b,type c){ int big1=max(a,b); int big2=max(a,c); int big3=max(b,c); return min(big1,min(big2,big3));}template
           
            int partion2(vector
            
             & vec,int start,int end){ //3数取中和9数取中的方式，保证了一定随机性，下面是3数取中的方式 int key=midNumber(vec[start],vec[(start+end)/2],vec[end]); int midNumPos=0; if(key==vec[start]) midNumPos=start; else if(key==vec[end]) midNumPos=end; else midNumPos=(start+end)/2; vec[midNumPos]=vec[end]; vec[end]=key; //如今採用一种和上一种方案不同的交换方式 while(start
             
              =key) end--; tmp=vec[start]; vec[start]=vec[end]; vec[end]=tmp; } return start;}template
              
               int partion3(vector
               
                & vec,int start,int end){//取随机数的方法 int keyNumPos=start+rand()%(end-start); int tmp=vec[keyNumPos]; vec[keyNumPos]=vec[end]; vec[end]=tmp; int key=vec[end]; while(start
                
                 =key) end--; tmp=vec[start]; vec[start]=vec[end]; vec[end]=tmp; } return start;}//以上是三种对枢轴的优化方法。无非就是避免高速排序恶化//下面是避免不必要的交换过程template
                 
                  int partion4(vector
                  
                   & vec,int start,int end){//取随机数的方法 int keyNumPos=start+rand()%(end-start); int tmp=vec[keyNumPos]; vec[keyNumPos]=vec[end]; vec[end]=tmp; int key=vec[end]; while(start
                   
                    =key) end--; vec[start]=vec[end];//start以end覆盖 } vec[start]=key; return start;}template
                    
                     void qSort1(vector
                     
                      & vec,int start,int end){ if(start>=end)return; int index=partion4(vec,start,end);//key qSort1(vec,start,index-1); qSort1(vec,index+1,end);}//递归过程须要出栈入栈，成本较高，并且可能栈溢出。假设可能的话最好以循环方式取代递归template
                      
                       void qSort2(vector
                       
                        & vec,int start,int end){ if(start>=end)return; int index;//key while(start
                        
                         void qSort3(vector
                         
                          & vec,int start,int end){ if(start>=end)return; int index;//key if(end-start>VALUE) { while(start
                          
                           void quickSort(vector
                           
                            & vec){ int length=vec.size(); qSort2(vec,0,length-1);}int main(){ int a[10]={1,5,9,0,6,3,2,7,8,4}; vector
                            
                              vec(a,a+10); quickSort(vec); for(int i=0;i