【排序算法】插入排序

1  前言

今天把排序的几个算法过一下，这节我们看一下插入排序，简单的来说就是从第2个元素往前寻找位置进行插入，我们看示例。

2  代码示例

/**
 * 插入排序
 * 从第2个元素开始，往前插入
 * 假设待排序的数量为：n
 * 要考虑的是：
 * 1、轮数还是 n-1 我们外层循环起始刚好是2 到 n
 * 2、内层循环就是 0 -> i，i即外层循环的索引
 */
public static void insertSort(int[] arr) {
    // 外层循环
    for (int i = 1; i < arr.length; i++) {
        // 升序，arr[i] 当前要插入的值发现比前边的最后一个元素都大说明不需要往前插入，跳过
        if (arr[i-1] < arr[i]) {
            continue;
        }
        // 记录要进行插入的值
        int temp = arr[i];
        // 记录内层循环的起始位置，从最后一个元素开始遍历
        int j = i-1;
        // 内层循环
        for (; j >= 0; j--) {
            // 升序，当发现有比我大的，就往后放
            if (arr[j] > temp) {
                arr[j+1] = arr[j];
                // 持续往后放
                continue;
            }
            // 发现有比我小的了，停止遍历
            break;
        }
        /**
         * 找到位置了，进行替换 这里为什么 +1？
         * 能走到这考虑两种情况：
         * 1、内层循环遍历到索引为 -1时停止的，也就是前边的所有元素都比待插入的大 比如 1 2 5 要插入 0 这是索引为-1 + 1 = 0就是要放入的位置
         * 2、找到一个比待插入的小了 比如 1 2 5 要插入 4 到 2 的时候停止了 这是索引为 1 所以+1 = 2就是要放入待插入的位置
         */
        arr[j+1] = temp;
    }
}
public static void main(String[] args) {
    int[] arr = IntStream.generate(() -> ThreadLocalRandom.current().nextInt(10000)).limit(10000).toArray();
    System.out.println("排序前：" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(",")));
    insertSort(arr);
    System.out.println("排序后：" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(",")));
}

3  小结

有写的不对的地方，欢迎指正哈。