希尔排序是直接排序的更好优化

如果没有听过直接插入排序的可以看这里——

直接插入排序是一个一个的插入，然后排序

但是希尔排序不一样

希尔排序的思路

：分组排序，将一个数组排到相对有序，然后在进行插入排序

例如这样的一个数组

我们将每间隔为2的分为一组

然后我们进行每组的排序

我们将间隔减少继续排列

根据这样的思想，我们就得到了希尔排序

2.代码实现

我们默认间隔为gap

首先我们先完成一组内的排序（与直接插入排序相似）

先将需要插入的数存起来

int tmp = arr[end + gap];

然后我们对这组内的数字进行遍历比较

while (end)
{
		if (arr[end] > tmp)
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
}

当循环停止时（两种情况）

1.找到了比他小的数

2.找完了也没找到比他小的数

就是我们要放入这个数的时候

arr[end + gap] = tmp;

这是一组的比较，那么我们一共要进行多组

引入循环

for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}

当循环结束的时候，我们就将这个数组变得相对有序

那么我们该如何将他变得完全有序呢？

答案是：改变gap

gap每变小一次，数组就相对有序，直到gap变为1，数组完全有序

gap我们希望第一次是n/2，每次gap/=2；

因此引入gap，进行多次排序使得，数组完全有序

完整代码

void ShellSort(int* arr,int n)
{
	int gap = n/2;
	while (gap /= 2)
	{
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
		
	}
	
}