插入排序
插入排序是一种序列从左端开始一次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。
插入排序的思路就是从右侧未排序的区域内去策划一个数据，然后将它插入到已排序的区域内的合适位置上。
排序步骤
假设有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(n2)。
网友评论