- 相關(guān)推薦
希爾排序（C語(yǔ)言實(shí)現(xiàn)）
導(dǎo)語(yǔ)：C語(yǔ)言的設(shè)計(jì)目標(biāo)是提供一種能以簡(jiǎn)易的方式編譯、處理低級(jí)存儲(chǔ)器、產(chǎn)生少量的機(jī)器碼以及不需要任何運(yùn)行環(huán)境支持便能運(yùn)行的編程語(yǔ)言。下面我們來(lái)看看希爾排序（C語(yǔ)言實(shí)現(xiàn)），希望對(duì)大家有所幫助。
希爾排序的基本思想是：先將整個(gè)待排序列分割成若干子序列分別進(jìn)行進(jìn)行直接插入排序，等到整個(gè)待排序列基本有序時(shí)，再對(duì)全體記錄依次進(jìn)行直接插入排序。希爾排序也叫縮小增量排序，是1959年由D.L.Shell提出來(lái)的。
希爾排序的具體實(shí)現(xiàn)方法和步驟：
a、選擇一個(gè)步長(zhǎng)序列d1，d2，d3，...，dk，其中，di > dj，dk = 1;
b、按步長(zhǎng)序列個(gè)數(shù)K對(duì)序列進(jìn)行K趟排序
c、每趟排序，根據(jù)對(duì)應(yīng)的步長(zhǎng)di進(jìn)行分組，即將待排序的記錄序列所有距離為di的記錄放在同一組中，如此可將待排序列分割成若干個(gè)長(zhǎng)度為m的子序列，分別對(duì)各組進(jìn)行直接插入排序。當(dāng)dk=1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度，整個(gè)排序結(jié)束。
具體的希爾排序函數(shù)實(shí)現(xiàn)如下(按照逐漸遞增來(lái)進(jìn)行排序)：
/* 希爾排序算法的簡(jiǎn)單實(shí)現(xiàn)
* array[] : 要排序的數(shù)組
* length : 要排序的數(shù)組的長(zhǎng)度
* d[] : 增量值數(shù)組
* number : 增量值個(gè)數(shù)
*/
void shell_sort(int array[], int length, int d[], int number)
{
int i, j, k, m;
int span; // 用于存放具體增量的數(shù)值
int temp; // 用于存放臨時(shí)的待排序元素的值
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;
}
}
}
}
測(cè)試函數(shù)的實(shí)現(xiàn)如下：
/* 程序的入口函數(shù) */
int main()
{
int a[ARRAY_LENGTH];
int i;
int d[3] = {5, 3, 1}; // 定義一個(gè)表示增量值的數(shù)組
/* 輸入10個(gè)整形元素 */
printf("Input %d numbers : ", ARRAY_LENGTH);
for(i = 0; i < ARRAY_LENGTH; i++)
{
scanf("%d", &a[i]);
}
printf("**************************************************************** ");
/* 把排序前元素都打印出來(lái) */
printf("The elements before sort is : ");
for(i = 0; i< ARRAY_LENGTH; i++)
{
printf("%d ", a[i]);
}
printf(" ");
printf("**************************************************************** ");
/* 對(duì)元素進(jìn)行有小到大的直接插入排序 */
shell_sort(a, ARRAY_LENGTH, d, sizeof(d)/sizeof(d[0]));
/* 把排序后元素都打印出來(lái) */
printf("The elements after sort is : ");
for(i = 0; i < ARRAY_LENGTH; i++)
{
printf("%d ", a[i]);
}
printf(" ");
return 0;
}
【希爾排序C語(yǔ)言實(shí)現(xiàn)】相關(guān)文章：
C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例09-18
C語(yǔ)言經(jīng)典冒泡排序法09-24
經(jīng)典c語(yǔ)言冒泡排序法08-08
C語(yǔ)言的冒泡排序方法08-22
希爾排序是什么09-20
C語(yǔ)言的HashTable簡(jiǎn)單實(shí)現(xiàn)10-12
C語(yǔ)言快速排序?qū)嵗a06-04
C語(yǔ)言冒泡排序算法實(shí)例06-15