用分治法实现元素选择所用函数：
在该程序中总共用了六个函数：
1、两个数的交换函数swap( );
2、对一个数组进行划分函数partition(int a[],int p,int r,int x);
3、快速排序函数 void quicksort(int a[],int p,int r);
4、选择第k小数的函数int select(int a[],int p,int r,int k)；
5、数组生成函数 void create_array( )；
6、开始选择函数 void begin_select( );
一、交换函数swap( )
void __fastcall TForm1:: swap(int &a,int &b)
{ //交换两个整数a和b
int temp=a;
a=b;
b=temp;
}
二、划分函数partition(int a[],int p,int r,int x)
int __fastcall TForm1::partition(int a[],int p,int r,int x)
{ int i=p; //把一个数组下标从p到r之间的数以x为基准
int j=r+1; //划分为两个部分
while(true)
{
while(a[++i]<x);
while(a[–j]>x);
if(i>=j) break; //
swap( a[i], a[j]); //调用交换函数来交换a[i]和a[j]
}
a[p]=a[j];
a[j]=x;
return j;
void __fastcall TForm1:: quicksort(int a[],int p,int r)
{ if(p<r) //把a[p]到a[r]的数进行快速排序
{
int q=partition(a,p,r,a[p]); //以a[p]为基准划分数组
quicksort( a, p,q-1); //对左边的数组排序
quicksort( a,q+1, r); //对右边的数组排序
}
}
{
if(r-p<75) //当需选择的数个数小于75时
{ //对它进行快速排序
quicksort(a,p,r);
return a[p+k-1];
}
{ //将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,p+(r-p-4)/5,(r-p-4)/10); //找中位数的中位数
int m=partition(a,p,r,x); //以中位数的中位数为基准划分数组
int j=m-p+1;
if(k<=j)
else
}
{
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的文件中
}
{
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函数对数组
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的文件中
}
void __fastcall TForm1::N3Click(TObject *Sender)
{ //new一个AboutBox窗体
AboutBox=new TAboutBox(Application);
AboutBox->ShowModal(); //显示该窗体
delete AboutBox; //释放该对象
}
