如需转载请评论或简信，并注明出处，未经允许不得转载

概述

插入排序就是从数组的第二位开始，不断的与前面一位数字进行比较，直到插入到合适位置的排序算法（类似扑克牌理牌）

时间复杂度

O(n²)

排序过程

1. 初始化一个数组

   
   

2. 找到数组中的第2个数（默认第一个数已经排好序）

   
   

3. 第2个数与第1个数进行比较，比第1个数小，交换位置

   
   

4. 找到数组中的第3个数

   
   

5. 第3个数与第2个数进行比较，比第2个数小，交换位置;
   紧接着又与第1个数比较，比第1个数小，继续交换位置

   
   

6. 找到数组中的第4个数
   ......

不断重复上述步骤，直到数组从小到大排列

代码

public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        //第i个数不断的与前一个数进行比较大小，比前一个数小则交换位置
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
            swap(arr, j - 1, j);
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

性能测试

随机生成10,000个从0到10,000的数，分别进行五次测试，效果如下

次数	性能
1	64ms
2	60ms
3	54ms
4	67ms
5	63ms

随机生成100,000个从0到100,000的数，分别进行五次测试，效果如下

次数	性能
1	5013ms
2	5066ms
3	5409ms
4	4459ms
5	5036ms

分析

插入排序和选择排序都是时间复杂度为O(n²)的排序算法，但是插入排序可以提前终止（如果当前数大于前面一个数），所以从循环次数少来说插入排序是要比选择排序更少的，但是从性能测试上看起来选择插入好像并没有比选择排序好多少，这是为什么呢？

因为插入排序需要非常频繁的交换位置，这显然也是有性能影响的，那怎么来解决这个问题呢？可以看排序算法 — 插入排序法（改进版）