插入排序
打过牌的朋友肯定知道在发完牌之后通常需要把自己的牌整理成“有序”的，现实世界中你当然可以自由插入。
但是在计算机的世界中，要插入元素往往需要将插入位置右边的元素都向右移动一位。
这就是我们今天这篇文章要跟大家分享的一种基础的排序算法——插入排序，虽说基础，但是他对于我们优化更高级的排序算法的性能，是很有作用的，甚至在某些场景下效率比快速排序和归并排序等还要快。
算法的核心又来了：在排序的过程中将数组分成有序和无序的两部分，并在排序的过程中不断的让无序的部分变得有序。
那插入排序算法是怎么逐渐的将数组变有序的？
我们认为数组左边是有序，右边是无序的。然后每次都从数组的无序部分取第一个元素，将其插入到有序的部分中适当的位置 X。具体的我们是通过不断的往前比较来找到这个适当的位置 X 的。
之后我们再重复这个过程。
插入排序算法流程分析
我们通过一个对有 n 个元素的数组进行插入排序的具体例子，来演示这个过程（升序）。
排序之前
8 4 2 6 9 6
排序之前我们认为数组从 [0, 0] 这个范围是有序的。
第一轮插入
我们从无序部分的第一个元素（也就是 4）开始，往前比较，4 < 8，进行交换。
结果：
4 8 2 6 9 6
再继续往前，发现到了边界，结束第一轮插入。
此时的数组：
4 8 2 6 9 6
此时，数组从 [0, 1] 这个范围是有序的，从 [2, n - 1] 这个范围是无序的。
接下来，我们只需要对 [2, n - 1] 这个范围重复上面的操作。
第二轮插入
我们继续从无序部分的第一个元素（也就是 2）开始，往前比较，2 < 8，进行交换。
结果：
4 2 8 6 9 6
再继续往前比较，2 < 4，进行交换。
结果：
2 4 8 6 9 6
再继续往前比较，发现到了边界，结束第二轮插入。
此时的数组：
2 4 8 6 9 6
此时，数组从 [0, 2] 这个范围是有序的，从 [3, n - 1] 这个范围是无序的。
接下来，我们只需要对 [3, n - 1] 这个范围重复上面的操作。
继续插入
依次类推，我们可以顺利推出下面几次插入的结果，并在最后得到有序的数组。
第三轮插入结果
2 4 6 8 9 6
第四轮插入结果
2 4 6 8 9 6
第五轮选择结果
2 4 6 6 8 9
代码实现
public void insertSort(int[] nums) {
// 第一轮循环表示我们每次选择的是数组无序部分中的第一个元素 nums[i]
// [0, i - 1] 有序 [i, nums.length - 1] 无序
for (int i = 1; i < nums.length; i++) {
for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
swap(nums, j, j - 1);
}
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
时间复杂度
插入排序的时间复杂度是 {O(n^2)}。
但不同于我们上面文章所讲的选择排序，插入排序所需的时间取决于数组的初始顺序。
当输入的数组已经有序（或者接近有序时），想想我们在排序的过程中，会发生什么。
我们每一次只需要将无序部分的第一个元素向前比较一次，或者少数的几次，就能确定这个元素的位置。
数组接近有序（或小规模数组）的情况下插入排序的时间复杂度接近于 **{O(n)}。
后面在学习其他高级的排序算法，我们会和插入排序再次相遇的。
还有一个很有意思的点，我们所讲过的冒泡排序，选择排序和插入排序都是在排序的过程中将数组分成有序和无序的两部分，但是冒泡排序和选择排序是保持有序的部分不动，而插入排序却不断的去改变有序的部分让数组变得更有序。
空间复杂度
插入排序和冒泡排序，以及选择排序一样，都属于典型的原地排序算法，空间复杂度为 O(1)，因为只需要常数级别的额外空间来存储临时变量。
稳定性
插入排序是一种稳定的排序算法。在我们的算法实现中，在往前比较时，当遇到相同元素时不进行交换操作，就能保证相同元素的相对位置不会改变，从而保持了稳定性。
写在最后
总的来说，插入排序是一种很有用的排序算法，无论是在小规模数组或有序数组的场景下使用，还是后面我们会继续提到的如何优化高级排序算法，都很有用。
同样给大家留一些思考题。
- 我们在前文给出了迭代算法的实现，希望大家可以尝试下用递归的方法，这对于更深入的理解插入排序和递归都很有帮助。
- 我们是通过往前比较进行交换元素的方式来实现有序的，其实大家也可以尝试用让元素向右移动的方式来实现。
- 我们是在数组的有序部分中来找到应该插入的位置的，那是否可以用二分查找来找到应插入的位置呢，大家又可以尝试一下了。
大家加油！