概要

      希尔(Shell)排序的主要思想是分组分别用插入排序实现排序，然后不断缩小分组时的相邻组内元素的距离达到排序效果，经过几步之后，整个序列基本有序，最后整体利用插入排序即可完成排序。这里为什么选择插入排序呢？因为排序过程中“基本有序”越来越好，所以采用插入排序最好。

主要代码及示例

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void ShellSort(int a[], int n);

int main()
{
	const int nLen = 20;
	int a[nLen] = {40,25,96,59,91,81,51,62,46,20};

	srand((unsigned int)time(NULL));
	for (int i=0; i<nLen; i++)
	{
		a[i] = rand()%100;
	}

	for (int i=0; i<nLen; i++)
	{
		printf("%2d ", a[i]);
	}
	printf("\n");


	ShellSort(a, nLen);

	for (int i=0; i<nLen; i++)
	{
		printf("%2d ", a[i]);
	}
	printf("\n");
	return 0;
}

void ShellSort(int a[], int n)
{
	int d = n;
	do
	{
		d /= 2;
		for (int i=0; i<d; i++)
		{
			/** 对a[j]插入排序 */
			for (int j=i+d; j<n; j+=d)
			{
				int k = j-d;
				int t = a[j];
				while(k>=0 && a[k]>t)
				{
					a[k+d] = a[k];
					k -= d;
				}
				a[k+d] = t;
			}
		}

		/** 输出过程信息 */
		printf("d=%2d时\t", d);
		for (int i=0; i<20; i++)
		{
			printf("%2d ", a[i]);
		}
		printf("\n");

	} while (d>1);
}

结果展示

 2 16 49 35 27 54 89 82 78 25 86 30 29 50 94 48 55 30 21 68
d=10时   2 16 29 35 27 48 55 30 21 25 86 30 49 50 94 54 89 82 78 68   # 按照组内元素距离为10后的排序结果，间隔为10的序列有序
d= 5时   2 16 29 21 25 48 30 30 35 27 54 55 49 50 68 86 89 82 78 94
d= 2时   2 16 25 21 29 27 30 30 35 48 49 50 54 55 68 82 78 86 89 94
d= 1时   2 16 21 25 27 29 30 30 35 48 49 50 54 55 68 78 82 86 89 94
 2 16 21 25 27 29 30 30 35 48 49 50 54 55 68 78 82 86 89 94

希尔排序