Skip to content

Latest commit

 

History

History
104 lines (74 loc) · 3.88 KB

插入排序.md

File metadata and controls

104 lines (74 loc) · 3.88 KB

插入排序

前言

插入排序的效果就像将一个数组模拟成两个数组的在选择、插入的过程。

实现思路

假设在下标 i 之前的是数都已经排好了顺序（ 0 ... i-1 ），那么此次需要找到 i 位置的数的正确位置 k 。在寻找这个位置 k 的过程中，逐个比较 i 之前排好顺序的数组，先比较最大的 i-1 位置的数（因为有序，所以 i 以前的数， i-1 是最大的），在寻找的过程中，比较的数大于当前 i 位置的数 ，那么比较的数置后一个位置，那么在有序数组中会一直“腾位置”，那么一直一直找，当找到比 i 位置小的数时，插入到这个数的后面即可，完成一趟插入。

模拟走位

上面说的很麻烦，直接看走位比较好 。

初始数组：[ 11 , 31 , 12 , 5 , 34 , 30 , 26 , 38 , 36 , 18 ]

第一趟：[ 11 , 31 , 12 , 5 , 34 , 30 , 26 , 38 , 36 , 18 ] （ 无移动的元素 ）

第二趟：[ 11 , 12 , 31 , 5 , 34 , 30 , 26 , 38 , 36 , 18 ] （ 31 向后移动 ）

第三趟：[ 5 , 11 , 12 , 31 , 34 , 30 , 26 , 38 , 36 , 18 ] （ 11 , 12 , 31 皆向后移动 ）

第四趟：[ 5 , 11 , 12 , 31 , 34 , 30 , 26 , 38 , 36 , 18 ] （ 无移动的元素 ）

第五趟：[ 5 , 11 , 12 , 30 , 31 , 34 , 26 , 38 , 36 , 18 ] （ 31 , 34 向后移动 ）

第六趟：[ 5 , 11 , 12 , 26 , 30 , 31 , 34 , 38 , 36 , 18 ] （ 30 , 31 , 34 向后移动 ）

第七趟：[ 5 , 11 , 12 , 26 , 30 , 31 , 34 , 38 , 36 , 18 ] （ 无移动的元素 ）

第八趟：[ 5 , 11 , 12 , 26 , 30 , 31 , 34 , 36 , 38 , 18 ] （ 38 向后移动 ）

第九趟：[ 5 , 11 , 12 , 18 , 26 , 30 , 31 , 34 , 36 , 38 ] （ 26 , 30 , 31, 34 , 36 , 38 向后移动 ）

**总结：**插入排序会比选择排序更优秀，以为它能利用排序过程中部分数有序的优势，减少一些不必要的比较，是否优秀取决于数组的初始顺序。

如果给定的数组是倒序，那么就是最坏的情况下了，比较次数：1 + 2 + ... ( n-1 ) + n = ( n+1 ) / 2。是一个不稳定的排序，依赖着数组的初始顺序。

实现代码

    public <T extends Comparable<T>> T[] insertSorting(T[] array) {
        int len = array.length;
        // 每个元素选取出来作为插入元素
        for (int i = 0; i < len; i++) {
            T toInsert = array[i];
            int j = i;
            for (; j > 0; j--) {
                /**
                 * 原来顺序系列里从最大的数开始  和 现在选择的比较
                 * 如果找到比选择的数小的 break
                 * 此时已经记下了 坐标 保存到 j 中
                 */
                if (array[j - 1].compareTo(toInsert) <= 0) {
                    break;
                }
                /**
                 * 如果一直没找到j的位置 那么就是 选择到的元素一直比较小
                 * 那么一直腾位置
                 */
                array[j] = array[j - 1];
            }
            //如果此时 j = 0 说明了 顺序序列里没有比选择元素小的
            array[j] = toInsert;
            System.out.print("i = " + i + "  array = ");
            for (T data : array) {
                System.out.print(data + " ");
            }
            System.out.println("");
        }
        return array;
    }

运行

    public static void main(String args[]) {
        /**
         * 插入排序
         */
        InsertSort insertSort = new InsertSort();
        System.out.println("\n插入排序\n");
        Integer[] object = {11, 31, 12, 5, 34, 30, 26, 38, 36, 18};
        Integer[] result = insertSort.insertSorting(object);
        System.out.println("");
        System.out.println("\n插入排序\n");
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println("");
        System.out.println("\n插入排序\n");
    }