希尔排序

希尔排序（Shell Sort）就是将原本有大量记录数的记录进行分组（将相距某个“增量”的记录组成一个子序列），此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，再对全体记录进行一次直接插入排序。

所谓基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像{2, 1, 3, 6, 4, 7, 5, 8, 9}这样可以称为基本有序了。但像{1, 5, 9, 3, 7, 8, 2, 4, 6}这样9在第三位，2在倒数第三位就谈不上基本有序了。

核心代码

void ShellSort(int arr[], int len)
{
    int j;
    int k;
    int nGap;
    int temp;

    assert(arr!=NULL && len>0);

    //定步长
    for(nGap=len/2; nGap>0; nGap/=2)
    {
        //根据步长进行分组
        //各组内进行插入排序
        for(j=nGap; j<len; ++j)
        {
            //有序数组的最后一个
            k = j-nGap;
            //无序数组的第一个
            temp = arr[j];

            while(temp<arr[k] && k >= 0)
            {
                arr[k+nGap] = arr[k];
                k -= nGap;
            }

            arr[k+nGap] = temp;
        }
    }
}

 算法分析：

　　最好时间复杂度：O(n)　　　　有序

　　平均时间复杂度：O(n^1.5)

　　最坏时间复杂度：O(n^2)

　　　　空间复杂度：O(1)

　　　　　　稳定性：不稳定

对于希尔排序，增量的选取是关键，但是这目前还是一个数学难题，不过大量的研究表明，当增量序列为dlta[k] = 2^(t-k+1)-1（0≤k≤log2(n+1)向下取整）时，可以获得不错的效果。注意：增量序列的最后一个增量必须等于1才行。