插入排序（Insertion sort）

算法原理

假定第一个数字最小（升序排列），从第二个数字开始（每一次选定的数字范围向后递增，第一次只比较前两个数字，第二次前三个…以此类推），依次将数字插入到它应该放置的位置。（暂未选定的其余数字不参与排序，每次换位的数字为最后一位，第一次为第二个，第二次第三个…以此类推）

5 4 9 1 —— 4 5 9 1 —— 4 5 9 1 —— 1 4 5 9

注意事项：

编码时可以先将1存在临时变量中，并将4 5 9向右移位后再将1放入指定位置，不用每次换位都存一次1，可以略微提高代码执行速度

当进行到最后一步时 例如数组内容为（1 2 4 3 5 —— 1 2 3 4 5）时，由于3 > 2，所以循环可以终止，因为左侧部分已经有序

随着排序进行，需要对比和换位的操作均可能减少，所以，插入排序的效率要明显高于冒泡与插入排序

当仅有一个数组元素时不会进行排序，所以，插入排序需要的比较轮次为

数组长度 - 1

每一轮的比较换位次数随数组内元素开始顺序不同而随之改变，具体范围为（0~比较轮次）

实现步骤

import java.util.Arrays;
import java.util.Random;

public class SelectionSort {
    public static void main(String[] args) {
        Random rd = new Random();
        //生成数组
        int[] arr = new int[rd.nextInt(100)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rd.nextInt(500);
        }
        System.out.println(Arrays.toString(arr));
        int tem;//存储临时数据
        int swapCount = 0;//换位次数
        int compareCount = 0;//对比次数
        long start = System.currentTimeMillis();//开始时间
        //开始插入排序
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]){
                    tem = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tem;
                    swapCount++;
                }else {
                    break;
                }
                compareCount++;
                //System.out.println(Arrays.toString(arr));//输出每次比较换位的结果
            }
            //System.out.println(Arrays.toString(arr));//输出每轮的结果
        }
        long end = System.currentTimeMillis();//结束时间
        long time = end - start;
        System.out.println(Arrays.toString(arr));//最终结果
        System.out.println("换位次数为"+swapCount);
        System.out.println("对比次数为"+compareCount);
        System.out.println("执行时间为"+time+"ms");
    }
}