作者在 2010-05-25 12:26:47 发布以下内容
算法程序设计题~~高手帮忙啊~~~
请高手看看下面的程序怎么写呢，我是新手，请多多关照！程序名： algo9-1.cpp
根据输入的长度为10的无序关键字序列，先进行快速排序（升序），再用折半查找算法循环查找某一关键字的元素，直到按“#”号退出循环。
输入：10个关键字序列
输出：进行快速排序的过程（如下图所示）
循环输入：某一关键字k
循环输出：k在有序序列中的位置。
例如关键字序列为{6,8,7,9,0,1,3,2,4,5}。采用快速排序方法进行排序的过程如下：
排序前：6 8 7 9 0 1 3 2 4 5
5 4 2 3 0 1 6 9 7 8
1 4 2 3 0 5
0 1 2 3 4
2 3 4
3 4
8 7 9
7 8
排序后:0 1 2 3 4 5 6 7 8 9
要求：每个功能作为一个函数，每个函数有详细的注释。
程序可读性强，输入输出有明显的中文提示。
若你的程序能运行，要求附带提交exe文件，否则为不能运行。
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
void quick(int a[],int lf,int rg)
{
int tmp;
int lf_idx;
int rg_idx;
int t;
//1：第一个键值为a[lf]
if(lf<rg)
{
lf_idx=lf+1;
rg_idx=rg;
while(1)
{
int i,j;
for(i=lf+1;i<=rg;i++) //由左向右找出一个键值大于 d[lf]数
{
if(a[i]>=a[lf])
{
lf_idx=i;
break;
}
lf_idx++;
}
for(j=rg;j>=lf+1;j--) //由右向左找出一个键值小于 d[lf]数
{
if(a[j]<=a[lf])
{
rg_idx=j;
break;
}
rg_idx--;
}
if(lf_idx<rg_idx) //若lf_idx<rg_idx
{
tmp=a[lf_idx];
a[lf_idx]=a[rg_idx];
a[rg_idx]=tmp;
}
else
{
break;
}
}
if(lf_idx>=rg_idx)
{
tmp=a[lf];
a[lf]=a[rg_idx];
a[rg_idx]=tmp;
quick(a,lf,rg_idx-1);
quick(a,rg_idx+1,rg);
}
}
}
int bin_search(int a[],int val,int x)
{
int high,low,mid;
low=0;
high=x-1;
while(low<=high&val!=-1)
{
mid=(low+high)/2;
if(val<a[mid])
{
high=mid-1;
}
else if(val>a[mid])
{
low=mid+1;
}
else
return mid;
}
return -1;
}
int main()
{
char b;
int a[10];
int i,j;
while(1)
{
cin>>b;
if(b==35)
break;
else
{
cout<<"请输入十个数:"<<endl;
for(i=0;i<10;i++)
{
cin>>a[i];
}
//快速排序
quick(a,0,9);
for(i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
int val;
cin>>val;
int x=bin_search(a,val,10);
cout<<x<<endl;
}
}
return 0;
}
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
void quick(int a[],int lf,int rg)
{
int tmp;
int lf_idx;
int rg_idx;
int t;
//1：第一个键值为a[lf]
if(lf<rg)
{
lf_idx=lf+1;
rg_idx=rg;
while(1)
{
int i,j;
for(i=lf+1;i<=rg;i++) //由左向右找出一个键值大于 d[lf]数
{
if(a[i]>=a[lf])
{
lf_idx=i;
break;
}
lf_idx++;
}
for(j=rg;j>=lf+1;j--) //由右向左找出一个键值小于 d[lf]数
{
if(a[j]<=a[lf])
{
rg_idx=j;
break;
}
rg_idx--;
}
if(lf_idx<rg_idx) //若lf_idx<rg_idx
{
tmp=a[lf_idx];
a[lf_idx]=a[rg_idx];
a[rg_idx]=tmp;
}
else
{
break;
}
}
if(lf_idx>=rg_idx)
{
tmp=a[lf];
a[lf]=a[rg_idx];
a[rg_idx]=tmp;
quick(a,lf,rg_idx-1);
quick(a,rg_idx+1,rg);
}
}
}
int bin_search(int a[],int val,int x)
{
int high,low,mid;
low=0;
high=x-1;
while(low<=high&val!=-1)
{
mid=(low+high)/2;
if(val<a[mid])
{
high=mid-1;
}
else if(val>a[mid])
{
low=mid+1;
}
else
return mid;
}
return -1;
}
int main()
{
char b;
int a[10];
int i,j;
while(1)
{
cin>>b;
if(b==35)
break;
else
{
cout<<"请输入十个数:"<<endl;
for(i=0;i<10;i++)
{
cin>>a[i];
}
//快速排序
quick(a,0,9);
for(i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
int val;
cin>>val;
int x=bin_search(a,val,10);
cout<<x<<endl;
}
}
return 0;
}