1.什么是插入排序
- 每一步将一个待排序的数据插入到前面已经排序好的有序序列里，直到插完所有的元素为止。
- 插入排序与打扑克牌很类似，你摸到第一张牌的时候是不需要排序的，后续摸到的牌可以根据第一张牌进行向左或者向右排序。
- 算法实现
- 直接插入排序是把无序的序列里的数据插入到有序的序列中去。
- 在遍历无序序列的时候，首先拿无序序列里的第一个元素跟有序序列里的每一个元素比较，并且插入到合适的位置，一直到无序序列里的所有元素插入完毕为止。
2.插入排序算法图解
- 初始化序列如下所示，分为有序序列（没有任何元素）和无序序列（8,2,6,4,3,7,5），一开始有序序列是没有任何元素的。
- 第一轮用8和2比较，返现2比8小，交换位置，变成2 8
- 第二轮用8和6比较，交换位置，然后再用2和6比较，发现6比2大不用交换位置变成 2 6 8
- 第三轮用8和4比较，交换位置，再用6和4比较交换位置，2和4比较不用交换位置
- 第四轮8和3比较，交换位置，6和3比较交换位置，4和3比较交换位置，2和3比较不用交换位置
- 后面以此类推，都是向左比较到第一个元素，也就是当前元素左边都是有序的，右边都是无序的
3.插入排序代码实现
（1）整体编码实现
public class InsertSort {
public static void main(String[] args) {
int[] arr = {8,2,6,4,3,7,5};
System.out.println("排序前：");
System.out.println(Arrays.toString(arr));
insertSort(arr);
System.out.println("排序后：");
System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr){
//第一层循环，把数组分成两部分，左边是已将排好序的，右边是未排序的
//当前下表左边的元素已经排好序，右边还未排序
for (int i = 1; i < arr.length; i++) {
//内层循环，从当前下标开始祥左比较，如果发现比左边元素小就惊醒交换
//直到比较到左边第一个元素
for (int j = i; j > 0; j--) {
//依次交换，依次比较，如果不比前一个元素小，就跳出
if(arr[j-1]>arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}else{
break;
}
}
System.out.println("第 "+i+" 轮: "+Arrays.toString(arr));
}
}
}（2）代码测试
