直接插入排序、希尔排序详解。及性能比较

一、 直接插入排序

1.1 插入排序原理

直接插入排序是一种简单的插入排序法，其基本原理是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

而实际中我们玩扑克牌时，就用了插入排序的思想

1.2 代码实现

【代码思路】：直接插入排序还是比较简单的。我们将第一个元素当作一个有序序列，然后从第二个元素开始，将其作为当前插入的元素，并与已排序部分的元素进行比较，找到合适的插入位置。然后不断重复上述操作，直到所有元素都被插入到已排序部分。

当插入第i(i>=1)个元素时，前面的a[0], a[1], …, a[i-1]已经排好序，此时用a[i]的排序码与a[i-1],a[i-2],…的排序码顺序进行比较，找到插入位置即将a[i]插入，原来位置上的元素顺序后移。

void InsertSort(int* a, int n)//排升序
{
  for (int i = 0; i < n-1; i++)
  {
    int end = i;
    //tmp记录待插入元素，因为插入数据时需要挪动数据，会被覆盖
    int tmp = a[end+1];
    //[0,end]有序，将tmp插入到合适位置
    while (end >= 0)
    {
      if (a[end] > tmp)
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;
  }
}

1.3 直接插入排序特点总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高。
2. 时间复杂度：O(N^2)。并且是时间复杂度为 N^2的所有算法中最快的排序。
3. 空间复杂度：O(1)，它是一种稳定的排序算法。

二、希尔排序 ( 缩小增量排序 )

逆序有序的数组进行插入排序时，时间复杂度为O ( n^2 )，此时效率最低。

顺序有序的数组进行插入排序时，时间复杂度为O ( n )，此时效率最高。

我们发现，当被排序的对象越接近有序时，插入排序的效率越高，那我们是否有办法将数组变成接近有序后再用插入排序，此时希尔大佬就发现了这个排序算法，并命名为希尔排序

2.1 希尔排序原理

希尔排序法又称缩小增量法。为了提高插入排序效率，希尔给出了这样一个办法：

将原有大量数据进行分组，分割成若干个子序列，此时每个子序列待排序的个数就减少了。然后对这些子序列分别进行插入排序（目的在于使较小的数据基本在前面，较大的数据基本在后面，而不大不小的数据则位于中间，从而达到排序基本有序的目的）。当整个序列基本有序时，最后在全体进行一次插入排序即可。

2.2 代码实现

【代码思路】：首先确定希尔排序的间距（gap），可以根据不同的方法选择不同的间距。根据选择的间距，将待排序的数组分割成若干个子序列，使用插入排序对每个子序列进行排序。逐步减小间距，重复第二步，直到间距为1。此时，整个数组被分割成了一个子序列，即原始的待排序序列。最后对原始的待排序序列进行插入排序，最终得到有序数组。（这里博主建议gap=n(数据个数）/ 3,在不断更新gap)

void ShellSort(int* a, int n)
{
  //1. gap>1 预排序
  //2. gap=1 插入排序
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;
    //多组并排
    for (int j = 0; j < n - gap; j++)
    {
      int end = j;
      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.3 希尔排序特点总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
   《数据结构(C语言版)》— 严蔚敏
   
   《数据结构-用面相对象方法与C++描述》— 殷人昆
   
   因为此处的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(n^1.25) ~ O(1.6 * n^1.25)。

三、直接插入排序和希尔排序性能大比拼 !!!

希尔排序虽然看起来比较普通，但实际性能可以和快排以及堆排序达到一个量级！！！

3.1 如何对比性能？准备工作

要对比两算法性能，首先创建一个包含大量元素的随机数组，这个数组将用于测试两个排序算法的效率。并且要确保测试数据集的大小足够大，以便能够准确测量算法的效率。在分别对两个排序算法在相同的测试数据集上进行排序，并记录每个算法排序所花费的时间。最后将两个排序算法的排序时间进行比较即可。

Tips：

①：在对比两个排序算法的效率时，需要确保使用相同的编程语言和相同的测试数据集。

②：：编译器切换到Release模式。

至于原因就得提到Release的特点了。

Release模式可以优化代码的性能和执行速度，减少调试信息的冗余，并提高程序的运行效率。在对比两个算法时，这些优化和调试信息并不是必需的。

3.2 如何实现？

创建数据

首先为两个为两个待排序数组创建足够大的存储空间，然后调用rand()随机生成数据。为保证两待排数组中的数据一样，将随机生成的数据依次赋值给两数组。

比较快慢

要比较两则运行时间，可以调用clock()函数，就可以轻松得到算法执行时间了！！

CPlusPlus:clock()

（clock()计算的是程序运行开始到执行此函数的运行时间，单位ms）

代码、结果分析

void TestOP()
{
  srand((unsigned int)time(NULL));
  //博主受限电脑配置，数据只能建10000个。
  //各位可适当扩大数据，两则差距更明显
  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];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  free(a1);
  free(a2);
}

运行结构：

上述结果我们直观发现，希尔排序性能远远大于直接插入排序。

可能有部分学者还是感受不出来，你可以将数据个数扩大到百万看看就知道了。