算法----插入排序（insert sort）

插入排序就是每次选取一个元素插入到已经排序的子数组中，如此循环，直到所有的元素都完成排序。算法实现：void sort::insert_sort（int* a, const int n）
{
for（int i=1; i<n; i++）
{
for（int j=i; j>0 && a[j] < a[j-1]; j--）
{
swap（a,j,j-1）;
}
}
}上述算法的时间复杂度为O（N^2）。但是插入排序的算法性能与待排序的数组有关，当数组已排序，则可在线性时间内完成，如果数组为逆序，则需要O（N^2）的时间才能完成排序。因此插入排序算法的时间复杂度在N~N^2之间。当数组规模较小或者存在多个局部有序的子数组时，算法的执行速度会更快。归并排序的实现 http://www.linuxidc.com/Linux/2014-09/107316.htm直接插入排序的三种实现 http://www.linuxidc.com/Linux/2014-09/107313.htm直接选择排序及交换二个数据的正确实现 http://www.linuxidc.com/Linux/2014-09/107315.htm排序总结之选择式排序 http://www.linuxidc.com/Linux/2014-09/106564.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-11/109825.htm