插入排序（Java实现）

前言

    稳定性：如果一个排序是稳定的，是可以变成不稳定的，此时这个排序归结为稳定，但是如果这个排序本身是不稳定的，是不可以变成稳定的，此时这个排序是不稳定的。

    过程：如果数组中只有一个元素，这个数组当前就是有序的，当数组中有多个元素，要对其进行插入排序，此时就可以定义一个下标 i，来控制比较的元素，可以将 i 放到 tmp 中，然后 j 控制被比较的元素，一直比较的是 i 和 i 下标之前的所有的元素。

// 插入排序
    // 过程 arr[1]元素放到tmp中，j下标控制数组前边的元素去和tmp中的值去比较
    // 如果比 tmp 中的值大，此时让所有大的值往后挪动即可
    /* 时间复杂度：O（N ^ 2）  最好时间复杂度：O（N）（也就是当数据接近有序的时候排序速度非常快）
       所以一般的场景就是数据基本有序的时候就用 插入排序
    * */
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (tmp < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    arr[j + 1] = tmp;
                    break;
                }
                // 正常情况下，数组中最后一个元素是最小的，此时应该将这个元素放到最前边
                // 但是 j 下标是负数了，此时跳出循环了，所以就应该将tmp的最小值放到 j + 1 下标的位置上
                arr[j + 1] = tmp;
            }
        }
    }