插入排序

在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。

基本思路：当迭代到i时，会向前比较，插入到合适的位置（去在线算法演示体会）。

Java代码

public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j >= 1; j--) {
            if (nums[j-1] < nums[j]) {
                break;
            }
            int tmp = nums[j-1];
            nums[j-1] = nums[j];
            nums[j] = tmp;
        }
    }
}

空间复杂度

假设数组的元素个数是 n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是 O(1)。

时间复杂度

• 给定的数组按照顺序已经排好
  只需要进行 n-1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

• 给定的数组按照逆序排列
  在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。

• 给定的数组杂乱无章
  在这种情况下，平均时间复杂度是 O(n2)。

由此可见，和冒泡排序一样，插入排序的时间复杂度是 O(n2)，并且它也是一种稳定的排序算法。

练习题目：LeetCode 第 147 题

END!