思路：

　　每次迭代都和前面的元素进行比较，如果小于前面的元素则把当前元素和其前面的元素进行交换，然后接着再比较和前面元素的大小，若还是小于前面的元素则继续进行交换。如果大于前面的元素则终止当前的迭代。和选择排序相比，优势在于可以提前终止迭代。

原始数组 　　： 5  7  8  2  3  9

外层循环一次 ： 5  7  8  2  3  9

外层循环二次 ： 5  7  8  2  3  9

外层循环三次 ： 2  5  7  8  3  9

外层循环四次 ： 2  3  5  7  8  9

外层循环五次 ： 2  3  5  7  8  9

 

template< class T >void insertSort( T data[], int iLength ){    for (int n=1; n
     
       0 ; i--)        {            if( data[i - 1 ] > data[i])            {                swap( data[ i -1], data[i]);//依次替换两个元素，            }            else             {                break;             }        }    }}
     

 

优化：

　　可以看出下面的代码用一次赋值代替了上面的swap（三次赋值）。　　

template< class T >void insertSort( T data[], int iLength ){    for (int n=1; n
     
       0 && data[i - 1 ] > temp ; i--)        {                        data[i] = data[i-1];        }        data[ i ] = temp;    }}