平均时间O(NlogN)，最坏O(N^2)

 

主要过程四步：

1 如果S中元素为1 或者 0 ，直接返回

2 取S中的任一元素v，称为 枢纽元

3 将集合按照 枢纽元大小 分成两个集合

4 两个子集合递归调用2 - 3

 

选取枢纽元方法：

1错误方法：直接选取第一个

2安全方法: 随即选取一个枢纽元

3三数中值分割法：选取数组的中值

主要代码：

1 #include 
     
        2 #include 
      
         3 using namespace std;  4 template 
       
          5 void quicksort( vector
        
          & a)  6 {  7     quicksort(a,0,a.size()-1);  8 }  9 template 
         
           10 const Comparable & median3(vector
          
            & a,int left,int right) 11 { 12 int center = (left + right)/2; 13 if(a[center] < a[left]) 14 swap(a[left],a[center]); 15 if(a[right] < a[left]) 16 swap(a[left],a[right]); 17 if(a[right] < a[center]) 18 swap(a[center],a[right]); 19 20 swap(a[center],a[right - 1]); 21 return a[right-1]; 22 } 23 template 
           
             24 void quicksort( vector
            
              & a,int left,int right) 25 { 26 if(left + 10 <= right) 27 { 28 Comparable pivot = median3(a,left,right); 29 30 int i=left,j=right-1; 31 for( ; ; ) 32 { 33 while(a[++i] < pivot){} 34 while(pivot < a[--j]){} 35 if(i
             
               48 void insertionSort(vector
              
                & a) 49 { 50 int j; 51 for(int p = 1;p
               
                0 && tmp
                
                  60 void insertionSort(const Iterator & begin,const Iterator & end,Comparator lessThan) 61 { 62 if(begin != end) 63 insertionSort(begin,end,lessThan,*begin); 64 } 65 template 
                 
                   66 void insertionSort(const Iterator & begin, const Iterator & end , Comparator lessThan,const Object & obj) 67 { 68 Iterator j; 69 for(Iterator p =begin+1;p != end;++p) 70 { 71 Object tmp = *p; 72 for(j=p; j!=begin && lessThan(tmp,*(j-1)); --j) 73 *j = *(j-1); 74 *j = tmp; 75 } 76 }*/ 77 int main() 78 { 79 vector
                  
                    ivec; 80 ivec.push_back(1); 81 ivec.push_back(9); 82 ivec.push_back(2); 83 ivec.push_back(10); 84 ivec.push_back(3); 85 ivec.push_back(11); 86 ivec.push_back(4); 87 ivec.push_back(12); 88 ivec.push_back(5); 89 ivec.push_back(13); 90 ivec.push_back(6); 91 ivec.push_back(14); 92 ivec.push_back(7); 93 ivec.push_back(15); 94 ivec.push_back(8); 95 ivec.push_back(16); 96 quicksort(ivec); 97 for(int j = 0;j
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

代码执行中，因为没有insertionSort，所以暂时执行不了，insertionSort是插入排序，这样可以减少时间的消耗。