希尔排序（C语言实现）

导语：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;

}