導語:C語言的設計目標是提供一種能以簡易的方式編譯、處理低階儲存器、產生少量的機器碼以及不需要任何執行環境支援便能執行的程式語言。下面我們來看看希爾排序(C語言實現),希望對大家有所幫助。
希爾排序的基本思想是:先將整個待排序列分割成若干子序列分別進行進行直接插入排序,等到整個待排序列基本有序時,再對全體記錄依次進行直接插入排序。希爾排序也叫縮小增量排序,是1959年由l提出來的。
希爾排序的具體實現方法和步驟:
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;
}