插入排序就是这么容易

welcome rodert一插入排序（Insertion Sort）

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

一介绍

image

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

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

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

一实现

算法描述：

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

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

动态图演示：

image

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

image

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);
        }
    }