数组希尔排序

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

49 58 65 97 26 13 27 49 55 4

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

2015-06-07_233049

【实现代码】

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);
}

 

发表评论