☑️前言

🚩我们在学习当中，最常见的算法莫过于排序算法了！

🚩而常见的排序算法有八种，本章给大家讲解八大排序中的直接插入排序和希尔排序

1. 直接插入排序

直接插入排序其实我们从小就在接触了，我们之前打的跑得快，斗地主，抓牌整理牌的过程就是类似于插入排序。

对于插入排序，它的过程是如何的呢？我们以下面这组乱序数组为例（假设这里以升序为例）：

5    1    2    4    6    3

由于数组的第一个元素是有序的，所以我们要从数组的第二个元素开始，也就是从下标为1的元素开始执行插入排序。

当插入第i (i >= 1) 个元素时，前面的array[0],array[1],…,array[i-1] 已经排好序，此时将array[i] 的值与array[ i - 1 ] , array[ i - 2 ] , … 的值依次进行比较，比array[i]大就将其往后移，找到正确的插入位置将array[i] 插入即可。

当i为1时 （定义一个变量tmp存储此时要插入的值，再定义一个变量end指向要插入的元素的前一个位置），也就是上面数组对元素1的插入，此时将1与前面一个元素5比较，发现5比1大，这时就将5后移放在1的位置，此时前面的有序序列已经遍历完毕，将tmp放入正确的位置，1就插入完毕。1插入后，数组变为：1 5 2 4 6 3，此时对元素2（下标也为2）进行插入，同样的进行上面的操作，5被挪动到下标为2的位置，5处理完后，元素2与元素1比较，1 < 2，此时说明数组已经有序，然后将元素2插入到元素1的后面的位置就OK了。2插入完后数组变为：1 2 5 4 6 3，同样的，后面对元素4，6，3的插入也是如此，由后向前依次与前面的有序序列的元素进行比较，比较出无序就将被比较的元素往后挪动一个位置，比较出有序，说明该元素应该被插入在被比较的元素的后面。

图示：

动图演示：

代码实现：

void InsertSort(int* a, int n)
{
  assert(a);
  // 从下标为1的元素开始
  for (int i = 1; i < n; i++)
  {
    // end 指向要插入的元素的前一个元素（前面是一个有序序列）
    int end = i - 1;
    // tmp 存放要插入的元素的值
    int tmp = a[i];
    while (end >= 0)
    { 
      // 如果大于 tmp 就将其向后挪动一位
      if (a[end] > tmp)
      {
        // 挪动，相当于覆盖后面的值
        a[end + 1] = a[end];
        // 减减将 tmp 再与前面的元素进行比较
        end--;
      }
      else break;  // 如果找到一个元素使其能够有序，就跳出循环，在其后插入
    }
    // 由后向前 在第一个比 tmp 小的数的后面的位置插入 tmp 
    a[end + 1] = tmp;
  }
}

对于直接插入排序的时间复杂度，从最坏的角度看，每一趟插入的次数相加是一个等差数列，因此直接插入排序的时间复杂度为 O(logN^2)。而最好的情况，就是数组有序，此时每一个元素的插入排序都不会进行，所以相当于只是遍历了一遍数组，时间复杂度为O(N)。

很明显，空间复杂度为 O(1)。

直接插入排序是稳定的。（除排序交换了两个元素的初始相对位置顺序之外，并没有改变其它任意两个元素初始的相对位置（开始谁在前，现在还是谁在前）。）

2. 希尔排序

希尔排序是直接插入排序的一个优化版。

那么它是如何优化的呢?

希尔排序法又称缩小增量法。希尔排序法的基本思想是：一个数组，它的长度为n，先选定一个整数gap（gap < n），把待排序的数组的所有元素分成若干个组，所有距离为gap的分在同一组内，并对每一组内的元素进行距离为gap的插入排序。当一个gap排完每一组后，gap按一定规律变小，并重复上述分组和排序的工作。当gap == 1时，相当于直接插入排序，最后数组就有序了。

图示排序过程：

每个gap值都对应着一趟距离为gap的插入排序，每一趟排序会使数组越来越接近有序，直到最后gap为1，相当于是一趟直接插入排序。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，就会很快。这样整体而言，可以达到优化的效果。

关于gap，每次排完一趟到下一趟排序可以将他除以2作为这趟排序的分组排序距离，这样循环往复，最终，gap会变成1，数组会有序。

代码实现：

// 希尔排序
void SherSort(int* a, int n)
{
  assert(a);
  int gap = n;
  while (gap > 1)
  {
    // 这里是 gap 每次除以 2
    // 当然其它取法也行，只要 gap 最后能够变为 1 即可
    gap /= 2;
    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      // tmp 为要进行距离为gap的插入的值
      int tmp = a[i + gap];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          // 每一次挪动一个位置，end（下标）要减 gap 距离
          // 因为是按 gap 来分组的
          end -= gap;
        }
        else break;
      }
      // 插入合适的位置
      a[end + gap] = tmp;
    }
  } 
}

时空复杂度分析：

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：

对于空间复杂度，很明显，为O(1)。

稳定性：不稳定。

☑️写在最后

💝排序相对来说较为简单，不过我们还是要认真对待，理清楚排序的思路。

❤️‍🔥后续将会继续输出有关数据结构与算法的文章，你们的支持就是我写作的最大动力！

感谢阅读本小白的博客，错误的地方请严厉指出噢~