C++模板实现常用排序算法

本文利用模板实现通用性好的排序算法，包括冒泡排序，选择排序，直接插入排序，快速排序，堆排序，希尔排序，归并排序和桶排序，并且给出排序算法的比较。

#include 
#include 
#include 
using namespace std;


template  void BubbleSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;

    bool flag = false;
    for(auto i=0; i=i; --j){
     if(array[j+1] void SelectSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;

    for(auto i=0; i=0 && array[i] > tmp){
     array[i+1] = array[i];
     --i;
 }
 array[i+1] = tmp;
    }    
}


template  void QuickSort(T *array, int l, int r)
{   
    if(l=tmp) --j;
     if(i void QuickSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;
    QuickSort(array, 0, length-1);
}


template  void MaxHeapify(T *array, int i, int heapSize)
{
    int l = 2*i+1;
    int r = 2*i+2;
    int tmp = i;
    if(l<=heapSize && array[l]>array[i]){
 tmp = l;
    }else{
 tmp = i;
    }

    if(r<=heapSize && array[r]>array[tmp]){
 tmp = r;
    }

    if(tmp != i){
 swap(array[i], array[tmp]);
 MaxHeapify(array, tmp, heapSize);
    }

}
template  void HeapSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;
    for(auto i = length/2; i>=0; --i){ //构建最大堆
 MaxHeapify(array, i, length-1);
    }
    for(auto i = length-1; i>=0; --i){
 swap(array[0], array[i]);
 MaxHeapify(array, 0, i-1);
    }
}


template  void ShellSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;

    int gap = length/2;
    while(gap){
 T tmp;
 for(int i=gap; i=gap && tmp void Merge(T *array, int l, int mid, int r)
{
    T *tmp = new T[r-l+1];
    int i = l;
    int j = mid + 1;
    int k = 0;
    while(i<=mid && j<=r){
 if(array[i] void subSort(T *array, int l, int r)
{
    if(l void MergeSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;
    subSort(array, 0, length-1);
}



template  void BucketSort(T *array, const int length)
{
    if(array == NULL){ 
 throw invalid_argument("Array must not be empty");
    }   
    if(length<=0) 
 return;
    T maxV = array[0];
    for(int i=0; i maxV)
     maxV = array[i];
    }

    int tempArrLength = maxV+1;
    T tempArr[tempArrLength];
    for(int i=0; i
下表是个人对排序算法的总结: