直接插入排序算法

直接插入排序是一种简单直观的排序方法，它的基本操作是将一个元素插入到已经排好序的有序序列中，从而得到一个新的，记录数增1的有序序列，工作原理类似我们抓扑克牌。

执行过程

对一组序列42,11,27,13,47,28,1,4,48,44执行直接插入排序算法，其排序过程如下：

代码

直接插入排序的C++实现如下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (0 == nums.size() || 1 == nums.size()) return nums;
        // i的初始值为1，从第一个元素开始
        for (int i = 1 ; i < nums.size() ; i++) {
            // 待插入的记录
            int record = nums[i];
            int j = i - 1;
            // 向后移动元素
            while (j > -1 && record < nums[j]) {
                nums[j + 1] = nums[j];
                j--;
            }
            // 插入
            nums[j + 1] = record;
        }
        return nums;
    }
};

由于测试用例的规模太大，本答案在912. 排序数组中执行耗时为：超出时间限制。

空间复杂度分析

本实现只需要一个记录即可，空间复杂度为O(1)；

时间复杂度分析

直接插入排序主要耗时操作是：(1)比较两个元素大小，(2)移动元素。假定我们的目标序列为升序序列时：

最好情况下：当序列升序排列时，无需移动记录，只需比较n-1次即可，时间复杂度为O(n)；

最坏情况下：当序列降序排列时，比较次数达到最大值：(1+2+3+...+n-1)=n(n-1)/2，记录移动次数也达到最大值2+3+4+...n=(n+2)(n+1)/2次，时间复杂度为O(n)；

平均情况下：时间复杂度为O(n)。

稳定性分析

由于只会移动比record大的数，移动的顺序为从后往前，排序后相同元素的相对位置不变，因此直接插入排序是稳定的排序算法。将比较条件改为record <= nums[j]，排序后相同元素的相对位置就会发生改变，就变成了不稳定的排序算法。

总结

直接插入排序算法

原文：https://www.cnblogs.com/hjxrupert/p/14649921.html