简介

插入排序就是将要排序的元素插入到曾经排序的数组中，从而造成一个新的排好序的数组。

这个算法就叫做插入排序。

插入排序的例子

同样的，如果咱们有一个数组：29,10,14,37,20,25,44,15，怎么对它进行插入排序呢？

先看一个插入排序的动画，对它有个直观的理解：

咱们来剖析一下排序的流程。

八个数字，咱们分为7轮。

第一轮，假如29是曾经排好序的数组，从第二个元素开始，向排好序的数组插入新的元素。 也就是说向数组[29]插入10。失去[10,29]。

第二轮，[10,29]曾经排好序了，抉择数组中的第三个元素14，插入排好序的数组[10,29]。

先将29和14比拟，发现29>14,则将29右移一位[10, ,29],而后比拟10和14，发现10小于14，那么将14插入10前面[10,14,29]，以此类推。

插入排序的java程序

咱们看下java程序怎么写：

public class InsertionSort {    public void doInsertSort(int[] array){        log.info("排序前的数组为:{}",array);        int n = array.length;        //从第二个元素开始插入        for (int i = 1; i < n; ++i) {            int key = array[i];            int j = i - 1;            //j示意的是要插入元素之前的曾经排好序的数组            //曾经排好序的数组，从后向前和要插入的数据比拟，如果比要插入的数据大，须要右移一位            while (j >= 0 && array[j] > key) {                array[j + 1] = array[j];                    j = j - 1;            }            //最初的j+1的地位就是须要插入新元素的地位            array[j + 1] = key;            log.info("第{}轮排序后的数组为:{}", i+1, array);        }    }    public static void main(String[] args) {        int[] array= {29,10,14,37,20,25,44,15};        InsertionSort insertionSort=new InsertionSort();        insertionSort.doInsertSort(array);    }}

运行后果：

插入排序的工夫复杂度

从代码中咱们能够看到，插入排序有一个for循环，在for循环中还有一个while循环。

所以插入排序的工夫复杂度也是O(n²)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-insertion-sort/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」,懂技术，更懂你！