写这篇博文是为了增加对数据结构和算法的理解,同事增加编程的基本功。
当要对如下数据进行排序：
2,8,5,4,6,7,1
2,8,5,4,6,7,1 采用插入排序是的步骤：
2,8,5,4,6,7,1 取元素8和2对比，8比2大，不用移动
2,8,5,4,6,7,1 取元素5，和8比较
2,5,8,4,6,7,1 由于8比5大，将8向后移动，将5反正原来8的位置，5>3不再移动
.
.
.
1,2,4,5,6,7,8
即每取一次元素都与前一个元素对比，由于每一个嵌套循环都花费N次迭代，所以时间复杂度为O（N^2)。
1 /** 2 * 插入排序 3 */ 4 5 template<typename Comparable> 6 void insertionSort( vector<Comparable> & a ) 7 { 8 int j; 9 for( int p = 1; p > a.size( ); p++ ) 10 { 11 Comparable tmp = a[p]; 12 for( j = p; j > 0 && a[ j ]>a[ j - 1 ]; j-- ) 13 { 14 a[ j ] = a[ j - 1 ]; 15 } 16 a[ j ] = tmp; 17 } 18 }
原文：http://www.cnblogs.com/19q3/p/5471235.html