排序算法 —— 希尔排序

1.希尔排序的由来

2.希尔排序的思想

3.希尔排序的实现

实现分析

实现代码

代码优化

4.希尔排序的总结

1.希尔排序的由来

希尔排序是对直接插入排序的优化。在直接插入排序算法中，如果数据是有序or接近有序的时候，直接插入排序算法的时间复杂度是O(N)，因为每次选取的待排序元素不需要经过太多次的比较，就能插入到有序序列中。

所以希尔排序的发明者就想，如果能把待排序序列快速的变得接近有序，那么直接插入排序不就能得到优化了吗？

2.希尔排序的思想

希尔排序的思想就是先对序列中的元素进行间距分组，先把分出来的这些组进行插入排序，然后缩小间距，再进行分组，在进行插入排序，当间距缩小为1的时候，此时就是直接插入排序。所以，希尔排序又叫缩小增量排序。

希尔排序分为两步：预排序和直接插入排序。在间距大于1的时候所进行的排序叫做预排序，当间距等于1的时候进行的排序就是直接插入排序。

预排序的意义：

大的数据越快的跳到后面去，小的数据越快的跳到前面去。

间距越大，数据跳的越快，数据越不接近有序。

间距越小，数据跳的越慢，数据越接近有序。

值得注意的是：当间距为几的时候，数据就被分成了几组。

3.希尔排序的实现

实现分析

想要实现希尔排序，我们先分析清楚如何实现一趟排序，就拿下面这个例子来说，我们先看红色的这一组。

红色的这一组之间的间距是3，我们类比直接插入排序，直接插入排序可以看做间距为1，所以我们只需要对直接插入排序稍微修改即可得出单趟排序的代码。

在上面右侧的代码中最外围的变量 i 控制的是一组中的元素下标，当这层循环走完之后，说明完成了一组数据的排序，但是我们需要完成的是分出的所有组的排序。在讨论希尔排序的思想的时候，我们发现，数据之间的间距是多少，数据就被分成了几组，所以，还需要在外面再加一层循环控制排序的数据是第几组的数据。

代码如下：

在前面我们也讨论过，希尔排序的间距是需要变化的，并且是变小的，而且，间距最后必须为1，所以，我们先将间距设置为待排序数据个数的一半，然后逐渐缩小一半。所以还需要再加一层循环控制间距。

代码如下：

实现代码

#include <stdio.h>

void ShellSort(int* a, int n)
{
	int gap = n;

	while(gap > 1) // 控制间距 
	{
		gap /=2;
		for (int j = 0; j < gap; j++)  //控制排第几组的数据 
		{
			// 枚举一组中待排序的数据 
			for (int i = 0; i < n - gap; i += gap) 
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}
}

int main()
{
	int nums[] = {5,1,2,4,6,3,8,9,7,0};
	ShellSort(nums,10);
	
	int i = 0;
	while(i < sizeof(nums)/sizeof(int))
	{
		printf("%d ",nums[i]);
		i++;
	}
	
	
	return 0;
}

代码优化

在上面的代码中，我们是将数据分成多组之后，然后一组排完之后再排另一组。其实，这多组数据是可以同时排的，也就是多组并排。

优化方案：1.去掉控制排第几组数据的循环。2.将枚举一组中待排序的数据修改为枚举所有组中待排序的数据。

代码示例如下：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i) //枚举所有组中待排序的数据 
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}