数据结构——lesson10排序之插入排序

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

上篇我们学习了选择排序的两种算法——直接选择排序与堆排序，今天我们将学习插入排序，它也有两种——直接插入排序与希尔排序🥳🥳

1.直接插入排序

1.1基本思想：

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

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

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

每次摸到一张牌我们就会把他和前面的牌逐一比较，直到找到适合它的位置进行交换，同时后面的牌要顺位往后移一位，因为中间加了一张牌。

图解如下：

每次取一个数与前面的数比较，直到找到合适的位置

1.2代码实现如下

// 插入排序
void InsertSort(int* a, int n)
{
  //排n-1趟
  for (int i = 1; i < n; i++)
  {
    int endi = i - 1;//endi表示已经排好序的尾标
    int tmp = a[i];//首先保存要排序的数，一会就会被覆盖了
    //一趟排序
    while (endi >= 0)
    {
      if (a[endi]  > tmp )//只要前面的数大于tmp, 则前面的这些数都向后挪动一个位置
      {
        a[endi + 1] = a[endi];
        endi--;
      }
      else
        break;
    }
    a[endi + 1] = tmp;//最后再把挪动后空出来的位置给tmp

  }
}

以上面动图的数据为例：

int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };

结果如下：

1.3直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)

从下标为1开始每次拿出数组的一位数与前面的数进行比较，按照最坏的情况前面所有的数都比较一次，时间复杂度可以看成1+2+3+4+…+n-1；结果是O(N^2)；如果元素集合接近有序则不需要和前面所有的数比较时间复杂度大大减少，最好时（有序）可以达到O(n).

3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.希尔排序

2.1基本思想

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

希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有数分成几个组，所有距离为gap的数分在同一组内，并对每一组内的数进行排序。然后将选定的gap按规律依次减少，重复上述分组和排序的工作。直到gap为1时，此时就是直接插入排序，因为之前进行的预排序已经将该组数排得接近有序了，所以最后一次排序时时间复杂度大大减少。

图解如下：

记得每次分组时不是单一的将n个数分成gap组而是从下标为0开始间隔gap距离的数直到末尾的几个数分成一组，再从下标为1开始间隔gap的数分为一组…图解如下：

上面1、3、9、6还应该加一个7漏了写了；因为每个都是与后面gap距离的数比较所以我们直接for循环从下标为0到n-1即可，然后比较时与距离为gap的比较，具体可看下面的代码实现。

希尔排序分为两个步骤：预排序（当gap>1）和直接插入排序(gap=1)

2.2代码实现如下

// 希尔排序
void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)//不能写成大于0,因为gap的值始终>=1
  {
    //只有gap最后为1，才能保证最后有序
    //所以这里要加1
    gap = gap / 3 + 1;
    //这里只是把插入排序的1换成gap即可
    for (int i = gap; i < n; i++)
    {
      int endi = i - gap;
      int tmp = a[i];
      //一趟排序
      while (endi >= 0)
      {
        if (a[endi] > tmp)
        {
          a[endi + gap] = a[endi];
          endi -= gap;
        }
        else
          break;
      }
      a[endi + gap] = tmp;

    }
  }
}

2.3希尔排序特性

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。

3.结语

插入排序也有两种——直接插入排序和希尔排序；希尔排序是由希尔发明的对直接插入排序的一种优化，使用gap来跳跃实现，不得不说这位大佬的思维也很跳跃，希尔排序关键理解它的分组以及gap每次都要依次减少直到为1才能实现排序，不是说一次gap就可以实现排序。以上就是插入排序的实现啦~ 完结撒花 ~🥳🥳🎉🎉🎉