数组希尔排序

希尔排序是建立在插入排序的基础之上的，只不过是将数据中做插入排序之前做了一次分组，他的分组是根据用户输入的一个数字来决定分多少组的，比如有如下数据：

49 58 65 97 26 13 27 49 55 4

按下图表示的方法进行三次分组，对每次分组出来的数据执行插入排序，最后得出有序的数组，乍一看来这岂不是多了一步画蛇添足的步骤？实际并不是这样，因为先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前三种方法有较大提高。

【实现代码】

void shell_sort(int *arr, int len)
{
	int value = len;
	int temp = 0;
	int index = 0;
	do 
	{
		// 业界统一实验的 平均最好情况 经过若干次后,收敛为1
		value = value / 3 + 1;
		// 一次跳 value 个
		for (int idx = 0; idx < value; idx++)
		{
			// 对分组后的数据进行排序，每一次跳过整个长度
			for (int i = value; i < len; i += value)
			{
				index = i;
				temp = arr[i];
				for (int j = i - value; j >= 0 && arr[j] > temp; j -= value)
				{
					arr[j + value] = arr[j];
					index = j;
				}

				arr[index] = temp;
			}
		}
	} while (value > 1);
}