八大排序——希尔排序

希尔排序算法思想

希尔排序核心思想就是:1,分组;2,直接插入排序:越有序越快
希尔排序就是多次利用直接插入排序的一个排序算法.
希尔排序的算法思想:间隔式分组,利用直接插入排序让组内有序,然后缩小分组再次排序,直到组数为1

希尔排序的理论基础就是直接插入排序越有序越快;
1.先预排序：取一个小于N的整数gap作为第一次增量，然后将距离gap的元素放入一组，再对每一组进行直接插入排序。然后将gap缩小，作为第二增量，重复以上操作。

2.再直接插入排序：当gap缩小为1时，进行直接插入排序

3.希尔排序利用了gap越大，挪动数据的距离越大，效率更高；gap越小，挪动的距离越小，前面让gap较大，可以让数据更快的挪动到自己对应的位置附近，减少挪动次数，让数据部分有序，利用直接插入排序越有序越快的特性。

 希尔排序的代码实现

//一趟希尔排序,gap为组数(间隔)
static  void  Shell(int* arr, int len, int gap)
{
	int  tmp;
	int j;
	for (int i = gap; i < len; i++)
	{
		tmp = arr[i];
		for (j = i - gap; j >= 0; j -= gap)
		{
			if (arr[j] > tmp)
			{
				arr[j + gap] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + gap] = tmp;
	}
}

void  ShellSort(int* arr, int len)
{
	int d[] = { 5,3,1 };//分组数,最后一个一定为1
	for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++)
	{
		Shell(arr, len, d[i]);//一趟希尔排序
	}
}

希尔排序考察点:O(n1.3~n1.5),O(1),不稳定,详细见《数据结构C语言版》严蔚敏上284页.