void QuickSort1(int *data, int l, int u){
if (l>=u)return;//递归出口
// divide
int m=l;
for(int i=l+1;i<=u;i++){
if( data[i] <data[l])//品味这个条件
swap(data,++m ,i );
//三月份的这个版本，最大的发现就是：
//data[m]存储的是：当前比data[l]大的第一个元素。详细品味那个图
//cout<<"debug divide in quicksort "<<data[m]<<endl;
}
swap(data,l,m);//why??
// 特别的，我把这个不等式放在这儿：
// x [1..m-1 ] <x [m] <= a[m+1...u]
QuickSort1(data,l,m-1);
QuickSort1(data,m+1,u);
}
void QuickSort2(int *data,int l,int u){
int i,j;
if(l>=u)return;
int temp;
temp=data[l];
i=l;
j=u+1;//两个界限都比以前大step 1
while (true)
{ do i++; while(i<=u && data[i] <temp); //想想这里的上届下界？
do j--; while( j>=l && data[j] >temp); //66 add ..
if (i>j)
{
break;}
swap(data, i ,j);//测试，这里用i 一样吧？？
}
//when i==j 退出
swap(data,l,j); //细节
QuickSort2(data,l,j-1);//不是j
QuickSort2(data,j+1,u);
}
int cutoff=1;//为寻找最优设置。
void QuickSort3(int *data,int l, int u){
int i,j;
if ( u-l <cutoff ) return ; //cutofff
swap(data, l, rand() % (u -l) +1);
int temp;
temp=data[l];
i=l;
j=u+1;
while (true)
{
do i++; while( i<=u && data[i] < temp);
do j--; while( data[j] >temp);
if (i>j)
{
break;}
int t=data[i]; data[i]=data[j];data[j]=t;
}
swap(data,l,j);
QuickSort3(data,l,j-1);
QuickSort3(data,j+1,u);
}
源文档 <file:///C:\Documents%20and%20Settings\Administrator\桌面\cache1.doc>