“希尔排序”编码详解

（准备工作）希尔排序是插入排序的升级版，本质还是插入排序，因此就少不了数据在数组中的移动。

比如在长度为三的数组中想把2插到1和3的中间，首先应该把3右移一个位置好给2腾出空间，然后把2插到1和3的中间。

因此，希尔排序至少应该留有一个预备位置好让元素可以在不丢失数据的情况下实现位置的移动。

在程序中的体现就是设置一个变量保存要被别的数据占位的数据，可以是一个单独的变量设置成temp（标识符名称自己定）。

然后是一个存储多个数据的数组。

开始：

有了数组之后先确定最初的步长（主要是总长度的二分之一或者三分之一），即确定以步长为间隔的数据组成的集合。

先在这个集合里面用插入排序的方式将数据排列好。

然后缩小步长（一般为原步长的二分之一，跟原步长的设定方式一样就行。），

同样用插入排序的方式将数据排列好，直到步长为1。

详细编码描述：

先输入10个数据：69  56  12  136  3  55  47  98  88  23  

1、确定步长为5

2、判断步长是否大于等于1，如果大于等于1，跳到步骤3，如果小于1，跳到步骤5

3、依次对根据步长确定的集合按照插入排序的方式进行排序

4、将步长重新设定，跳到步骤2

5、输出排序后的结果，算法结束

插入排序的详细编码：（升序排序）

0、i=2;

1、如果  i  的值小于等于数据的个数，则将这个集合中的第i个数存放到temp变量中，跳转到步骤2；否则即是排序完成，终止循环

2、比较temp和第(i-1)个数的大小，如果(i-1)大于等于1并且temp小于第(i-1)个数，跳转到步骤3,否则跳转到步骤4

3、将第(i-1)个数右移一位，空出第(i-1)个位置,跳转到步骤2

4、将temp的值填充到空出的那个位置上面。

5、i++，跳转到步骤1

将上述两个算法步骤结合到一起的时候要注意，上面步骤三是分出了多个数据集合的，

因此，该步骤需要重复使用下面插入排序的步骤，因此会出现三层循环的现象。

一般的三层循环时间复杂度是O(n^3)，不推荐使用三层循环编程，一般编程最多到O(n^2)

但是这道题的三层循环的时间复杂度并不是O(n^3),而是在O(n*logn)和O(n^2)之间，

是满足小于O(n^2)的，甚至比插入排序还要好一些，因此可以应对一般的情况。

但是各种不同排序之间的优劣在这里讲的还比较少，可以去搜索各种不同排序方法的使用条件。

但是这里有一个需要关注的就是三层循环出现不一定就会使时间复杂度变成O(n^3)，

而且有的二层循环的时间复杂度不一定就是O(n^2),

现在暂时先写到这里，有兴趣的时候可以多了解一下降低时间复杂度的各种方法。

下面是希尔排序的具体实现：

#include <stdio.h>

void shellSort(int a[],int n)
{
    int temp;
    int d=n/2;
    while(d>=1)
    {
        for(int i=d;i<n;i++)
        {
            temp=a[i];
            int j=i-d;
            while(j>=0&&temp<a[j])
            {
                a[j+d]=a[j];
                j=j-d;
            }
            a[j+d]=temp;
        }
        d=d/2;
    }
}

void main()
{
    int a[10];
    printf("请输入需要排序的十个整型数据\n");
    for(int i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    shellSort(a,10);
    for(int j=0;j<10;j++)
    {
        printf("%d \t",a[j]);
    }
    printf("\n");
}