排序之二：希尔排序（C语言实现）

怼烎@ 2022-06-14 01:56 200阅读 0赞

希尔排序的基本思想是：先将整个待排序列分割成若干子序列分别进行进行直接插入排序，等到整个待排序列基本有序时，再对全体记录依次进行直接插入排序。希尔排序也叫缩小增量排序，是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 : \n", ARRAY_LENGTH);
    	for(i = 0; i < ARRAY_LENGTH; i++)
    	{
    		scanf("%d", &a[i]);
    	}
    
    	printf("****************************************************************\n");
    
    	/* 把排序前元素都打印出来 */
    	printf("The elements before sort is : \n");
    	for(i = 0; i< ARRAY_LENGTH; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    
    	printf("****************************************************************\n");
    
    	/* 对元素进行有小到大的直接插入排序 */
    	shell_sort(a, ARRAY_LENGTH, d, sizeof(d)/sizeof(d[0]));
    
    	/* 把排序后元素都打印出来 */
    	printf("The elements after sort is : \n");
    	for(i = 0; i < ARRAY_LENGTH; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    
    	return 0;	
    }

编译运行结果如下所示：

![SouthEast][]

[SouthEast]: /images/20220614/b637e3cdefec4c43b35b82d9b4d7256c.png