1 #include <iostream> 2   3 using namespace std; 4   5 void Qsort(int a[], int low, int high) 6 { 7     if(low >= high) 8         return; 9     int first = low;10     int last = high;11     int key = a[first];12     while(first < last)13     {14         while(first < last && a[last] >= key)15             --last;16         a[first] = a[last];17         while(first < last && a[first] <= key)18             ++first;19          a[last] = a[first];20     }21     a[first] = key;22     Qsort(a, low, first-1);23     Qsort(a, first+1, high);24 }

 1 template <typename T> 2 void MergeSort (T data[], int size) 3 { 4     if ( size>1 ) 5     { 6         //预处理 7         int mid=size/2; 8         int numOfleft=mid; 9         int numOfright=size-mid;10         T* left=new T[numOfleft];11         T* right=new T[numOfright];12         //分13         std::copy(data, data+numOfleft, left);14         std::copy(data+numOfleft, data+size, right);15         MergeSort(left, numOfleft);16         MergeSort(right, numOfright);17         //合18         std::merge(left, left+numOfleft, right, right+numOfright, data);19         //清理20         delete[] left;21         delete[] right;22     }23 }

 1 template <typename T> 2 void heap_down (T data[], int i, const int& size) 3 { 4     int p=i*2+1; 5     while ( p<size ) 6     { 7         if ( p+1<size ) 8         { 9             if ( data[p]<data[p+1] )10                 ++p;11         }12         if ( data[i]<data[p] )13         {14             std::swap(data[p], data[i]);15             i=p;16             p=i*2+1;17         }18         else19             break;20     }21 }

 1 template <typename T> 2 void HeapSort (T data[], int size) 3 { 4     int i; 5     for (i=(size-1)/2; i>=0; --i) 6         heap_down(data, i, size); 7     for (i=size-1; i>0; --i) 8     { 9         std::swap(data[0], data[i]);10         heap_down(data, 0, i);11     }12 }