插入排序的执行流程

插入排序，从该算法的名字中也可以看出，这种算法会有插入操作，如果我们用数组作为底层的数据结构实现该算法的话，进行插入操作，需要移动现有元素，空出位置后，才能进行插入操作。插入排序的排序思路，主要就是将未排序的数据和已排序的数据进行比较，找到较小的元素后，移动到已排序区间中。插入排序是原地排序算法，也可以是一种稳定排序算法(如果元素相等，我们将后来的相等元素添加到已排序区间的末尾即可)。插入排序在实战中用的很少，主要原因是这种算法可能会演变成O(n²)。
我在网上找了一个动图，很直观，大家可以看一下，来源：https://www.cnblogs.com/fivestudy/p/10064969.html

下面，我们看一下java的实现

public static void main(String[] args) {
        int[] array = new int[]{1, 8, 5, 6, 7, 3, 2};
        insertionSort(array, array.length);
    }

    public static void insertionSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                //判断是否需要移动元素
                if (a[j] > value) {
                    // 数据移动
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            // 插入数据
            a[j + 1] = value;
        }
    }

时间复杂度分析
最好情况下，数组是有序的，我们只需要一次比较操作就可以确定插入位置，所以最好情况时间复杂度是O(n)。
最坏情况下，数组是逆序的，我们每一轮比较操作，都需要移动n个数据，所以最坏情况时间复杂度是O(n²)。
平均情况下，数组一半逆序，一半有序。我们在一个数组中插入一个元素的时间复杂度是O(n)，所以平均时间复杂度就是O(n²)。
空间复杂度分析
未借助临时空间，空间复杂度是O(1)。
原地排序算法分析
是原地排序算法
稳定排序算法分析
先说答案，是稳定排序。插入排序可以是一种稳定排序算法，当两个元素相同时，将相同元素添加到已排序区间的末尾即可。

最后

以上就是大胆龙猫最近收集整理的关于插入排序的执行流程的全部内容，更多相关插入排序内容请搜索靠谱客的其他文章。