算法总结-直接插入排序

算法定义

直接插入排序是插入排序的一种，是一种简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增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)

参考资料

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

原文链接

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

最后

以上就是寒冷铃铛为你收集整理的算法总结-直接插入排序的全部内容，希望文章能够帮你解决算法总结-直接插入排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。