排序算法

//直接插入排序
template<class T>
void insertSort(T array[],int n)
{
    T temp;
    for(int i = 1; i < n ; i++)//循环，i表示插入的趟数，共进行n-1趟插入
    {
        temp = array[i];//将待插入元素赋给temp
        int j = i-1;
        while(j >= 0 && temp < array[j])//把比temp大的元素向后移
        {
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = temp;//j+1为temp的位置，将temp插入到这个位置
    }
}

//折半插入排序
void BianryInsertSort(int array[],int n){
    for(int i = 1; i < n; i++)//共进行n-1次插入
    {
       int left = 0, right = i-1, temp = array[i];//保存待插入数据
       while(left <= right)
       {
           int mid = (left + right)/2;//求出中心点
           if(temp < array[mid])//如果待插入数据比中心点元素小
           {
               right = mid - 1;//更新右区间的值
           }
           else
               left = mid + 1;//更新左区间的值
       }

       for(int j = i-1;j >= left; j--)//执行移动操作
           array[j+1] = array[j];

       array[left] = temp;//将待插入数据插入到有序表中
    }
}

//希尔排序（不稳定）
void ShellSort(int array[], 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)//对每一个子序列执行插入排序
            {
                int temp = array[i];
                int j = i-d;
                while(j>=k && array[j] > temp){
                    array[j+d] = array[j];
                    j-=d;
                }
                array[j+d] = temp;
            }
        }
        d = d/2;//增量为上次的一半
    }
}