算法入门 - 插入排序

大多数半路出家的算法学习者都是从排序开始入手，一方面一个完整的算法教程都会以排序为开头，一方面排序相对简单，没有很多烧脑的操作，也是其他进阶算法的基础，很重要。但作为一名 Java 打字员，很多时候我会直接用集合自带的 sort 方法而不是自己去写一个。排序量一般情况下不太大，如果真的有大量的数据需要排序，在数据库这一侧也解决一大部分，毕竟 API 的超时时间有限，要保性能还是有很多算法之外的东西可以使用。

总之学习排序算法的用处首先是熟悉算法的思维，了解什么时候是 O(n)，什么时候是 O(n^2)，同时为以后更复杂的算法打好基础，毕竟面试的时候要手写，而且不会是排序这么简单的题目。几大排序算法，可能最简单的冒泡排序，就是暴力便利，小的往前放，大的往后放，复杂度为 O(n^2)。但今天介绍一个对之后的学习更有帮助的排序：插入排序。

算法思路

先介绍一下这个算法的思路：

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置后

6. 重复步骤 2~5

通过下面的动画可以理解整个排序的过程：

复杂度与适用场景

首先肯定要把这个列表遍历一遍，不断对比大小，这至少是个 O(n)了。然后每次取出的元素都要跟之前已经排序好的列表再遍历对比一次，最坏的情况也是 n 次对比，所以最终插入的排序的复杂度为 O(n^2)。对于这样的指数级复杂度的算法我们不是应该摒弃吗，也不一定。这里最坏的情况才是指数，如果一个列表大部分是已经排序的，那用插入排序可以收获惊人的 O(n)，这是很多算法都难以企及的，在一些标准库中，插入排序也是快速排序的替补，足见其在特定场景下的用处。

实现

简单写了个实现，仅供参考。

public static void sort(Integer[] arr, Integer size) {    for (int i = 1; i < size; i++) {
        int e = arr[i]; //临时变量存储当前的游标值        int j; //最终应该存放当前游标值的位置        for (j = i; j > 0 && (arr[j - 1] > e); j--) { //前一个值是否比当前游标值要大，满足条件才进行赋值            arr[j] = arr[j - 1];        }        arr[j] = e;    }}