算法和数据结构2.3插入排序

插入排序

插入排序是一种序列从左端开始一次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。
插入排序的思路就是从右侧未排序的区域内去策划一个数据，然后将它插入到已排序的区域内的合适位置上。

排序步骤

假设有9个数字：

5 3 4 7 2 8 6 9 1

首先假设最左边的数字5已经完成了排序，所以此时只有5是已经排好序的数字。

接下来从待排序的数字区域内取出最左边的数字3，将它和左边已经归为的数字5进行比较。

若左边的数字更大，就交换这两个数字的位置。重复该操作，直到左边的已经归为的数字比取出的数字要小，或者取出的数字已经被移到整个序列的最左边为止。

因为5 > 3 所以

3 5 4 7 2 8 6 9 1

对数字3的排序工作到此结束。

此时3 和 5都已经归为了

还剩下右侧7个数字没有排序

接下来是地三轮。和前面的一样，取出未怕爱徐区域中最坐标安的数字4，将它与左边的数字5进行比较。

这里由于 5 > 4,所以交换这两个数字。

注意：这里交换后，再把4和左边的3比较，因为3 < 4,出现了比4小的数字，操作结束。

3 4 5 7 2 8 6 9 1

于是4也归位了。此时3，4，5都归为了已经排序的区域也得到了扩大。

接下来操作7，
将7和5进行比较，发现5 < 7 ，那么操作结束，不需要进行任何操作即可完成排序。

排序中....

重复以上操作，直到所有数字都归为。

对所有数字归为以后，排序就完成了。

时间计算：

在插入排序中，需要将取出的数据与其左边的数字进行比较。如果左边的数字更小，就不需要继续比较，本轮操作结束，自然也不需要交换位置的操作。

如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它整个序列的最左边为止。

具体来说就是：第k轮需要比价k-1次。因此，在最糟糕的情况下，第2轮的操作需要一次，第k轮的操作需要k-1次，所以时间复杂度和冒泡排序一样的都是O(n²)。