0001 template <typename T> //对列表中起始于位置p、宽度为n的区间做选择排序 0002 void List<T>::selectionSort ( ListNodePosi<T> p, int n ) { //valid(p) && rank(p) + n <= size 0003 ListNodePosi<T> head = p->pred, tail = p; 0004 for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail) 0005 while ( 1 < n ) { //在至少还剩两个节点之前,在待排序区间内 0006 ListNodePosi<T> max = selectMax ( head->succ, n ); //找出最大者(歧义时后者优先) 0007 insert ( remove ( max ), tail ); //将其移至无序区间末尾(作为有序区间新的首元素) 0008 tail = tail->pred; n--; 0009 } 0010 }