人生有涯，学海无涯
前面跟大家分享的排序算法之快速排序，今天跟大家分享另外一个排序算法——插入排序。插入排序可能大家在平时真正用到地方不多，但是也会用到，而且有一个场景我想大家一定经历过，那就打扑克牌。想想我们在抓牌的时候，是不是随着拿到一张张的扑克牌，然后按照顺序插入我们左手呢（或者右手上）？这其实就是插入排序，通过依次比较前一个数字的大小，将需要排序的数字插到最适合的位置，下面我们一起看下吧。
01、插入排序
我们先看看维基百科的解释:
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
02、算法思想
插入排序的算法思想是通过构建有序序列，对未排序的数据从有序队列中依次进行比较，找到相应的位置进行插入。注意，如果当前位置不满足的情况下是需要将该位置的元素进行后移，以便腾出位置。
插入排序算法的实现大致分成三步
- 获取待插入的元素：
- 将待插入的元素与前一个元素进行比较；
- 如果当前元素与待插入元素大则将当前元素进行后移，再依次比较。
03、算法实现
/** * <br> * <b>Function：</b><br> * <b>Author：</b>@author 子悠<br> * <b>Date：</b>2019-09-25 00:24<br> * <b>Desc：</b>无<br> */ publicclass InsertSort { public static void main(String[] args) { int[] array = newint[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1}; insertSort(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } } /** * 插入排序 * * @param array 待排序数组 */ public static void insertSort(int[] array) { for (int i = 0; i < array.length; i++) { //待插入的元素 int needInsert = array[i]; //开始比较的索引 int index = i - 1; while (index >= 0 && array[index] > needInsert) { //将该位置的元素进行后移 array[index + 1] = array[index]; //再比较该位置前一个元素 index--; } //当前位置满足条件 array[index + 1] = needInsert; } } }
运行结果：
1 1 2 2 3 3 4 5 6 7 8 8 9
从上面的代码我们可以看到，相对于快速排序，插入排序还是比较简单的，而且理解起来也相对容易，代码中已经增加了详细的注释，相信大家都能理解。注意的点就是每次在比较完之后，对于不满足的元素，我们需要进行一个后移，这个才能给待插入的元素在数组前面腾出空间。也就是代码的 array[index + 1] = array[index]; 这一行。
插入排序算法的最好时间复杂度，是序列本身就已经有序的情况下，是 O(n)，最坏的时间复杂度是 O(n^2)，平均时间复杂度也是 O(n^2)。由于没有申请额外的空间，所以空间复杂度为 O(1)。
插入排序算法在数据量不是很大的时候还是比较快速好用的，但是如果数据量很大就不建议采用插入排序了，可以采用变种的二分查找，有机会再给大家介绍，一般数据不超过千的时候都是可以使用的。
04、总结
这篇文章简单给大家介绍了一下插入排序的思想和实现，排序算法是大家日常工作和学习不可避免要学习的知识，我们《Java 极客技术》也会在后续的文章中慢慢的给大家分享很多优质的，算法和数据结构的文章，便于大家学习和成长。最后欢迎大家到我们《Java 极客技术》知识星球中一起学习和进步，扫描下放二维码还有优惠，我们在知识星球中等你。
