插入排序——直接插入排序和希爾排序

常見的比較排序算法有插入排序（直接插入排序和希爾排序），選擇排序（選擇排序和堆排序），交換排序（冒泡排序和快速排序），歸并排序。

還有非比較排序：基數排序和計數排序。

本文講講插入排序中的直接插入排序和希爾排序。

直接插入排序

如圖所示是我們直接插入排序的算法思想，我們可以看到它的時間複雜度為O（N的平方）。

代碼實作：

void InsertSort(int *a,size_t n)
{
    assert(a);
    for (size_t i = ; i<n - ; ++i)
    {
        int end = i;
        int tmp = a[end + ];
        while ( end>= )
        {
            if (a[end] > tmp)
            {
                a[end + ] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + ] = tmp;
    }
}
           

希爾排序：希爾排序可以說的直接插入排序的一種優化，他大緻分為兩步：預排序，直接插入排序。

上圖就是希爾排序的算法思想，通常我們gap的取值是數組大小的三分之一加1，為什麼加1呢，因為我們要保證gap>=1。也就是說gap至少有一個元素。

代碼實作：

void ShellSort(int* a, size_t n)
{
    assert(a);
    //1，預排序  2，

    int gap = n;
    while (gap > )
    {
        gap = gap /  + ;
        for (size_t i = ; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= )
            {
                if (a[end]>tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
                a[end + gap] = tmp;
            }
        }
    }
}