1 #include
      
        2 #include
       
         3 using namespace std; 4 void QSort(int*p, int left,int right) 5 { 6     if(left>=right) 7         return; 8     int i,j; 9     int key=p[left];10     i=left;11     j=right;12     while(i
        
         =key)15             j--;16         p[i]=p[j];17         while(i
         
          <=key)18             i++;19         p[j]=p[i];        20     }21     p[i]=key;22     QSort(p,left,i-1);23     QSort(p,i+1,right);24 }25 26 void QuickSort(int* p,int left,int right)27 {28     //QSort(p,left,right);29     stack
          
            is;30     is.push(left);31     is.push(right);32     while(!is.empty())33     {34         int j=is.top();is.pop();35         int i=is.top();is.pop();36         right=j;37         left=i;38         if(i>=j)39             continue;40         int key=p[i];41         while(i
           
            =key)44 j--;45 p[i]=p[j];46 while(i
            
             <=key)47 i++;48 p[j]=p[i];49 }50 p[i]=key;51 is.push(left);is.push(i-1); 52 is.push(i+1);is.push(right);53 }54 }55 int main()56 {57 int a[]={ 5,1,2,0,6,9,4};58 QuickSort(a,0,6);59 for(int i=0;i<7;i++)60 printf("%d ",a[i]);61 return 0;62 }
            
           
          
         
        
       
      

其实递归是一种栈的表达。

就像树本质上是一种递归结构。要抓住本质。

合理选取枢纽元的快排程序（比上面的快排平均要快5%），以及当数组元素个数小于等于3时用插入排序进行。

1 void  Qsort(int A[], int Left, int Right )  2 {    3     int  i, j;  4     int Pivot;  5     int Cutoff=3; 6     if(Left<=Right-Cutoff) //为什么不用Left+Cutoff<=Right ? 考虑溢出处理 7     {  /* if the sequence is not too short */ 8         Pivot = Median3(A,Left,Right);  /* select pivot */ 9         i = Left+1;     10         j = Right – 2; 11         for(;;) 12         { 13          while (i
      
       = Pivot ) {j--;}  /* scan from right */15          if (i
       
         A[ Center ] ) 33         swap(A[ Left ],A[ Center ] ); 34     if ( A[ Left ] > A[ Right ] ) 35         swap(A[ Left ], A[ Right ] ); 36     if ( A[ Center ] > A[ Right ] ) 37         swap( A[ Center ], A[ Right ] ); 38     /* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */ 39     swap(A[ Center ], A[ Right - 1 ] ); /* Hide pivot */ 40     /* only need to sort A[ Left + 1 ] … A[ Right – 2 ] */41     return  A[ Right - 1 ];  /* Return pivot */ 42 }