目录

插入排序

基本介绍

插入式排序属于内部排序法,是对于要排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。

排序思想

把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的值依次与有序表元素的值进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 /**
     * 插入排序
     * 从小到大
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            // 待排序的元素下标和值,初始化为有序列表的最后一个元素
            int j = i - 1;
            // 从左边有序列表的最后一位元素开始遍历,如果待插入元素arr[i]比有序列表中的元素小,则有序列表中的元素后移否则插入
            for (; j >= 0 && insertVal < arr[j]; j--) {
                // 有序列表中的元素后移
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = insertVal;
        }

    }