乐趣区

关于算法:算法总结直接插入排序

jiezi

算法定义

间接插入排序是插入排序的一种，是一种简略的排序办法，其基本操作是将一条记录插入到已排好的有序表中，从而失去一个新的、记录数量增 1 的有序表。

算法原理

间接插入排序算法流程如下：

1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最初一个元素当成是未排序序列。

2、从头到尾顺次扫描未排序序列，将扫描到的每个元素插入有序序列的适当地位。

代码实现

依照下面的思路，能够通过交换法实现。

从第 2 个数开始，确定要操作的数，对要操作的数找到要插入的地位。

而后一路往前比照，若以后数字比前一个数字小，那么替换两个数字，通过一直的替换找到这个数适合的地位插入。

交换法的代码如下：

public class Main {// 间接插入排序 ( 插入排序)，交换法，均匀工夫复杂度 O(n^2)，最好工夫复杂度 O(n)，最坏工夫复杂度 O(n^2)，空间复杂度 O(1)
    public static void directlyInsertSort(int[] arr) {
        // 从第 2 个数开始，确定要操作的数，对要操作的数找到要插入的地位
        for (int i = 1; i < arr.length; ++i) {
            // 获取以后数字的下标
            int j = i;

            // 一路往前比照，若以后数字比前一个数字小，那么替换两个数字，通过一直的替换找到这个数适合的地位插入
            while (j >= 1 && arr[j] < arr[j - 1]) {
                // 替换两个数字
                arr[j - 1] ^= arr[j];
                arr[j] ^= arr[j - 1];
                arr[j - 1] ^= arr[j];

                // 下标往前挪动
                --j;
            }
        }
    }

}

然而咱们发现，在交换法中，每次替换数字时，下一次比拟可能又要被替换上来了。

所以，咱们想到一个优化，应用挪动法：先让新插入的数字和后面的数字进行比拟，比新插入的数字大的数字一直向后挪动，直到找到适宜这个新插入的数字的地位后，新插入的数字再做一次替换，来实现插入。

挪动法的代码如下：

public class Main {// 间接插入排序 ( 插入排序)，挪动法，均匀工夫复杂度 O(n^2)，最好工夫复杂度 O(n)，最坏工夫复杂度 O(n^2)，空间复杂度 O(1)
    public static void directlyInsertSort(int[] arr) {
        // 从第 2 个数开始，确定要操作的数，对要操作的数找到要插入的地位
        for (int i = 1; i < arr.length; ++i) {
            // 先把以后要插入的数字保存起来
            int temp = arr[i];

            // 获取以后要插入的数字的前一个下标
            int j = i - 1;

            // 一路往前，和以后要插入的数字比拟，若大于以后要插入的数字，那么后移，直到不大于以后要插入的数字或者到了第一个下标，完结循环
            while (j >= 0 && arr[j] > temp) {
                // 后移数字
                arr[j + 1] = arr[j];

                // 下标往前挪动
                --j;
            }

            // 找到插入的地位，把以后要插入的数字赋值到这里
            arr[j + 1] = temp;
        }
    }

}

交换法和挪动法其实差不多，挪动法没有本质的效率改善，只是缩小了一些没有必要的替换操作，并没有升高工夫复杂度和空间复杂度。

算法效率

间接插入排序是稳固的排序算法。

最好工夫复杂度是 O(n)，刚好数组是程序的，两层循环只走了第一层，第一层 for 循环是 n 数量级的工夫，第二层 while 循环，数组曾经有序，不会进入。

最坏工夫复杂度是 O(n^2)，刚好数组是顺叙的，两层循环都走了，第一层 for 循环是 n 数量级的工夫，第二层 while 循环也是 n 数量级的工夫，每次都要替换 n - k 次，k 是常数，去到常数项 k，还是 n 的数量级，所以是 n * n=n ^ 2。

均匀工夫复杂度是 O(n^2)，第一层 for 循环无论如何都要走的，第二层的 while 循环，均匀下来也是 n 的数量级，因为假如数组有 n 个数，不同程序的数组，第二层的 while 循环还是和后面的示意一样，替换 n - k 次，k 是常数，去到常数项 k，还是 n 的数量级，所以还是 n * n=n ^ 2。

空间复杂度为 O(1)，因为只应用无限个数的变量。

算法是稳固的，因为间接插入排序本质是通过替换来实现插入的，而这里的替换判断没有等于的判断，如果数组里的两个数是相等的，那么不会替换，那么就不存在数组里相等的两个数的替换。

均匀工夫复杂度：O(n^2)

最好工夫复杂度：O(n)

最坏工夫复杂度：O(n^2)

空间复杂度：O(1)

参考资料

间接插入排序动图来自：间接插入排序

原文链接

原文链接：算法总结 - 间接插入排序

退出移动版