C語言希爾排序演算法

2020-07-16 10:04:29
用希爾排序法對一組資料由小到大進行排序,資料分別為 69、56、12、136、3、55、46、 99、88、25。

實現過程:

(1)自定義函數 shsort(),實現希爾排序。

(2) main() 函數作為程式的入口函數。程式程式碼如下:
#include <stdio.h>
int shsort(int s[], int n)    /* 自定義函數 shsort()*/
{
    int i,j,d;
    d=n/2;    /*確定固定增雖值*/
    while(d>=1)
    {
        for(i=d+1;i<=n;i++)    /*陣列下標從d+1開始進行直接插入排序*/
        {
            s[0]=s[i];    /*設定監視哨*/
            j=i-d;    /*確定要進行比較的元素的最右邊位置*/
            while((j>0)&&(s[0]<s[j]))
            {
                s[j+d]=s[j];    /*資料右移*/
                j=j-d;    /*向左移d個位置V*/
            }
            s[j + d]=s[0];    /*在確定的位罝插入s[i]*/
        }
        d = d/2;    /*增裡變為原來的一半*/
    }
return 0;
}

int main()
{
    int a[11],i;    /*定義陣列及變數為基本整型*/
    printf("請輸入 10 個資料:n");
    for(i=1;i<=10;i++)
    scanf("%d",&a[i]);    /*從鍵盤中輸入10個資料*/
    shsort(a, 10);    /* 呼叫 shsort()函數*/
    printf("排序後的順序是:n");
    for(i=1;i<=10;i++)
    printf("%5d",a[i]);    /*輸出排序後的陣列*/
    printf("n");
    return 0;
}

執行結果:

請輸入 10 個資料:

69 56 12 136 3 55 46 99 88 25
排序後的順序是:
    3   12   25   46   55   56   69   88   99  136

技術要點:

希爾排序是在直接插入排序的基礎上做的改進,也就是將寒排序的序列按固定增量分成若干組,等距者在同二組中,然後再在組內進行直接插入排序。這裡面的固定增量從 n/2 開始,以後每次縮小到原來的一半。