希尔排序算法

ShellSort希尔排序

整体思路

图解分析

【1】预排序

单组排序

多组并排

【2】直接插入排序

关于gap取值

总代码实现

时间复杂度

ShellSort希尔排序

希尔排序法又称缩小增量法。

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
希尔排序=预排序+直接插入排序
预排序：让大的数值更快的到达后面，小的数值更快的到达前面。（达到一个让数组元素接近顺序的效果）
gap是间距值❗
直接插入排序相当于gap==1，希尔排序相当gap存在值了。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 稳定性：不稳定

4. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

整体思路

gap是数值之间的间距值❗
直接插入排序相当于gap==1，希尔排序相当gap存在值了。
gap是几，就可以把整体分为几组。（除去gap = n的情况)（gap=gap/2或者gap=gap/3+1)
分组和每组里面的元素个数的关系

gap = n（gap随着n的变换而变化，gap的值不固定）
gap/2（每次gap组，每组里面的元素个数：2，4，8......)*2 【n/2，n/4，n/8....】
gap/3+1 (每次gap组，每组里面的元素个数：3，9，27...）*2【n/3，n/9，n/27....】
随着gap的变小，组数会变小，每组里面的数值个数会变大。
gap的值

一个数无论是奇数还是偶数/2 最后都等于1
gap的值不是固定的，可以是gap/2或者gap/3+1
gap值无论是/2 /3，最后都必须==1 ，最后要直接插入排序
gap>1时时预排序，目的是让整体数值更加接近有序
gap == 1的时候就是直接插入排序，目的是让整体值有序。
gap的值越大，大的值更快的调到后面，小的值可以更快的调到前面，越不接近有序。
gap的值越小，大的值更慢的调到后面，小的值可以慢的调到前面，越接近有序。
gap的值不是固定的，gap的值是随着整体n的大小变化而变化的。
随着gap的变小，组数会变小，每组里面的数值个数会变大。
预排序gap的上一个值排完之后会对下一个值得排序调整次数产生影响。

整体思路

一趟：类似直接插入排序的一趟，间距从1变为gap
一组：加入循环，完成一组的排序（类似直接插入排序整体）
多组：加入三层嵌套循环/多组并排。（完成多组排序）（gap是多少就有多少组）
整体：完成整个数组的排序（多次预排序直到最后插入排序gap=1)（n个值）gap=n（gap=gap/2或者gap=gap/3+1)

图解分析

gap是数值之间的间距值❗
gap=n（n是整个的数值个数）
gap=gap/2
gap=10/2=5
gap=5/2=2
gap=2/2=1
注意：无论gap用gap/2或者gap/3+1或者其他最后gap的值必须为1，因为最后要进行直接插入排序，完成整体的排序。

【1】预排序

为了理解，这里我们先把gap理解为固定值gap == 3是一个固定值。假设n=11

单组排序

一组一组排序
三个嵌套循环
控制起始位置i=j（0/1/2）
i=0（0/3/6）
i=1（1/4/7）
i=2（2/5）
i=0/3/6/1/4/7/2/5
控制数组元素下标，防止越界i<n-gap（i<11-3=8)

//升序
//写法1：三层嵌套循环
void ShellSort(int* a, int n)
{
	//多组
	int gap = 3;
	for (int j = 0; j < gap; j++)
	{
        //每组
		for (int i = j; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			//一趟
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else//<=
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

多组并排

多组并排
两个嵌套循环
控制起始位置i=0/1/2
i=0/1/2/3/4/5/6/7
控制数组元素下标，防止越界i<n-gap（i<11-3=8)

//写法2
//多组并排
void ShellSort(int* a, int n)
{

	//多组
	int gap = 3;
	for (int i = 0; i < n - gap; i++)
	{
		int end = i;
		int tmp = a[end + gap];
		//一趟
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else//<=
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}
}

【2】直接插入排序

实际上如果整体的数量过大，gap为3是非常不合适的。所以，gap不可能为固定值，gap的取值是随着n变化的，所以gap有两种方式去取值。

关于gap取值

gap=gap/2
gap=gap/3+1
注意：无论gap用gap/2或者gap/3+1或者其他。最后gap的值必须为1，因为最后要进行直接插入排序，完成整体的排序。
gap是几，就可以把整体分为几组。（除去gap = n的情况)（gap=gap/2或者gap=gap/3+1)
分组和每组里面的元素个数的关系
gap = n（gap随着n的变换而变化，gap的值不固定）
gap/2（每次gap组，每组里面的元素个数：2，4，8......)*2 【n/2，n/4，n/8....】
gap/3+1 (每次gap组，每组里面的元素个数：3，9，27...）*2【n/3，n/9，n/27....】
随着gap的变小，组数会变小，每组里面的数值个数会变大。

void ShellSort(int* a, int n)
{
	//整体
	int gap = n;
	while (gap > 1)
	{
		//每组
		//gap = gap / 2;
		gap = gap / 3 + 1;
        //..........
		}
	}
}

总代码实现

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 (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else//<=
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

时间复杂度

希尔排序的时间复杂度O(N^1.3)
O(N^1.3)比O（N*logN)略慢，效率略低一点。
希尔排序VS直接插入排序（秒入过万VS分入过万）
预排序gap的上一个值排完之后会对下一个值得排序调整次数产生影响。
O(N^1.3)需要套用数学模型，统计学来计算，这里只是近似计算。记住最后结论即可。