基础知识
类型：是一种稳定的内部排序。
思路：将序列分为有序和无序两部分，将无序部分的元素依次插入到有序部分的适当位置，为了给待插入的元素留出位置，我们需要在插入之前，将插入位置之后的所有元素都向后移动一位。
步骤：
1.将第一个元素视作有序的部分
2.取出下一个元素，在已经排序好的序列中从后向前扫描
3.如果已排序的元素大于该新元素，继续向前扫描
4.重复步骤3，直到找到已排序的元素小于或等与该新元素
5.将新元素放在该已排序好的元素之后
6.重复步骤2~5
参考文章：Java实现八大排序算法
两种实现方式
方式一：通过将较大的元素都向右移动而不总是交换两个元素
取出已排序的元素序列后边第一个未排序元素（下标记为j），用临时变量保存起来，通过比较待排序元素与arr[j-1]大小，以arr[j]=arr[j-1]的方式，将已排序的其他元素向后移动一位，最后找到合适位置将临时变量保存的未排序元素保存起来。
public static void insertSort1(int[] array) {
int [] arr=array.clone();
long start = System.currentTimeMillis();
for (int i = 1; i < arr.length; i++) { //执行次数：n
int tem = arr[i]; //执行次数：n
int j = i; //执行次数：n
//下方tem < arr[j - 1]易出错，容易写成arr[j]< arr[j - 1]
while (j > 0 && tem < arr[j - 1]) { //执行次数：最大n 最小1
arr[j] = arr[j - 1]; //执行次数：最大n 最小1
j--; //执行次数：最大n 最小1
}
arr[j] = tem;//执行次数：n
}
long end = System.currentTimeMillis();
System.out.println("insertSort1排序用时==" + (end - start));
//执行次数：最高：(n+n+n+n)*(n+n+n)=12n² 最低：(n+n+n+n)*(1+1+1)+n=12n
}
方式二：通过交换进行插入排序，借鉴冒泡排序
内层for循环是对已排序好的再加一个当前正在找位置的元素组成的序列的逆序遍历,从最后一位开始跟前一个元素比较，若比前一位小，就交换
public static void insertSort2(int[] array) {
int [] arr=array.clone();
long start = System.currentTimeMillis();
for (int i = 0; i < arr.length - 1; i++) { //执行次数：n
for (int j = i + 1; j > 0; j--) { //执行次数：n
if (arr[j] < arr[j - 1]) { //执行次数：1
int tem = arr[j]; //执行次数：最大1 最小0
arr[j] = arr[j - 1]; //执行次数：最大1 最小0
arr[j - 1] = tem; //执行次数：最大1 最小0
}
}
//执行次数：最多：n*(n+1+1+1+1)=n²+4n 最少：n*(n+1)=n²+n
}
long end = System.currentTimeMillis();
System.out.println("insertSort2排序用时==" + (end - start));
}
两种实现方式时间复杂度对比
通过以下代码测试三种情况下两种方式的耗时情况。
public static void main(String[] args) {
int[] arr = new int[100000];
for (int i = 0; i < 100000; i++) {
// 模拟乱序的数组
arr[i] = new Random().nextInt();
// 模拟倒序数组
// arr[i] = 100000-i;
// 模拟原本就有序的数组
// arr[i] = i;
}
insertSort1(arr);
insertSort2(arr);
}
第一种情况：乱序的数组
运行三次main方法，分别得到以下数据：
第一次：insertSort1排序用时==1189， insertSort2排序用时==8330
第二次：insertSort1排序用时==1154， insertSort2排序用时==8122
第三次：insertSort1排序用时==1208， insertSort2排序用时==8124
总体来看，对于乱序的数组，insertSort1要优于insertSort2。
第二种情况：倒序的数组
运行三次main方法，分别得到以下数据：
第一次：insertSort1排序用时==2099，insertSort2排序用时==3300
第二次：insertSort1排序用时==2118，insertSort2排序用时==3310
第三次：insertSort1排序用时==2004，insertSort2排序用时==3231
总体来看，对于倒序的数组，insertSort1要略优于insertSort2。
第三种情况：有序的数组
运行三次main方法，分别得到以下数据：
第一次：insertSort1排序用时==4，insertSort2排序用时==2040
第二次：insertSort1排序用时==3，insertSort2排序用时==2022
第三次：insertSort1排序用时==4，insertSort2排序用时==2121
总体来看，对于原本有序的数组，insertSort1要远远优于insertSort2。
参考文章：Java实现八大排序算法
