剖析插入排序

插入排序---直接插入排序
int a[10];
for(int i=1;i<10;i++){
if(a[i] < a[i-1])
{
    int j = i-1;
    int t = a[i];
    while(t<a[j] && j>=0)
    {
    a[j+1] = a[j];
    j--;
    }
    a[j+1] = x;
}
}
时间复杂度：T(n)=O(n^2)


插入排序---希尔排序


首先应当理解希尔排序算法：
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：


13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：


10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：


10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：


10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）。


void print(int a[], int n, int i)
{
    printf("%d:",i);
    for(int j=0; j<8; j++)
    {
    printf("%-3d",a[j]);
    }
}


void ShellInsertSort(int a[], int n, int dk)
{
    for(int i = dk; i<n; i++)
    {
    if(a[i] < a[i-dk])
    {
    int j = i-dk;
    int x = a[i];
    a[i] = a[i-dk];
    while(x < a[j] && j>=0)
    {
    a[j+dk] = a[j];
    j -=dk;
    }
    a[j+dk] = x;
    }
    print(a,n,i);
    }
}


void shellSort(int a[], int n)
{
    int dk = n/2;
    while( dk >=1 )
    {
    ShellInsertSort(a,n,dk);
    dk /= 2;
    }
}


int main()
{
    int a[8] = {3,4,2,1,5,3,1,9};
    shellSort(a,8);
    print(a,8,8);
}