排序算法之希尔排序

        1959年Shell发明，是简单插入排序的改进版。它与插入排序的不同之处在于：它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序

一、基本思想：

        把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。那么到最后的时候，插入的序列是一个大致有序的序列，效率会非常高。

• 时间复杂度：O(n²)
• 空间复杂度：O(1)  
• 排序稳定程度：稳定 
• 适用场景：数据量大，元素杂乱无章。

二、示例：

      

• 初始时，有一个大小为 10 的无序序列。
• 第一趟排序中，设 步长 gap = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组，然后按照直接插入排序的方法对每个组进行排序。
• 在第二趟排序中，我们把上次的 gap 缩小一半，即 gap' = gap / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组，然后按照直接插入排序的方法对每个组进行排序
• 在第三趟排序中，再次把 gap 缩小一半，即gap'' = gap' / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。接着按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

三、代码实现：

void ShellSort(int arr[], int size)
{
	if (size <= 1)
		return;
	for (int gap = size / 2; gap > 0; gap /= 2)   //步长分组
	{
		for (int pos = 0; pos < gap; pos++)   // 每组起始元素
		{
			for (int ret = pos + gap; ret < size; ret += gap)  // 插入排序，不过每组元素间相差 gap
			{
				int index = ret - gap;
				int val = arr[ret];  //val 记录要插入的元素
				while (index >= 0 && val < arr[index])
				{
					arr[index + gap] = arr[index];
				    index -= gap;
				}
				arr[index + gap] = val;  //把要插入的元素插进有序数组的相应位置
			}
		}
	}
}

//test.c
int main()
{
	int arr[] = {9,5,2,7,4,3,8,6};
	int size = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, size);
	for (int i = 0; i < size; ++i)
		printf("%d", arr[i]);
	system("pause");
	return 0;
}