插入排序

插入排序介绍

插入排序得基本思路是每次插入一个元素，每一趟完成对待插入元素得放置，直到全部插入完成。

• 直接插入排序

直接插入排序是一种最简单得排序方法，过程就是将每个待排元素逐个插入到已经排号得有序序列中。

• 折半插入排序

由于在插入排序的过程中，已经生成了一个（排好的元素组成）有序数列。所以插入待排元素时可以使用折半查找的方式，更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。

• 希尔排序

希尔排序可以看作是分组排序的排序方法。把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。

直接插入排序

• 输入

n个数的序列，通常直接存放在数组中，可能是任何顺序

• 输出

输入序列的一个新排列，满足从小到大的顺序，默认升序，简单修改可以实现降序

• 算法说明

每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，那么新的有序排列也就完成了。
通俗一点的解释就好比我们在打扑克牌，所有的牌扣在桌面上，我们一张一张的抓，抓起一张就在手里把它排好，那么我们把所有的牌都抓起来之后，手里的牌也就是有序的了

• 算法流程

对于计算机来说，我们必须要详细的告诉它如何比较大小，以及如何确定位置，毕竟它不能像我们一样，一眼就看出位置。试想一下，当数据量比较多的时候，我们也需要一个一个的看过来，然后才能确定新插入元素的位置，整个过程如下：
1 第一个元素：放在第一个位置，直接排好
2 第二个元素: 与第一个元素比较，如果更大，放在第二个位置，如果更小，放在第一个位置
3 第三个元素：顺次从后向前比较，如果更小，将已排好的元素向后串位，直到找到合适的位置插入
4 剩余其它元素： 顺次从后向前比较，如果更小，将已排好的元素向后串位，直到找到合适的位置插入
5 如果待排元素是已经排好元素中最大的，只需要比较一次，然后直接追加到已排好的序列后面

直接插入排序伪代码

for j=2 to A.length
    key = A[j]
    i=j-1
    while i>0 and A[i]>key
        A[i+1]=A[i]
        i = i -1 
    A[i+1] = key

初始计数器为2 ， 代表第一个元素默认排好，从第二个元素开始操作，直到最后一个元素
每次用key记录新操作的元素，i的初始值代表当前操作元素的前一个元素，也就是第一个要与之比较的元素。
while循环为内层循环，作用是已经排号的元素中找到合适的位置，来将key插入。
如果进入到循环体中执行，代表key相对较小，还要再向前寻找，同时，与之比对的元素要向后串位，因为此时可以确定，key一定在这个for循环的最后一行是将key插入到对应的位置，外层循环结束（每次循环插入一个数）