【算法】插入排序算法的讲解和代码实践

思路

有数组[26, -3, 14, -15, 0, 324, 98, 1, 22]
现对该数组进行排序，使用插入排序算法。
先来屡一下思路和步骤：

1. 从下标为1的元素开始进行遍历；
2. 如果它前面的元素比它大，那么将前面的元素进行后移，并记录下标；
3. 直至遇见小于等于它的数，将当前元素插入上面记录的下标中。

讲解

第一步，记录当前元素（从下标为1的元素开始），即 -3；插入下标初始化为 -1。

image.png

第二步，将 -3 前面的所有元素与 -3 进行对比，大于 -3 的，进行后移，并将后移元素的下标赋值到插入下标中：

image.png

第三步，将当前元素 -3 插入到插入下标的位置：

image.png

这样就完成了一个元素的插入排序。以此类推即可完成整个数组排序。

实现

    @Test
    public void sortTest() {
        int[] nums = new int[]{26, -3, 14, -15, 0, 324, 98, 1, 22};
        insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void insertSort(int[] nums) {
        if (nums.length < 2) {
            return;
        }
        // 从下标为1的元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 记录当前元素
            int cur = nums[i];
            // 初始化插入下标为-1
            int insertIndex = -1;
            // 遍历当前元素前面的所有元素
            for (int j = i - 1; j >= 0; j--) {
                // 如果前面的某个元素大于当前元素，则前面的元素后移一位
                if (nums[j] > cur) {
                    // 元素后移
                    nums[j + 1] = nums[j];
                    // 记录插入下标
                    insertIndex = j;
                }
            }
            // 如果插入下标不等于-1，将当前元素赋值到插入下标
            if (insertIndex != -1) {
                nums[insertIndex] = cur;
            }
        }
    }

看一下运行结果：

image.png

这样插入排序就实现完成了。