经典算法5：用分治法实现元素选择

}

三、快速排序函数 quicksort(int a[],int p,int r)
void __fastcall TForm1:: quicksort(int a[],int r)
{ ? ?if(p<r) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //把a[p]到a[r]的数进行快速排序
{
int q=partition(a,p,r,a[p]); ? ? ? ? //以a[p]为基准划分数组
? ? ? ? ? ? quicksort( a,q-1); ? ? ? ? ? ? ? ? ? //对左边的数组排序
quicksort( a,q+1,r); ? ? ? ? ? ? ? ? ? ? //对右边的数组排序
} ??
?}

四、选择第k小数的函数int select(int a[],int r,int k)

int __fastcall TForm1::select(int a[],int k)
{
? ?if(r-p<75) ? ? ? ? ? ? ? ? //当需选择的数个数小于75时
? { ? ? ? ? ? ? ? ? ? ? ? ?//对它进行快速排序
? ? ? quicksort(a,r); ??
? ? ? return a[p+k-1];
? ?}

for(int i=0;i<=(r-p-4)/5;i++)
? ?{ ? ? ? ? ? ? ? ? ? ? ? ?//将a[p+5*i]到a[p+5*I+4]的数进行快速排序
? ? ? ? quicksort(a,p+5*i,p+5*i+4);
? ? ? ? swap(a[p+i],a[p+5*i+2]); // 交换a[p+i] 和a[p+5*i+2]
? ? }
? ??int ?x=select(a,p+(r-p-4)/5,(r-p-4)/10); ?//找中位数的中位数
? ? int m=partition(a,x); ? ? ?//以中位数的中位数为基准划分数组
? ??int j=m-p+1;
? ? if(k<=j) ?

return ?select(a,m,k); ? //在中位数的中位数左边选择
? ?else

return ?select(a,m+1,k-j); ? ? ? //在中位数的中位数右边选择
}

五、数组生成函数 void create_array( )

void __fastcall TForm1::create_array()
{ ?

int max=120; ? ? ? ? ? ? ? ? //定义数组大小为120；

? ? AnsiString str;
? for(int i=0;i<max;i++)
? { ? ? //循环调用随机函数random()给array数组赋值
? ? array[i]=random(max); //该函数中的max值可以根据需要随意更改
? ? str="array["+IntToStr(i)+"]="+IntToStr(array[i])+"；";
Memo1->Lines->Append(str); ? ? ? ?//在Memo组件中显示数组
? Memo1->Lines->SaveToFile("array_before.txt");
? } ? ? //把排序前的数组写入文件名为array_before.txt的文件中
}

六、开始选择函数 void begin_select( );

void __fastcall TForm1::begin_select( )
{?
? int ?no =StrToInt(Edit2->Text); ? ? ? //定义将要选择的第几小数
? int ?first=StrToInt(Edit4->Text); ? ? //定义选择区域的起始位置
? int ?last=StrToInt(Edit5->Text); ? ? //定义选择区域的终止位置
if( no>120 || no<0 || first>119 ||first<0 || last>119 || last<0 || first>last ? ? ? ?
? ? ? || ? first + no-1 > last)
{ ? ? ? ? ? ? ? ?//当no 、first和 last三个数的输入不对时给出消息框
Application->MessageBoxA("输入错误！","警告",48);
}
? ? ?else
{
? ? ? create_array(); ? ? ? ? ? ?//调用create_array()构造数组array
? ? ? int ?result=select(array,first,last,no); ? //调用select函数对数组 ? ?

Edit3->Text=IntToStr(result); ? ? ? ? ? ? ? ? ? ? ? //进行选择
? ? AnsiString string;
? ? ? for(int i=0;i<120;i++)
? ? ? { ? ? ?string="array["+IntToStr(i)+"]="+IntToStr(array[i])+"；";
? ? ? ? ? ? ? ?Memo2->Lines->Append(string); ?//排序显示在Memo上
? ? ? ? ? ? ? Memo2->Lines->SaveToFile("array_after.txt");
? ? ? ? ? } //把排序前的数组写入文件名为array_after.txt的文件中
} ?

}

七、动态产生AboutBox窗体的代码