希尔排序

注1：本篇是基于对直接插入排序法的拓展，如果对直接插入法不了解，建议先看看直接插入排序

注2：本篇统一采用升序排序

基本思想

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

• 希尔排序其实是直接插入排序的改进。

• 其基本思想是：先选定一个整数gap，把待排序文件中所有记录分成数组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后缩小gap，重复上述步骤，当gap == 1时，所有记录在统一组内已经排好序。

整体插入思想

• 在直接插入排序中，我们知道最坏的情况是待排序列降序逆序的情况，如序列：8,7,6,5,4,3,2,1，这时时间复杂度为O(N²)，显然效率不高
• 而希尔排序的思想，就是先对待排序列进行预排序，使待排序列接近有序。我们知道，当待排序列接近有序时，直接插入排序法的时间复杂度接近O(N)，效率很高，因此预排序过后，就使用直接插入排序法，从而提高了效率。

预排序

• 预排序实际上也是直接插入排序，但是是将待排序列分成数组来排

• 根据基本思想，规定间隔为gap的数为一组

• 我们以数组{9,8,7,6,5,4,3,2,1}，gap = 3为例：

  • 每gap为一组：

    

  • 对第一组排序：

    

  • 对第二组排序：

    

  • 对第三组排序：

    

• 这时相较于最开始，待排序列更加接近于有序，此时我们不断缩小gap，不断预排序，直到最后gap == 1时最后使用一次直接插入排序（gap == 1时的直接插入排序实际上就是最原始的直接插入排序），使待排序列有序。

• 又例如：

  

结论

• 希尔排序实际上就是多组间隔为gap的预排序，gap由大到小
• gap越大，大的数能越快到后面，小的数能越快到前面
• gap越大，预排序之后待排序列越不接近于有序
• gap越小，预排序之后待排序列越接近于有序
• 当gap == 1时，预排序实际上就是对整个序列进行直接插入排序，排完后序列即有序
• 因此，最后一次预排序，gap必须为1.

代码实现

• 对每间隔gap的一组数据进行排序，本质上就是直接插入排序，故不作过多讲解

  int end;
  int temp = nums[end + gap];
  while (end >= 0)
  {
      if (temp < nums[end])
      {
          nums[end + gap] = nums[end];
          end -= gap;
      }
      else
          break;
  }
  nums[end + gap] = temp;
  

• 对多组间隔为gap的数据进行预排序

  • 以这张图为例：

    

  • 我们上面的步骤只是将间隔为pap的一组数据进行了排序，但待排序列不止一组间隔为gap的数据，因此我们要做到将所有间隔为gap的每组数据都进行排序。

  • 怎么实现呢？可能最容易想到的是分别将每组间隔为gap的数据进行排序，例如上面分别对第一组，第二组，第三组排序，但是这样做效率不高，且操作复杂。因此我们要换一种想法，即把间隔为gap的数据同时排序。

  • 如图：

    

  for (int i = 0; i < numsSize - gap; i++)
  {
      int end = i;
      int temp = nums[end + gap];
      while (end >= 0)
      {
          if (temp < nums[end])
          {
              nums[end + gap] = nums[end];
              end -= gap;
          }
          else
              break;
      }
      nums[end + gap] = temp;
  }
  

• 最后还要不断缩小gap的值，直到gap == 1

  int gap = numsSize;
  while (gap > 1)
  {
      gap /= 2;	//不断缩小gap
      /*
      	也可以写成 gap = gap / 3 + 1;
      	总之，必须要保证最后一次gap == 1
      */
  
      for (int i = 0; i < numsSize - gap; i++)
      {
          int end = i;
          int temp = nums[end + gap];
          while (end >= 0)
          {
              if (temp < nums[end])
              {
                  nums[end + gap] = nums[end];
                  end -= gap;
              }
              else
                  break;
          }
          nums[end + gap] = temp;
      }
  }
  

实现代码

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

直接插入排序与希尔排序的效率比较

• 看到希尔排序有三层循环，可能有小伙伴会疑惑希尔排序为什么会比直接插入排序快，这里我们先上测试代码，直观的来感受这两个排序算法之间的差距：

测试代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

//直接插入排序
void InsertSort(int* nums, int numsSize)
{
	for (int i = 0; i < numsSize - 1; i++)
	{
		int end = i;
		int temp = nums[end + 1];
		while (end >= 0)
		{
			if (temp < nums[end])
			{
				nums[end + 1] = nums[end];
				end--;
			}
			else
				break;
		}
		nums[end + 1] = temp;
	}
}

//希尔排序
void ShellSort(int* nums, int numsSize)
{
	int gap = numsSize;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < numsSize - gap; i++)
		{
			int end = i;
			int temp = nums[end + gap];
			while (end >= 0)
			{
				if (temp < nums[end])
				{
					nums[end + gap] = nums[end];
					end -= gap;
				}
				else
					break;
			}
			nums[end + gap] = temp;
		}
	}
}

int main()
{
	srand((unsigned int)time(NULL));
	
   //创建两个大小为N的数组
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	
   //为数组赋随机值
	for (int i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	
   /*
   	clock()函数可以记录当前时间
   	begin和end的差即排序算法运行的时间
   	注：时间的单位为毫秒(ms)
   */
	int beginl = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	printf("InsertSort:%d\n", end1 - beginl);
	printf("ShellSort:%d\n", end2 - begin2);

   //释放内存
	free(a1);
	free(a2);

	return 0;

}

测试结果：

• 我们可以看到，当数据个数为十万个时，直接插入排序所需要的时间是的希尔排序的100多倍
• 当数据个数为一百万个时，直接插入排序所需要的时间时希尔排序的2000倍、
• 可见，数据越多，希尔排序的优势就越明显，节省点时间就越多

时间复杂度

• 从上面的测试中，我们直观的感受到了相较于直接插入排序，希尔排序的优越性，那么具体的希尔排序的时间复杂度为多少呢？

• 我们先来看最外层的循环：

  int gap = numsSize;
  while (gap > 1)
  {
      gap /= 2;
      …………
  }
  

  • 设最外层循环运行了x次，那么2^x = numsSize，x = log₂N，即最外层的时间复杂度为log₂N

• 再看里面两层循环：

  for (int i = 0; i < numsSize - gap; i++)
  {
      int end = i;
      int temp = nums[end + gap];
      while (end >= 0)
      {
          if (temp < nums[end])
          {
              nums[end + gap] = nums[end];
              end -= gap;
          }
          else
              break;
      }
      nums[end + gap] = temp;
  }
  

  • 当gap很大时，尽管有两层循环，但数据之间跳跃的很大，需要排序的次数很少，因此时间复杂度为O(N)，例如这种情况：

    

  • 当gap很小时，尽管有两层循环，但此时数据已经接近有序，需要排序的次数也很少，因此时间复杂度也为O(N)。

• 综上，希尔排序的时间复杂度为O(NLog₂N)

• 也可以认为时间复杂度为O(N^1.3)