java-插值排序的简单理解

核心思想是，找到无序开始的地方，依次从无序中取出一个元素插入到已经排序完成的地方，插入的方式是两两比较调换位置

package sample.main.onlyt.suanfa;

public class chazhipaixu {
    public static void main(String[] args) {
        //数组
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        //1.找到无序的那一组数据是从哪个索引开始的
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[i + 1]) {
                startIndex = i + 1;//表示有序的数据到i下标就结束了
                break;
            }
        }
        System.out.println("无序从这里开始："+startIndex);

        //2.遍历从startIndex开始到最后一个元素，依次得到无序的那一组数据中的每一个数据
        for (int i = startIndex; i < arr.length; i++) {
            //记录当前要插入数据的索引
            int cur = i;

            System.out.println("当cur是"+cur);
            while (cur > 0 && arr[cur] < arr[cur - 1]) {
                System.out.println("====后面的数大于前面的数，需要调换"+arr[cur]+" "+arr[cur-1]);
                //交换位置
                int tmp = arr[cur];
                arr[cur] = arr[cur - 1];
                arr[cur - 1] = tmp;
                System.out.println("结果是：");
                printArr(arr);
                cur--;
            }
        }
        printArr(arr);

    }
    private static void printArr(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

运行结果就很容易理解：

无序从这里开始：2
当cur是2
====后面的数大于前面的数，需要调换38 44
结果是：
3 38 44 5 47 15 36 26 27 2 46 4 19 50 48 
当cur是3
====后面的数大于前面的数，需要调换5 44
结果是：
3 38 5 44 47 15 36 26 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换5 38
结果是：
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48 
当cur是4
当cur是5
====后面的数大于前面的数，需要调换15 47
结果是：
3 5 38 44 15 47 36 26 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换15 44
结果是：
3 5 38 15 44 47 36 26 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换15 38
结果是：
3 5 15 38 44 47 36 26 27 2 46 4 19 50 48 
当cur是6
====后面的数大于前面的数，需要调换36 47
结果是：
3 5 15 38 44 36 47 26 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换36 44
结果是：
3 5 15 38 36 44 47 26 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换36 38
结果是：
3 5 15 36 38 44 47 26 27 2 46 4 19 50 48 
当cur是7
====后面的数大于前面的数，需要调换26 47
结果是：
3 5 15 36 38 44 26 47 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换26 44
结果是：
3 5 15 36 38 26 44 47 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换26 38
结果是：
3 5 15 36 26 38 44 47 27 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换26 36
结果是：
3 5 15 26 36 38 44 47 27 2 46 4 19 50 48 
当cur是8
====后面的数大于前面的数，需要调换27 47
结果是：
3 5 15 26 36 38 44 27 47 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换27 44
结果是：
3 5 15 26 36 38 27 44 47 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换27 38
结果是：
3 5 15 26 36 27 38 44 47 2 46 4 19 50 48 
====后面的数大于前面的数，需要调换27 36
结果是：
3 5 15 26 27 36 38 44 47 2 46 4 19 50 48 
当cur是9
====后面的数大于前面的数，需要调换2 47
结果是：
3 5 15 26 27 36 38 44 2 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 44
结果是：
3 5 15 26 27 36 38 2 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 38
结果是：
3 5 15 26 27 36 2 38 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 36
结果是：
3 5 15 26 27 2 36 38 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 27
结果是：
3 5 15 26 2 27 36 38 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 26
结果是：
3 5 15 2 26 27 36 38 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 15
结果是：
3 5 2 15 26 27 36 38 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 5
结果是：
3 2 5 15 26 27 36 38 44 47 46 4 19 50 48 
====后面的数大于前面的数，需要调换2 3
结果是：
2 3 5 15 26 27 36 38 44 47 46 4 19 50 48 
当cur是10
====后面的数大于前面的数，需要调换46 47
结果是：
2 3 5 15 26 27 36 38 44 46 47 4 19 50 48 
当cur是11
====后面的数大于前面的数，需要调换4 47
结果是：
2 3 5 15 26 27 36 38 44 46 4 47 19 50 48 
====后面的数大于前面的数，需要调换4 46
结果是：
2 3 5 15 26 27 36 38 44 4 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 44
结果是：
2 3 5 15 26 27 36 38 4 44 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 38
结果是：
2 3 5 15 26 27 36 4 38 44 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 36
结果是：
2 3 5 15 26 27 4 36 38 44 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 27
结果是：
2 3 5 15 26 4 27 36 38 44 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 26
结果是：
2 3 5 15 4 26 27 36 38 44 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 15
结果是：
2 3 5 4 15 26 27 36 38 44 46 47 19 50 48 
====后面的数大于前面的数，需要调换4 5
结果是：
2 3 4 5 15 26 27 36 38 44 46 47 19 50 48 
当cur是12
====后面的数大于前面的数，需要调换19 47
结果是：
2 3 4 5 15 26 27 36 38 44 46 19 47 50 48 
====后面的数大于前面的数，需要调换19 46
结果是：
2 3 4 5 15 26 27 36 38 44 19 46 47 50 48 
====后面的数大于前面的数，需要调换19 44
结果是：
2 3 4 5 15 26 27 36 38 19 44 46 47 50 48 
====后面的数大于前面的数，需要调换19 38
结果是：
2 3 4 5 15 26 27 36 19 38 44 46 47 50 48 
====后面的数大于前面的数，需要调换19 36
结果是：
2 3 4 5 15 26 27 19 36 38 44 46 47 50 48 
====后面的数大于前面的数，需要调换19 27
结果是：
2 3 4 5 15 26 19 27 36 38 44 46 47 50 48 
====后面的数大于前面的数，需要调换19 26
结果是：
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48 
当cur是13
当cur是14
====后面的数大于前面的数，需要调换48 50
结果是：
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50 
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50 

参考
https://blog.csdn.net/qq_64743563/article/details/131735509