一個關于快排的問題

做1306的sorting algorithm的時候
一開始寫的快排逾時了
然後用ilovenwd師兄提供了下面的快排才過了


你快排寫得不好.
試試一組 1000000 個0的資料.
參考一下下面這個

  
   
    
        
  
            
  
             
void quick_sort(int *a,int n) ...{

        
  
             
        int i=0, j=n-1;

        
  
             
        int x=a[n/2];

        
  
          
  
             
        while(i<=j) ...{

        
  
             
                while(a[i]<x) i++; //注意<不是<=

        
  
             
                while(a[j]>x) j--;

        
  
             
                if(i<=j) swap(a[i],a[j]), ++i, --j;

        
  
             
        }

        
  
             
        if(j>0) quick_sort(a,j+1);

        
  
             
        if(i<n-1) quick_sort(a+i, n-i);

        
  
             
}
   
  關鍵的不是左邊或間.
而是 那個<和<=的差別.
你去看一些比較好的算法書.比如Robert Sedgewick那本.有詳細分析.
如果你覺得取中間有可能O(n^2)就一開始就随機Shuffle一下.不過基本沒必要.
===============

  
   
    
        
  
             
void sort(int l,int r) 

        
  
          
  
             
...{ 

        
  
             
        int i,j,x,t; 

        
  
             
        i=l;j=r;x=a[(l+r)/2]; 

        
  
          
  
             
        do ...{

        
  
             
        while ((a[i]<x)&&(i<r)) i++; 

        
  
             
        while ((a[j]>x)&&(j>l)) j--; 

        
  
          
  
             
        if (i<=j) ...{t=a[i];a[i]=a[j];a[j]=t;i++;j--;} 

        
  
             
        } while (i<=j) ; 

        
  
             
        if(l<j) sort(l,j); 

        
  
             
        if(r>i) sort(i,r); 

        
  
             
}