希尔排序

希尔排序

众所周知，在直接插入排序的算法中，每次只能插入一个数，使有序列每次只能增加一个节点，而且对后面的数没有任何的帮助，如果比较足够多的数据，将会产生足够大的时间复杂度。希尔排序则是对直接插入排序的一种改进优化，使相隔较远（一个增量）的数进行比较，
则进行一次比较就可以交换多组数据。
算法思想：
（1）.首先将待排序数据按某个增量h分为若干组，每组中记录其下标相差d;
（2）.对每个组中的数据进行排序；
（3）.然后缩小增量h，重复（1）（2）中的做法；
（4）.当增量缩小为一时，代表所有的数都被分为一组，即排序完成；

例如a[8]={7, 9, 0, 6, 7, 2, 3, 10};
数组中有八个数，我们可以初次取序列大小的一半为其增量（以后增量减半，直到增量为一），
即h=8/2=3;即分为下标差为4的4个组，让这4各组从小到大分别进行比较，按照要求进行交换，第一趟比较交换完成后，缩小其增量h=h/2(注意这里是之前增量的一半)=2;重复上面的操作，直到增量h减为1，排序完成，停止操作。

以下为代码演示，仅供参考。

RLSI(@_OMRJNL33CI8A$N_9.png 

代码

#include <stdio.h>

void shell_sort(int *x, int n)
{
    int h, j, k, t;
    for(h=n/2;h>0;h=h/2)
    {
        for(j=h;j<n;j++)
        {
            t=*(x+j);
            for(k=j-h;(k>=0&&t<*(x+k));k-=h)
            {
                *(x+k+h)=*(x+k);
            }
            *(x+k+h)=t;
        }
    }
}

int main()
{
    int n, num[8]={7, 9, 0, 6, 7, 2, 3, 10};
    for(int i=0;i<8;i++)
        printf("%d ", *(num+i));
    printf("\n");
    shell_sort(num, 8);
    for(int i=0;i<8;i++)
        printf("%d ", *(num+i));
}

总结

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序会比直接插入排序时间复杂度o(n^2)好一些。