@[toc]

插入排序

插入排序分为直接插入排序和希尔排序，其中希尔排序是很值得学习的算法

希尔排序的基础是直接插入排序，先学习直接插入排序

直接插入排序

直接插入排序类似于打扑克牌前的整牌的过程，假设我们现在有2 4 5 3四张牌，那么应该怎么整牌？
方法很简单，把3插到2和4中间，这样就完成了整牌的过程，而插入排序的算法就是这样的过程

插入排序的基本原理图如下所示

我们在这里定义end为已经排查结束的，排好序的一段数据的最后一个元素，tmp作为存储要移动的元素，那么具体实现方法如下：

这里找到了tmp确实比end要小，于是下一步是要让tmp移动到end前面这段有序的数据中的合适的位置

算法实现的思想是：tmp如果比end的值小，那么就让end的值向后移动，end再指向前一个，再比较覆盖移动...直到tmp的值不比end小或者end直接走出数组，如果走出数组就让tmp成为新的首元素

这样就完成了一次插入，那么接着进行一次排序：

从中可以看出，插入排序整体的思想并不算复杂，代码实现相对也更简单，直接插入排序的价值在于给希尔排序做准备

插入排序的实现如下：

void InsertSort(int* a, int n)
{
   
   
    for (int i = 0; i < n - 1; i++)
    {
   
   
        int end = i;      // 找到有序数组的最后一个元素
        int tmp = a[i + 1];  // 要参与插入排序的元素
        while (end >= 0)
        {
   
   
            if (a[end] > tmp)
            {
   
   
                // 进行覆盖
                a[end + 1] = a[end];
                end--;
            }
            else
            {
   
   
                break;
            }
        }

        a[end + 1] = tmp;
    }
}

直接插入排序的时间复杂度也不难分析，是O(N^2)，和冒泡排序在同一个水平，并不算高效
直接插入排序更多是给希尔排序做铺垫，希尔排序是很重要的排序，处理数据的效率可以和快速排序看齐

希尔排序

上面学完了插入排序，那么就必须总结一下插入排序的弊端

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

于是，希尔排序就是基于上面这两个问题进行解决的：
首先，插入排序对于已经排序差不多的序列有很强的效率，但与此同时它一次只能调整一个元素的位置，因此希尔就发明了希尔排序，它具体的操作几乎和插入排序相同，只是在插入排序的基础上，前面多了预排序的步骤，预排序是相当重要的，可以把一段数据的大小排序基本相同

那预排序的实现是如何实现的？

首先把数据进行分组，假设分成3组，下面的图片演示了这个过程

分好组后，对每一组元素单独进行插入排序

此时，序列里的数据就已经很接近有序了，再对这里的数据进行插入排序，可以完美适应插入排序的优点

这里只是写了希尔排序的基本思想是如何工作的，具体的代码实现较为复杂

那么下一个问题就有了，为什么gap是3？如果数据量特别大还是3吗？gap的选择应该如何选择？
这里对gap要进行理解，gap到底是用来做什么的，它的大小会对最终结果造成什么影响

gap是对数据进行预处理阶段选择的大小，通过gap可以把数据变得相对有序一点，而gap越大，说明分的组越多，每一组的数据就越少，gap越小，分的就越细，就越接近真正的有序，当gap为1的时候，此时序列只有一组，那么就排成了真正的有序

代码实现如下：

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

这里重点理解两点

gap = gap / 3 + 1;  // 这句的目的是什么？
gap==1  // 是什么

gap=gap/3+1会让gap的最终结果一定为1
而gap为1的时候，此时就是插入排序，而序列也接近有序，插入排序的优点可以很好的被利用

希尔排序的时间复杂度相当难算，需要建立复杂的数学模型，这里直接说结论，希尔排序的时间复杂度大体上是接近于 O(N^1.3) 整体看效率是不低的，值得深入钻研学习