java 实现排序算法之「插入排序」

java 实现排序算法系列

这是 Java 实现排序算法的第三篇文章——插入排序算法。插入排序可以说成是「一类」简单的排序算法，因为插入排序可以有变种，比如二分查找插入排序算法，本文讲述的是直接插入排序。

如文中出现错误，请在公众号「ikook」聊天窗口留言，十分感谢。

插入排序

插入排序「Insertion Sort」是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

来看一下插入排序算法的思路：

• 将需排序的数据分成已排序和未排序两部分，从第一个元素开始，并将该元素看做已排序。
  
  
• 取得下一个元素，即第二个元素，在已排序的序列中由后向前扫描，找出合适的位置将该元素插入。
  
  
• 重复上述步骤，直到最后一个元素被插入到已排序序列中。
  
  
• 排序完成。
  
  

使用插入排序为一列数字进行排序的过程示意图（来自维基百科）：

<center>

</center>

插入排序算法示意图（来自维基百科）：

<center>

</center>

代码实现

从上面可以看到，算法思路非常简单，但是代码就不那么简单易写了。算法本身是没有问题的，之所以不易写我觉得是由于编程语言的问题。这里我们使用 Java 来实现，那就拿 Java 来讲。

在上述思路中我们可以提出几个问题，先来看下。首先，我们该如何判断合适的位置？边界条件该怎么处理？在数组中插入元素，必然会移动数据，如何控制数据的移动？

为了解决这些问题，我们可以在算法思路的第二步做手脚，将第二步细化。我们不在已排序的序列起始位置开始比较，从已排序序列的尾部开始逆序比较，只要比待插入的数据大，那就向后移动，直到不大于该数据，此时空出来的位置就放入待插入数据。

上代码：

private static void insertionSort(int[] arr){
      for (int i=1; i<arr.length; i++){
          int value = arr[i];
          int position=i;
          while (position>0 && arr[position-1]>value){
              arr[position] = arr[position-1];
              position--;
          }
          arr[position] = value;
      }
}

如果在代码的理解上遇到困难，可以利用 IDE 的调试功能来学习。如下图（IntelliJ IDEA）：

<center>

</center>

算法复杂度

从上述内容容易看出，无论输入的数据怎样，插入排序算法总会进行 n-1 次排序。

由于每个元素插入点的不确定性，该算法复杂度并不是一定的。假设我们要将 n 个元素的序列升序排序，这时存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了（即数据本身的顺序和我们需要的顺序相同）。此时，需要进行的比较操作需（n-1）次即可，时间复杂度为 O(n)。

最坏情况很显然，序列为逆序排列时，即降序排序时为最坏。此时，需要进行的比较共有 1/2n(n-1) 次，时间复杂度为 O(n^2)。

平均来说，插入排序算法复杂度为 O(n^2)。插入排序的赋值操作是比较操作的次数加上（n-1）次。

空间复杂度，插入排序所有的数据移动均在内部进行，唯一的开销是我们使用了一个临时变量，则空间复杂度为 O(1)。

插入排序算法分析

算法稳定性：
拿本文中的例子来讲，只需要找到需插入元素的位置即可，并不需要交换，则直接插入排序是稳定排序算法。

适用场景：
从算法复杂度可以看出，该排序算法不适合数据较大的情况，数量级小于千时，插入排序是一个不错的选择。在 STL 的 sort 算法和 stdlib 的 qsort 算法中，都将插入排序作为快速排序的补充，用于少量数据的排序。

其他

关于插入排序算法的变种大家有兴趣的自己 Google 一下，本文只讲述了基本的直接插入排序。插入排序的变种大概有这几种：二分查找插入排序、2 - 路插入排序、表插入排序。二分查找插入排序有的文献叫做折半插入排序，2 - 路插入排序和表插入排序可以参考《数据结构》（严蔚敏、吴伟民著）一书。

完。

相关阅读：
Java 实现「冒泡排序」
Java 实现「选择排序」

PS：如果你觉得本文对你有一点帮助，点赞、转发，不胜感激。