/*折半查找*/
#include<stdio.h>
#define MAX 100
int a[MAX];
void init_array(int n)//初始化数组
{
int i;
for(i=0;i<n;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
}
void print_array(int n)//输出数组
{
int i;
for(i=0;i<n;i++)
printf("a[%d]=%-3d",i,a[i]);
printf("\n");
}
int halfserch(int n,int key)
{
int s,e,i;
s=1;
e=n;
while(s<=e)
{
i=(s+e)/2;
if(key<a[i])
e=i-1;
else if(key>a[i])
s=i+1;
else//刚好找到,返回
return(i);
}
return (0);
}
bublesort(int n)
{
int i,j,tmp;
for(i=0;i<n;i++)
for(j=0;j<i;j++)
if(a[i]<a[j])
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
int main(void)
{
int n,key,flag;
printf("Input the array size n:\n");
scanf("%d",&n);
init_array(n);
printf("Input the key you want to find\n");
scanf("%d",&key);
bublesort(n);
print_array(n);
flag=halfserch(n,key);
if(flag)
printf("We found it a[%d]=%d\n",flag,a[flag]);
else
printf("Not Found the number %d!\n",key);
}
/*快速排序*/
#include<stdio.h>
#define MAX 100
int a[MAX];
void init_array(int n)
{
int i;
for(i=0;i<n;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
}
void print_array(int n)
{
int i;
for(i=0;i<n;i++)
printf("a[%d]=%-3d",i,a[i]);
}
void quicksort(int s,int e)
{
int i,j,tmp,key;
i=s;
j=e;
key=a[s];
while(i<j)
{
if(a[i]>a[j])
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
if(tmp==key)
i++;
else
j--;
}
else
{
if(a[i]==key)
j--;
else
i++;
}
}
if(s<i-1)
quicksort(s,i-1);
if(i+1<e)
quicksort(i+1,e);
}
int main(void)
{
int n;
printf("Input the array size n:\n");
scanf("%d",&n);
init_array(n);
quicksort(0,n-1);
print_array(n);
printf("\n");
}