希爾排序（C語言實現）

希爾排序算法的C語言實現示例推薦度：
相關推薦

希爾排序（C語言實現）

　　導語：C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言。下面我們來看看希爾排序（C語言實現），希望對大家有所幫助。

　　希爾排序的基本思想是：先將整個待排序列分割成若干子序列分別進行進行直接插入排序，等到整個待排序列基本有序時，再對全體記錄依次進行直接插入排序。希爾排序也叫縮小增量排序，是1959年由D.L.Shell提出來的。

　　希爾排序的具體實現方法和步驟：

　　a、選擇一個步長序列d1，d2，d3，...，dk，其中，di > dj，dk = 1;

　　b、按步長序列個數K對序列進行K趟排序

　　c、每趟排序，根據對應的步長di進行分組，即將待排序的記錄序列所有距離為di的記錄放在同一組中，如此可將待排序列分割成若干個長度為m的子序列，分別對各組進行直接插入排序。當dk=1時，整個序列作為一個表來處理，表長度即為整個序列的長度，整個排序結束。

　　具體的希爾排序函數實現如下(按照逐漸遞增來進行排序)：

　　/* 希爾排序算法的簡單實現

　　* array[] : 要排序的數組

　　* length : 要排序的數組的長度

　　* d[] : 增量值數組

　　* number : 增量值個數

　　void shell_sort(int array[], int length, int d[], int number)

　　{

　　int i, j, k, m;

　　int span; // 用于存放具體增量的數值

　　int temp; // 用于存放臨時的待排序元素的值

　　for(m = 0; m < number; m++)

　　{

　　span = d[m]; // 獲取增量值

　　for(k = 0; k < span; k++)

　　{

　　for(i = k; i < length-1; i += span)

　　{

　　temp = array[i + 1];

　　j = i;

　　while((j > -1) && (temp < array[j]))

　　{

　　array[j + 1] = array[j];

　　j--;

　　}

　　array[j + 1] = temp;

　　}

　　測試函數的實現如下：

　　/* 程序的入口函數 */

　　int main()

　　{

　　int a[ARRAY_LENGTH];

　　int i;

　　int d[3] = {5, 3, 1}; // 定義一個表示增量值的數組

　　/* 輸入10個整形元素 */

　　printf("Input %d numbers : ", ARRAY_LENGTH);

　　for(i = 0; i < ARRAY_LENGTH; i++)

　　{

　　scanf("%d", &a[i]);

　　}

　　printf("**************************************************************** ");

　　/* 把排序前元素都打印出來 */

　　printf("The elements before sort is : ");

　　for(i = 0; i< ARRAY_LENGTH; i++)

　　{

　　printf("%d ", a[i]);

　　}

　　printf(" ");

　　printf("**************************************************************** ");

　　/* 對元素進行有小到大的直接插入排序 */

　　shell_sort(a, ARRAY_LENGTH, d, sizeof(d)/sizeof(d[0]));

　　/* 把排序后元素都打印出來 */

　　printf("The elements after sort is : ");

　　for(i = 0; i < ARRAY_LENGTH; i++)

　　{

　　printf("%d ", a[i]);

　　}

　　printf(" ");

　　return 0;

　　}

【希爾排序C語言實現】相關文章：

排序之一：直接插入排序（C語言實現）09-25