void Insertsort(int a[], int n)
{
    int i, j;
    int Tmp;
    for (i = 1; i < n; i++)//from the second element
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--){  //from the i-1 begin to compare until the first element
            Tmp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = Tmp;
        }
}
//The time complexity of the insertion sort is O(N2).

void shellsort(int a[], int n)
{
    int i, j, gap;
    int Tmp;

    for (gap = n / 2; gap > 0; gap /= 2)// an additional loop here
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap){
                Tmp = a[j];
                a[j] = a[j + gap];
                a[j + gap] = Tmp;
            }//modify the "1" to "gap"
}
//The insertion sort is the special situation in which the gap is 1

数据结构与算法——插入排序与希尔排序