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

java 实现排序算法系列

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

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

插入排序

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

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

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

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

插入排序算法示意图(来自维基百科):

代码实现

从上面可以看到,算法思路非常简单,但是代码就不那么简单易写了。算法本身是没有问题的,之所以不易写我觉得是由于编程语言的问题。这里我们使用 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):

算法复杂度

从上述内容容易看出,无论输入的数据怎样,插入排序算法总会进行 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 实现「选择排序」