菜鸟天堂

template<class T>
void insertion_sort( node<T> * & head )//
{
 node<T> * first_unsorted,
      * last_sorted,
   * insert,
   * insertPre;
 if( head )
 {
  last_sorted = head;  
  while( last_sorted->next )
  {
   first_unsorted = last_sorted->next;
   if( first_unsorted->key < last_sorted->key )
   {
    insert = head;   
    while( first_unsorted->key>=insert->key ) //从前到后, 保持稳定
    {
     insertPre = insert;
     insert = insert->next;
    }    
    if( insert == head )
    {
     last_sorted->next = first_unsorted->next;//
     first_unsorted->next = head;
     head = first_unsorted;       
    }
    else
    {     
     last_sorted->next = first_unsorted->next;
     first_unsorted->next = insert;
     insertPre->next = first_unsorted;
    }    
   }
      else
    last_sorted = first_unsorted;//   
  } 
 }
}
说明:
1) 插入之前不需要移动元素, 所以不需要从后往前查找.
2) 保持算法的稳定性.
3) 函数参数必须是指针的引用!