这段时间楼主在忙找工作的事情，必然要把数据结构和算法部分复习一下，抽空把几个经典的排序算法写了下，一方面练习一下，另一方面以后用到了就可以直接拿去了~

几点注意：

1.大部分都是按照《数据结构与算法分析》这本书上的例子写的

2.下面例子中的希尔排序并不是最优的

1 #include 
     
        2 #include 
      
         3   4 using namespace std;  5   6 /************************************************************************/  7 /* 将常用的排序算法总结如下：                                                                     */  8 /************************************************************************/  9  10 //1.插入排序 11 template 
       
         12 int InsertSort(T array[],int N) 13 { 14     if ( array == NULL || N == 0 ) 15         return 1; 16     T tmp; 17     int j; 18     for (int p=1;p
        
          0 && tmp < array[j - 1]; j --  ) 22         { 23             array[j] = array[j-1]; 24         } 25         array[j] = tmp; 26     } 27     return 0; 28 } 29  30 //2.希尔排序(n/2) 31 template 
         
           32 int ShellSort(T array[],int N) 33 { 34     T tmp; 35     int i,j,Increment; 36     for ( Increment = N/2; Increment>0; Increment/=2 ) 37     { 38         for (i=Increment;i
          
           =Increment && tmp < array[j-Increment];j-=Increment) 42 { 43 array[j] = array[j-Increment]; 44 } 45 array[j] = tmp; 46 } 47 } 48 return 0; 49 } 50 51 //交换例程 52 template 
           
             53 inline void swap(T *a, T *b) 54 { 55 T temp; 56 temp = *a; 57 *a = *b; 58 *b = temp; 59 } 60 61 //3.堆排序 62 #define LeftChild(i) (2*(i)+1) 63 template 
            
              64 void percdown(T array[], int i, int N) 65 { 66 int child; 67 T tmp = array[i]; 68 for (;LeftChild(i)
             
              array[child]) 72 child ++; 73 if (tmp
              
                81 void heapsort(T array[], int N) 82 { 83 int i; 84 for (i = N/2;i>=0;i--) 85 percdown(array,i,N); 86 for (i = N-1;i>0;i--) 87 { 88 swap(&array[0],&array[i]); 89 percdown(array,0,i); 90 } 91 } 92 93 //4.归并排序 94 template 
               
                 95 void Merge(T array[], T Tmparray[], int Lpos, int Rpos, int RightEnd) 96 { 97 int i,LeftEnd,NumElements,Tmppos; 98 LeftEnd = Rpos - 1; 99 Tmppos = Lpos;100 NumElements = RightEnd - Lpos + 1;101 102 while(Lpos<=LeftEnd && Rpos<=RightEnd)103 {104 if (array[Lpos]<=array[Rpos])105 Tmparray[Tmppos++] = array[Lpos++];106 else107 Tmparray[Tmppos++] = array[Rpos++];108 }109 while(Lpos<=LeftEnd)110 Tmparray[Tmppos++] = array[Lpos++];111 while(Rpos<=RightEnd)112 Tmparray[Tmppos++] = array[Rpos++];113 114 for (i=0;i
                
                 119 void Msort(T array[], T Tmparray[], int left, int right)120 {121 int center;122 if (left
                 
                  132 void Mergesort(T array[], int N)133 {134 T *Tmparray;135 Tmparray = new T[N];136 if (Tmparray!=NULL)137 {138 Msort(array,Tmparray,0,N-1);139 delete [] Tmparray;140 }141 else142 cout<<"error"<
                  
                   148 int qsort(T array[], int left, int right)149 {150 if(left >= right)151 return 0;152 T pivot = array[left];153 int i,j;154 i = left;155 j = right+1;156 for (;;)157 {158 while(array[++i]
                   
                    pivot){}160 if (i
                    
                     175 inline T median3(T array[], int left, int right)176 {177 int center = (left + right)/2;178 179 if (array[left]>array[center])180 swap(&array[left],&array[center]);181 if (array[left]>array[right])182 swap(&array[left],&array[right]);183 if (array[center]>array[right])184 swap(&array[center],&array[right]);185 186 swap(&array[center],&array[right-1]);187 return array[right-1];188 }189 190 #define Cutoff 3191 template 
                     
                      192 int qsortbest(T array[], int left, int right)193 {194 int i,j;195 T pivot;196 197 if (right - left >= Cutoff)198 {199 pivot = median3(array,left,right);200 i = left;201 j = right - 1;202 for (;;)203 {204 while(array[++i]
                      
                       pivot){}206 if (i
                       
                        >N;231 cout<<"\n输入排序方式："<<"\n1.插入排序\n2.希尔排序\n3.堆排序\n4.归并排序\n5.快速排序（编程珠玑）\n6.快速排序（优化）"<
                        
                         >chose;233 234 double tbegin,tend;235 236 srand((unsigned int)time(NULL));237 array = new int[N];238 for (int i=0;i