0001 typedef unsigned int U; //约定:类型T或就是U;或可转换为U,并依此定序 0002 0003 template <typename T> //对列表中起始于位置p、宽度为n的区间做基数排序 0004 void List<T>::radixSort ( ListNodePosi<T> p, int n ) { //valid(p) && rank(p) + n <= size 0005 ListNodePosi<T> head = p->pred; ListNodePosi<T> tail = p; 0006 for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail) 0007 for ( U radixBit = 0x1; radixBit && (p = head); radixBit <<= 1 ) //以下反复地 0008 for ( int i = 0; i < n; i++ ) //根据当前基数位,将所有节点 0009 radixBit & U (p->succ->data) ? //分拣为后缀(1)与前缀(0) 0010 insert( remove( p->succ ), tail ) : p = p->succ; 0011 } 0012 //思考:某趟分拣后若前缀、后缀没有变化,是否可以随即结束算法? 0013 //待改进:提前找出最大元素并估算出最高有效位,从而节省无用的分拣 0014 //待改进:为避免remove()、insertB()的低效率,实现List::moveB(t,p)接口,将节点p移动至t之前