插入排序

十大经典排序算法

插入排序（Insertion Sort）的原理是默认前面的元素都是已经排序好的，然后从后面逐个读取元素并插入到前面排序好的序列中，就相当于打扑克每获取一张牌的时候就插入到合适的位置一样。如果只有一个元素我们默认他是有序的，然后从第二个元素开始逐个往前插入，如下图所示。

插入排序在往前寻找插入位置的时候，比他大的都要往后挪，所以要从后往前比较，最终会把待插入的位置空出来，比如上面图中第三步的时候，已排序数组是 [2,4,5] ，我们把 3 插入到前面：

• 首先 3 和 5 比较，5 比 3 大，5 往后挪，变成了 [2,4,x,5] 。
• 接着 3 和 4 比较，4 比 3 大，4 往后挪，变成了 [2,x,4,5] 。
• 最后 3 和 2 比较，2 比 3 小，因为每个比较的元素后面挨着的都是空出来的位置，直接把 3 插入到 2 的后面即可。

来看下代码：

public void insertSort(int[] nums) {
    int length = nums.length;
    for (int i = 1; i < length; i++) {
        int key = nums[i];// 矩形后面挨着的元素，往前找插入的位置。
        int j = i - 1;
        // 大于key的往后挪，腾出位置。
        for (; j >= 0 && nums[j] > key; j--)
            nums[j + 1] = nums[j];
        nums[j + 1] = key;// 把key放到需要插入的位置。
    }
}

稳定性分析

插入排序是把待插入的元素放到前面有序序列的合适位置，当前元素只有比前面的小才会往前挪，所以如果有相同的元素，他们的相对位置是不会变的，所以他是稳定的。

时间复杂度：O(n^2)
稳定性：稳定

相关链接