C语言排序算法总结——希尔排序

前言

之前我们总结了比较简单的几种排序方法。冒泡，选择，排序。但是也提到了这些排序方法的缺陷。时间复杂度太高，在有大量数据需要排序的时候，会需要浪费太多的时间。所以在很多场景中是不适合使用。我们这次总结一种时间复杂度更优秀的希尔排序。

思路

希尔排序是以插入排序为基础的改进版本。是由Shell提出的方法。所以就叫希尔排序了。。 插入排序的基本思路是：将元素插入到一个有序的元素集合中。在使用插入排序时，我们是一个接一个的。 希尔排序的思想是：先确定一个flag，将待排序数组分为几个小组。分组方式是：将间隔为flag的数据设为一组。完成一轮插入排序后，缩小flag，再进行第二轮插入排序。直到flag缩小到一。 当我们有一个初始序列时： 9125748635 加入我们在开始时，假设gap为5，则序列分组像这样的 也就是每两个元素为一组。 这时候我们就像是使用插入排序，对五组只有两个元素的序列进行排序。于是排序好的序列为： 4 1 2 3 5 9 8 6 5 7 第一趟排序结束后，我们再对排序好的元素以gap=2来分组。 当gap为2时，序列被分为了两组。也就是第二躺我们其实对两组有五个元素的序列进行插入排序。排序完成后： 2 1 4 3 5 6 5 7 8 9 最后当gap为1时，我们就是对整个序列进行插入排序。得到最终的排序结果： 1 2 3 4 5 5 6 7 8 9

代码总结

代码其实也比较简单，直接插入排序的间隔是1，所以我们在写希尔排序的时候，需要改变间隔。也就是额外设置一个gap。以及我们需要注意循环的结束。因为也许并不是每一次分组后，每组的数据个数都是一样的。所以要注意越界问题。 我们在这里设置的gap为上一次的三分之一。 具体的代码行为：

gap=gap/3+1;

末尾需要加1，是为了放置gap在这里变成0，如果上一次gap为2时，这时再2/3 ，结果会变成0，就会出现问题。

int* ShellSort(int* data, int nums)
{
          
   
	int gap = nums;
	while (gap > 1)
	{
          
   
		gap = gap / 3 + 1;
		for (int i = 0; i < nums - gap; ++i)
		{
          
   
			int end = i;
			int tmp = data[end + gap];
			while (end >= 0)
			{
          
   
				if (tmp < data[end])
				{
          
   
					data[end + gap] = data[end];
					end -= gap;
				}
				else
					break;
			}
			data[end + gap] = tmp;
		}
	}
	return data;
}