目标

1.插入排序

2.插入排序实战

3.插入排序的实现

4.插入排序的效率

5.平均情况

6.希尔排序

7.希尔排序的实现

8.希尔排序的效率

9.总结

前言

之前我们衡量一个算法的效率时，都是着眼于它在最坏情况下需要多少步。原因很简单，连最坏的情况都做足准备了，其他情况自然不在话下。

但是，在我们实际生活中并不总是面临最坏情况，更多的是平均情况。本章我们会见证一种自适应性极强的排序算法---希尔排序，还有它的组成它的关键---插入排序。

正文

1插入排序

我们已经学过两种排序算法：冒泡排序和选择排序。虽然它们的效率都是 O(N^2 )，但其实选择排序比冒泡排序快一倍。

现在来学第三种排序算法——插入排序（直接插入排序）。你会发现，顾及最坏情况以外的场景将是多么有用。插入排序包括以下步骤。

插入排序包括以下步骤。

(1) 在第一轮里，暂时将索引 1（第 2格）的值移走，并用一个临时变量来保存它。这使得该索引处留下一个空隙，因为它不包含值。

在之后的轮回，我们会移走后面索引的值。

(2) 接着便是平移阶段，我们会拿空隙左侧的每一个值与临时变量的值进行比较。

如果空隙左侧的值大于临时变量的值，则将该值右移一格。

随着值右移，空隙会左移。如果遇到比临时变量小的值，或者空隙已经到了数组的最左端，就结束平移阶段。

(3) 将临时移走的值插入当前空隙。

(4) 重复第(1)至(3)步，直至数组完全有序。

2.插入排序实战

下面尝试对 [4, 2, 7, 1, 3] 数组运用插入排序。

第 1轮先从索引 1开始，其值为 2。

准备工作：暂时移走 2，并将其保存在变量 tmp 中。图中被移到数组上方的就是

tmp。

第 1步：比较 4与 tmp中的 2。

第 2步：因为 4大于 2，所以把 4右移。

于是空隙移到了数组最左端，没有其他值可以比较了。

第 3步：将 tmp插回数组，完成第一轮。

开始第 2轮。

准备工作：暂时移走索引 2的值，并保存到 tmp中。于是 tmp等于 7。

第 4步：比较 4与 tmp。

4小于 7，所以无须平移。因为遇到了小于 tmp的值，所以平移阶段结束。

第 5步：将 tmp插回到空隙中，结束第 2轮。

开始第 3轮。

准备工作：暂时移走 1，并将其保存到 tmp中。

第 6步：比较 7与 tmp。

第 7步：7大于 1，于是将 7右移。

第 8步：比较 4与 tmp。

第 9步：4大于 1，于是也要将 4右移。

第 10步：比较 2与 tmp。

第 11步：2比较大，所以将 2右移。

第 12步：空隙到了数组最左端，因此我们将 tmp插进去，结束这一轮。

开始第 4轮。

准备工作：暂时移走索引 4的值 3，保存到 tmp中。

第 13步：比较 7和 tmp。

第 14步：7更大，于是将 7右移。

第 15步：比较 4与 tmp。

第 16步：4大于 3，所以将 4右移。

第 17步：比较 2与 tmp。2 小于 3，于是平移阶段完成。

第 18步：把 tmp插回到空隙。

至此整个数组都排好序了。

3.插入排序的实现

以下使用C语言实现的直接插入排序：

void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    int tmp = a[end + 1];
    while (end >= 0)
    {
      if (a[end] > tmp)         //大于tmp，往后挪一个
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;          //把tmp插入空隙
  }
}

让我们一步步来讲解：

for (int i = 0; i < n - 1; i++)

最外层的这个循环用来控制end的位置，也就是一个轮回。

    int end = i;
    int tmp = a[end + 1];

我们通过控制end的位置，使end与end之前的数列都是有序的，而把end+1索引处的值（也就是tmp）插入到end之前的数列中。所以，end的值是从0开始的。这样能保证end与end之前的数列是有序的（因为只有一个数），那么将tmp插入后，前end+1个数都是有序的，再依次执行下去。

while (end >= 0)

end索引处的值会发生移动，最坏的情况是tmp的值比之前的有序数列中每一个值都要小，那么空隙的位置就在end=0处。例如：

            if (a[end] > tmp)         //大于tmp，往后挪一个
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }

找到空隙，将比tmp大的数字不断往后挪，直到找到小于等于tmp的数字。

a[end + 1] = tmp;          //把tmp插入空隙

将tmp插入空隙。

4.插入排序的效率

插入排序包含 4种步骤：移除、比较、平移和插入。要分析插入算法的效率，就得把每种步骤都统计一遍。

首先看看比较。每次拿 tmp跟空隙左侧的值比大小就是比较。

在数组完全逆序的最坏情况下，我们每一轮都要将 tmp左侧的所有值与tmp比较。因为那些值全都大于 tmp，所以每一轮都要等到空隙移到最左端才能结束。

对于含有N个元素的数组，可以得出比较的总次数为：

1 + 2 + 3 + … + N - 1 次。

接下来看看其他几种步骤。

我们每次将值右移一格，就是平移操作。当数组完全逆序时，有多少次比较就要多少次平移，因为每次比较的结果都会使你将值右移。

因而可以得出平移的总次数为：

1 + 2 + 3 + … + N - 1 次。

tmp的移除跟插入在每一轮里都会各发生一次。因为总是有 N - 1轮，所以可以得出结论：有 N - 1次移除和 N - 1次插入。

把它们都相加。

N^2 比较和平移的合计

+ N - 1 次移除

+ N - 1 次插入

=

N^2 + 2N - 2步

我们已经知道大 O有一条重要规则——忽略常数，于是你可能会将其简化成 O(N^2 + N)。不过，现在来学习一下大 O的另一条重要规则：

大 O 只保留最高阶的 N。

换句话说，如果有个算法需要 N^4 + N^3 + N^2 + N步，我们就只会关注其中的 N^4 ，即以 O(N^4 )

来表示。为什么呢？

请看下表。

随着 N的变大，N^4 的增长越来越抛离其他阶。当 N为 1000时，N^4 就比 N^3 大了 1000倍。因

此，我们只关心最高阶的 N。

所以在插入排序的例子中，O(N^2 + N)还得进一步简化成 O(N^2 )。

不过上一章曾指出，虽然冒泡排序和选择排序都是 O(N^2 )，但选择排序实际上是 N^2 / 2步，

比 N 2 步的冒泡排序更快。乍一看，你可能会觉得插入排序跟冒泡排序一样，因为它们都是 O(N^2 )，其实插入排序是 N^2 + 2N - 2步。你或许会认为比冒泡排序和插入排序快一倍的选择排序是三者中最优的，但事情并没有这么简单。