0001 #define Put( K, s, t ) { if ( 1 < (t) - (s) ) { K.push(s); K.push(t); } } 0002 #define Get( K, s, t ) { t = K.pop(); s = K.pop(); } 0003 0004 template <typename T> //向量快速排序 0005 void Vector<T>::quickSort( Rank lo, Rank hi ) { //0 <= lo < hi <= size 0006 Stack<Rank> Task; Put( Task, lo, hi ); 0007 while ( !Task.empty() ) { 0008 Get( Task, lo, hi ); 0009 /* DSA */ //printf ( "\tQUICKsort: " ); for ( Rank i = 0; i < Task.size(); i+=2 ) printf ( " " ); printf ( " [%3d, %3d)\n", lo, hi ); 0010 Rank mi = partition( lo, hi ); //在[lo, hi)内构造轴点 0011 if ( mi - lo < hi - mi ) { 0012 Put( Task, mi+1, hi ); Put( Task, lo, mi ); 0013 } else { 0014 Put( Task, lo, mi ); Put( Task, mi+1, hi ); 0015 } 0016 } //大任务优先入栈(小任务优先出栈执行),可保证递归深度(空间成本)不过O(logn) 0017 }