插入排序

插入排序：

插入排序基本思想：如下数组a［］

初始状态：S ［O］ R T E X A M P L E

1.先将a［0］和a［1］比较，a［1］小于a［0］，那么将a［1］与a［0］交换变为：

第1趟排序后：O S ［R］ T E X A M P L E

2.再用a［2］和第一次交换后的a［1］比较，如果a［2］小于a［1］（如果a［2］大于a［1］那么就结束这趟排序），那么a［2］和a［1］进行交换。交换后再让a［1］和a［0］进行比较，a［1］大则进行交换，否则不交换并结束这趟排序。变为如下：

第2趟排序后：O R S ［T］ E X A M P L E

3.按照上述的方式对a［3］进行一趟排序：

第3趟排序后：O R S T ［E］ X A M P L E

4.接下来对每一个数组的元素都进行一趟上述的排序。

第4趟排序后：E O R S T [X] A M P L E
第5趟排序后：E O R S T X [A] M P L E
第6趟排序后：A E O R S T X [M] P L E
第7趟排序后：A E M O R S T X [P] L E
第8趟排序后：A E M O P R S T X [L] E
第9趟排序后：A E L M O P R S T X [E]
 第10躺排序：A E E L M O P R S T X 

插入排序的特点：

部分有序数组：
1.数组中每个元素距离它的最终位置都不远。
2.一个有序的大数组接一个小数组。
3.数组中只有几个元素的位置不正确。
插入排序对这样的数组很有效，而选择排序则不然。事实上，当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。

和选择排序不同的是，插入排序所需的时间取决于输入元素的初试顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

算法优化：

插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。

总述：

插入排序对于部分有序的数组十分高效，也很适合小规模数组。这很重要，因为这些类型的数组在实际应用中经常出现，而且它们也是高级排序算法的中间过程。我们会在学习高效排序算法时再次接触到插入排序。