插入排序，顾名思义，在排序的过程中有插入的操作，既然要做插入操作，那把需要插入的元素直接插入到应该在的位置，插入后就不需要再次对它进行排序了。

插入排序，将已有集合划分为有序集合和非有序集合两部分。默认第一个元素为有序集合，其他元素为非有序集合。

排序步骤

1、取非有序集合的第一个元素R
2、将元素R依次与有序集合的每一个元素进行比较，在有序集合的最后一个开始比较。
3、将大于R元素的元素后移一个位置
4、将元素R放到最后一个大于R元素的原位置
5、如上依次遍历所有非有序集合的所有元素，最终得到一个有序集合

image.png

JAVA对插入排序算法的实现：

  1. public class InsertSort {
  2.     @Test
  3.     public void insertSortTest(){
  4.         int[] arrays = {1,8,4,3,7,9,2,10};
  5.         insertSort(arrays);
  6.         for(int i : arrays) {
  7.             System.out.print(i+",");
  8.         }
  9.     }
  11.     /**
  12.      * 插入排序
  13.      * @param arrays  需要排序的整形数组
  14.      */
  15.     public void insertSort(int[] arrays){
  16.         int length = arrays.length;
  17.         //1、遍历无序集合
  18.         for(int r = 1 ; r < length ; r++){
  19.             int value = arrays[r];
  20.             //获取有序集合的最后一个元素的下标
  21.             int j = r - 1 ;
  22.             //倒叙遍历有序集合，方便移动元素
  23.             for( ; j >= 0 ; --j){
  24.                 //大于插入元素，则移动
  25.                 if(arrays[j] > value){
  26.                     arrays[j+1] = arrays[j];
  27.                 }else{
  28.                     break;
  29.                 }
  30.             }
  31.             arrays[j+1] = value;
  32.         }
  33.     }
  34. }
  1. 1,2,3,4,7,8,9,10

算法性能分析

时间复杂度： O(n*n)
空间复杂度： O(1)
算法稳定性： 稳定算法

和排序算法的比较：
1、冒泡排序的主要操作是对元素的比较和交换
2、插入排序的主要操作是对元素的比较和移动

所以两种排序算法的区别就在于交换和移动的区别，两种排序算法的实现，这两个动作的实现如下：

  1. 冒泡排序中数据的交换操作：
  2. if (a[j] > a[j+1]) { // 交换
  3.    int tmp = a[j];
  4.    a[j] = a[j+1];
  5.    a[j+1] = tmp;
  6.    flag = true;
  7. }
  9. 插入排序中数据的移动操作：
  10. if (a[j] > value) {
  11.   a[j+1] = a[j];  // 数据移动
  12. } else {
  13.   break;
  14. }

可以看出，冒泡排序的交换需要3次赋值操作，而插入排序只需要一次赋值操作。

为了实验，针对上面的冒泡排序和插入排序的 Java 代码，随机生成 10000 个数组，每个数组中包含 200 个数据，然后分别用冒泡和插入排序算法来排序，冒泡排序算法大约 700ms 才能执行完成，而插入排序只需要 100ms 左右就能搞定！