[数据结构与算法]记直接插入排序，为什么必须从后往前遍历

从前往后遍历找到插入位置

@Slf4j
public class InsertSort {

    @Test
    public void test() {
        int[] arr = new int[]{5, 3, 7, 6, 4, 1, 0, 2, 9, 8};
        log.info("init: {}", Arrays.toString(arr));
        insertSort(arr);
        log.info("result: {}", Arrays.toString(arr));
    }

    /**
     * null就NPE
     */
    public void insertSort(int[] arr) {
        if (arr.length < 2)
            return;

        for (int i = 1; i < arr.length; i++) { // arr[i]为待排序值
            for (int j = 0; j < i; j++) { // 从前往后遍历，找待插入的位置
                if (arr[j] > arr[i]) { // 找到插入的位置。用>号保证稳定性。
                    int val = arr[i];
                    for (int k = i; k > j; k--) // 从后往前移动数组内容
                        arr[k] = arr[k - 1];

                    arr[j] = val; // 放入待排序值
                    break;
                }
            }
        }
    }
}

从后往前遍历找到插入位置

/**
 * 借鉴了网上的插入排序，重新写了一个
 * 这个是从后往前比较，
 * 直观看起来少一重循环
 */
@Slf4j
public class InsertSort_ {

    @Test
    public void test() {
        int[] arr = new int[]{5, 3, 7, 6, 4, 1, 0, 2, 9, 8};
        log.info("init: {}", Arrays.toString(arr));
        insertSort(arr);
        log.info("result: {}", Arrays.toString(arr));
    }

    public void insertSort(int[] arr) {
        if (arr.length < 2)
            return;

        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];

            int j = i - 1;
            while (j >= 0 && tmp < arr[j]) // 从后往前扫描，找到待插入的位置。同时移动数组内容
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }
}

区别与分析

直观看起来，从后往前遍历，比从前往后遍历，少了一重循环。

从原理上来分析，就是从前往后遍历来找到插入位置，这一重循环，其实是无效代码。

因为后面还要位移数组，需要将后半部分再遍历一遍，就相当于遍历了整个已排序部分。

因此在后续较大长度的数组测试中，算法性能也会相对低效。