【算法基础】:（三）插入排序

java基础算法

算法基础: 开始回顾下基础算法中的经典排序算法

插入排序

算法思想：一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

一、插入排序代码

public class 插入排序 {

    /**
     * @Description 从小到大
     * 循环开始,选择的索引数据,与之前的每个数据比较(分为两组,理论上,分为循环索引开始之前的为一组,已排序,索引之后为一组,未排序)
     * 比较之后,交换位置
     * <p>
     * 根据集合来看 i=3 开始生效
     * 第1次[4, 5, 6, 3, 2, 1]
     * 第2次[4, 5, 6, 3, 2, 1]
     * 第3次[3, 4, 5, 6, 2, 1]
     * 第4次[2, 3, 4, 5, 6, 1]
     * 第5次[1, 2, 3, 4, 5, 6]
     * @Author 寂寞旅行
     * @Date 9:42 2022/2/26
     * @Param [args]
     **/
    public static void main(String[] args) {

        int[] arr = {4, 5, 6, 3, 2, 1};
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                int temp;
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
            System.out.println("第" + i + "次" + Arrays.toString(arr));
        }
    }
}

二、动画演示

总结

可以看到希尔排序的核心思想是当前元素与之前的每个元素比较,相当于每个元素之前的顺序都是排好序的,之后的元素都是乱序的,按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序