排序算法之希尔排序（Shell‘s Sort）——C语言实现

希尔排序（Shell‘s Sort）又称“缩小增量排序”，它也是一种属插入排序类的 算法。

希尔排序的基本思想是：先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

思路分析

下面 来看一下图解（图片来源于网络图片原地址）

      从上图我们可以知道希尔排序需要一个增量序列来控制每一趟的分组，将分组中的元素进行排序，因此在最后一趟之前，较小的 记录是跳跃式地往前移，从而使得在进行最后一趟增量为1的插入排序中，序列已经基本有序，只需进行简单的移动便可以完成排序，这也是希尔排序较直接插入排序复杂度低的原因。

下面给出每一趟排序的代码：

void ShellInsert(int a[],int dk,int n)//dk为这一躺排序的增量
{
    int i,j;
    for(i=dk+1;i<=n;++i)
        {
            if(a[i]<a[i-dk])
            {
                a[0]=a[i];//暂存在a[0]中
                for(j=i-dk;j>0&&a[0]<a[j];j=j-dk)
                    a[j+dk]=a[j];//后移，寻找插入位置
                a[j+dk]=a[0];//插入
            }
        }
}
           

例子：当增量为2时的一次调整如下

调整之后为

代码如下

#include"malloc.h" /* malloc()等 */
#include"stdlib.h" /* exit() */
#include"stdio.h"
void ShellInsert(int a[],int dk,int n)
{
    int i,j;
    for(i=dk+1;i<=n;++i)
        {
            if(a[i]<a[i-dk])
            {
                a[0]=a[i];//暂存在a[0]中
                for(j=i-dk;j>0&&a[0]<a[j];j=j-dk)
                    a[j+dk]=a[j];//后移，寻找插入位置
                a[j+dk]=a[0];//插入
            }
        }
}
void ShellSort(int a[],int dlta[],int t,int n)
{
    int k,i;
    for(k=0;k<t;k++)
        {
            ShellInsert(a,dlta[k],n);//进行一趟排序
            for(i=1;i<=n;i++)
                printf("%d ",a[i]);
            printf("\n");//输出每一趟排序后的结果
        }
}
int main()
{
    int n,i,j,t=0;
    scanf("%d",&n);
    j=n;
    int a[n+1],dlta[n+1];
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=0;j>1;i++)
    {
        dlta[i]=j/2;
        j/=2;
        t++;
    }//利用dlta数组控制每一趟中比较的间隙
    ShellSort(a,dlta,t,n);
    return 0;
}
           

以上的代码当输入无序序列时，输出结果为每一趟的排序结果，当最后一趟时为递增序列。

分析

希尔排序的时间复杂度与增量序列的选取 直接相关，目前尚未有人求得一种最好的递增序列。有人指出，当增量序列取的某些 特定值时如Hibbard可使得最坏时间复杂度为O(n3/2)。