28.希尔排序

插入排序虽好，但是某些特殊情况也有很多缺点，比如像下面这种情况:

169 前的元素基本不用插入操作就已经有序，元素1 和2 的排序几乎要移动数组前面的所有元素!!! 于是，有个老帅哥就提出了优化此问题的希尔排序!
希尔排序是希尔（Donald Shell）于1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，所有元素被分成一组，实际上等同于执行一次上面讲过的插入排序，算法便终止。

希尔排序的基本步骤：

选择增量：gap=length/2，缩小增量：gap = gap/2
增量序列：用序列表示增量选择，{n/2, (n/2)/2, …, 1}
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序;
仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码实现:

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

void ShellSort(int arr[], int len)//希尔排序
{
	int gap = len / 2;

	for (; gap > 0; gap = gap / 2)//增量，依次按除2的范围缩小
	{
		for (int i = gap; i < len; i++)
		{
			int current = arr[i];

			int j = 0;

			for (j = i - gap; j >= 0 && arr[j] > current; j -= gap)
			{
				arr[j + gap] = arr[j];
			}
			arr[j + gap] = current;
		}
	}
}

int main()
{
	int beauties[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 , 1, 2};

	int len = sizeof(beauties) / sizeof(beauties[0]);

	ShellSort(beauties, len);

	printf("美女排序以后的结果是：\n");
	for (int i = 0; i < len; i++)
	{
		printf("%d ", beauties[i]);
	}

	system("pause");
	return 0;
}

参考资料来源：

奇牛学院