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

概述

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

本文是对基础的插入排序进行一个改进，解决插入排序数值交换过于频繁的问题，具体见下面的排序过程和代码（结合上一章更有利于理解这个插入排序算法改进的思想）

时间复杂度

O(n²)

排序过程

1. 初始化一个数组

   
   

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

   
   

3. 拷贝出第2个数的副本

   
   

4. 比较第2个数与第1个数的大小，如果第2个数更小，那就用第1个数直接覆盖第2个数

   
   

5. 将第2个数的副本赋值给第1个数

   
   

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

   
   

7. 拷贝出第3个数的副本

   
   

8. 比较第3个数与第2个数的大小，如果第3个数更小，那就用第2个数直接覆盖第3个数；
   继续比较第3个数与第1个数的大小，如果第3个数更小，那就用第1个数直接覆盖第2个数；

   
   
   

9. 将第3个数的副本赋值给第1个数

   
   

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

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

代码

public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int a = arr[i];
        int j;
        for (j = i; j > 0 && arr[j - 1] > a; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = a;
    }
}

性能测试

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

次数	性能
1	27ms
2	36ms
3	28ms
4	30ms
5	20ms

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

次数	性能
1	1107ms
2	1082ms
3	1097ms
4	1392ms
5	1265ms