0001 template <typename T> //列表的插入排序算法:对起始于位置p的n个元素排序 0002 void List<T>::insertionSort ( ListNodePosi(T) p, int n ) { //valid(p) && rank(p) + n <= size 0003 for ( int r = 0; r < n; r++ ) { //逐一为各节点 0004 insertA ( search ( p->data, r, p ), p->data ); //查找适当的位置并插入 0005 p = p->succ; remove ( p->pred ); //转向下一节点 0006 } 0007 }