愚昧者怨天尤人，无能者长吁短叹，儒弱者颓然放弃。

插入排序就是这么容易

welcome rodert一插入排序（Insertion Sort）

各位工作了的大佬们，日常工作可能都使用各种类库、工具，处理了需要处理的问题，一起来看看基础算法。

一详情

【百度百科】：插入排序，一般也被称为直接插入排序。对于一些元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

实质：插入排序的代码实现尽管没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易了解的了，由于只需打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度： O(N^(1-2))

一实现

算法形容：

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（假如待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

动态图演示：

选择排序流程图图片来源百度

Java代码实现

    @Test    public void insertionSort() {        int[] arr = {2, 0, 7, 3, 9};        for (int i = 1; i < arr.length; i++) {            // 记录要插入的数据            int tmp = arr[i];            // 从已经排序的序列最右边的开始比较，找到比其小的数            int j = i;            while (j > 0 && tmp < arr[j - 1]) {                arr[j] = arr[j - 1];                j--;            }            // 存在比其小的数，插入            if (j != i) {                arr[j] = tmp;            }        }        // 打印排序后结果        for (int i : arr) {            System.out.println(i);        }    }

优化

说明：
插入排序会将之前的所有的比它大的元素进行两两交换（从小到大排列的排序），会添加少量交换时间，降低运行效率，下面我们来探讨一下它的优化算法，
不是进行两两交换，而是把当前待插入的元素取出，让当前元素与之前的所有元素进行逐个比较，前一个元素大于当前元素直接覆盖，而到了最后当找到当
前元素的合适位置时只要要一次交换就可。

如序列：

【3 5 2 1 4】

元素5先存入临时变量temp中，跟前面元素比较，比前面元素大，而后拿出下一个元素2存入临时变量temp中，2与前一个元素5比较，2比5小，用5直接覆盖2

结果序列为：3 5 5 1 4 temp=2，而后temp再与前一个元素3进行比较，发现2比3小，而后3再覆盖刚才的位置，序列为3 3 5 1 4这时发现已经到序列的头部了，

而后将temp=2复制给arr[0]，就是直接覆盖第一个元素3，序列变为2 3 5 1 4，第一轮排序结束，跟直接插入排序太大的区别，只不过是减少了不断交换的次数

用直接复制覆盖取代，这样当数据量特别大时效率就会提高很多。

Java代码

    @Test    public void insertionSort2() {        int[] arr = {3, 5, 2, 1, 4};        //排序        for (int i = 1; i < arr.length; i++) {//从第2个元素开始遍历            int temp = arr[i];//将当前位置的元素取出            int j;            for (j = i; j > 0; j--) {                if (temp < arr[j - 1]) {//假如这个元素比temp大就覆盖，否则就证实该元素之前已经有序就break                    arr[j] = arr[j - 1];//直接用前一个元素进行覆盖                } else {                    break;                }            }            //将temp中的元素插入合适位置            arr[j] = temp;        }        // 打印排序后结果        for (int i : arr) {            System.out.println(i);        }    }

—END—rodert

更多文章后面会持续分享，有特别需要可以提前留言。