上学期写的关于排序的算法。最近抽空修正了原本的一些BUG加了注释，现在发出来。

#include<iostream>
#include<time.h>
#include<cstdlib>

using namespace std;

//直接插入排序
template<class T>
void InsertionSort(T Data[], int n){
    int p, i;
    for(p = 1; p < n; p++){
        T temp = Data[p];
        i = p-1;
        while( i>=0 && Data[i] > temp){
            Data[i+1] = Data[i];
            i--;
        }
        Data[i+1] = temp;
    }
}

//折半插入排序
template<class T>
void BinaryInsertionSort(T Data[], int n){
    int left, mid, right, p;
    for(p = 1; p < n; p++){
        T temp = Data[p];
        left = 0;
        right = p-1;
        while(left <= right){
            mid = (left + right)/2;
            if(Data[mid] > temp)
                right = mid - 1;
            else
                left = mid + 1;
        }
        for(int i = p-1; i>=left; i--)
            Data[i+1] = Data[i];
        Data[left] = temp;
    }
}

//希尔排序
template<class T>
void ShellSort(T Data[], int n){
    int d = n/2;
    while(d >= 1){
        for(int k = 0; k < d; k++){
            for(int i = k+d; i < n; i += d){
                T temp = Data[i];
                int j = i - d;
                while(j>=k && Data[j]>temp){
                    Data[j+d] = Data[j];
                    j -= d;
                }
                Data[j+d] = temp;
            }
        }
        d = d/2;
    }
}

//冒泡排序
template<typename T>
void BubbleSort(T Data[], int n){
    int flag = 0;
    for(int i = 0; i < n; i++){
        flag = 0;
        for(int j = 1; j < n-i; j++){
            if(Data[j] < Data[j-1]){
                flag = 1;
                swap(Data[j], Data[j-1]);
            }
        }
        if(!flag)
            return;
    }
}
template<class T>
void print(T Data[], int n){
    for(int i = 0; i < n; i++){
        cout<<Data[i]<<' ';
    }
    cout<<endl;
}

template<class T>
void cpy(T Data[], T temp[], int n){
    for(int i = 0; i < n; i++){
        Data[i] = temp[i];
    }
}

//实现对data[start]到data[end]的操作，并返回划分后轴元素对应的位置
template<class T>
int Partition(T Data[], int start, int end){
    T pivot = Data[start];
    int left = start,right = end;
    while(left <= right){
        while(left<=right && Data[left]<=pivot)
            left++;
        while(left<=right && Data[right]>pivot)
            right--;

        if(left<right){
            swap(Data[right], Data[left]);
            left++;
            right--;
        }
    }
    swap(Data[start], Data[right]);
    return right;
}

//快速排序
template<class T>
void QuickSort(T Data[], int left, int right){
    if(left < right){
        int p = Partition(Data, left, right);
        QuickSort(Data, left, p-1);
        QuickSort(Data, p+1, right);
    }
}

//简单选择排序
template<class T>
void SelectionSort(T Data[], int n){
    for(int i = 1; i < n; i++){
        int k = i-1;
        for(int j = i; j < n; j++){
            if(Data[j] < Data[k])
                k = j;
        }
        if(k != i-1){
            swap(Data[k], Data[i-1]);
        }
    }
}

//Data为待归并数组，其中对Data[start,mid]和Data[mid+1,end]之间的数据进行归并
template<class T>
void Merge(T Data[], int start, int mid, int end){
    int len1 = mid - start + 1, len2 = end - mid;
    int i, j, k;
    T * left = new T[len1];
    T * right = new T[len2];
    for(i = 0; i < len1; i++)
        left[i] = Data[i+start];
    for(i = 0; i < len2; i++)
        right[i] = Data[i+mid+1];
    i = 0;j = 0;
    for(k = start; k < end; k++){
        if(i == len1 || j == len2)
            break;
        if(left[i] <= right[j])
            Data[k] = left[i++];
        else
            Data[k] = right[j++];
    }
    while(i < len1)
        Data[k++] = left[i++];
    while(j < len2)
        Data[k++] = right[j++];

    delete [] left;
    delete [] right;
}

//归并排序
template<class T>
void MergeSort(T Data[], int start, int end){
    if(start < end){
        int mid = (start + end)/2;
        MergeSort(Data, start, mid);
        MergeSort(Data, mid+1, end);
        Merge(Data, start, mid, end);
    }
}

int main(){
    int arr[12], temp[12];
    srand(time(0));
    for(int i = 0; i < 12; i++){
        arr[i] = rand()%100;
    }
    for(int i = 0; i < 12; i++){
        temp[i] = arr[i];
    }
    cout<<"随机生成序列：";
    print<int>(arr, 12);

    InsertionSort<int>(arr, 12);
    cout<<"直接插入排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    BinaryInsertionSort<int>(arr, 12);
    cout<<"折半插入排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    ShellSort<int>(arr, 12);
    cout<<"希尔排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    BubbleSort<int>(arr, 12);
    cout<<"冒泡排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    QuickSort<int>(arr, 0, 11);
    cout<<"快速排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    SelectionSort<int>(arr, 12);
    cout<<"选择排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    MergeSort<int>(arr, 0, 11);
    cout<<"归并排序：";
    print<int>(arr, 12);
    cpy<int>(arr, temp, 12);

    return 0;
}