排序算法之希爾排序（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)。