排序算法（三）插入排序

举例：打牌时我们一张张的摸牌，将摸到的牌插入手牌的”顺子”里,凑成更长的顺子，这就是插入排序的含义。

设无序数组a[]长度为N，以由小到大排序为例。插入的原理是这样的： 
1.初始时，第一个数据a[0]自成有序数组，后面的a[1]~a[N-1]为无序数组。令 i = 1; 
2.将第二个数据a[1]加入有序序列a[0]中，使a[0]~a[1]变为有序序列。i++; 
3.重复循环第二步，直到将后面的所有无序数插入到前面的有序数列内，排序完成。

 插入排序是一种比较快的排序，因为它每次都是和有序的数列进行比较插入，所以每次的比较很有”意义”，导致交换次数较少。

 

例子：

从小到大排序：

 结果：