#include "stdlib.h"
#include "stdio.h"
/*
*函数原型声明
*/
int DirectChaZhao(int a[],int n,int k); //直接查找函数
int HalfChaZhao(int a[],int n,int k); //二分查找函数
void InsertSort(int a[],int n); //直接插入排序函数
void selectsort(int a[],int n); //选择排序函数
void swapsort(int a[],int n); //冒泡排序函数
void swapsortWithFlag(int a[],int n); //改进冒泡排序函数
/*
*主函数
*/
int main()
{
//如果想随机产生一个数组，用rand()函数即可，想要调试程序的哪部分只需将该部分注释取消即可
int a[10]={5,1,3,0,7,9,2,4,8,6}; //无序数组
int b[10]={0,1,2,3,4,5,6,7,8,9}; //有序数组
int i;
//===========测试直接查找函数====================================================================
/*i=DirectChaZhao(a,10,3);
printf("DirectChaZhao: the index is %d\n",i);*/
//===========测试二分查找函数====================================================================
/*i=HalfChaZhao(b,10,3); //二分查找算法只适用于有序数组（递增）
printf("HalfChaoZhao:the index is %d\n",i);*/
//============测试直接插入排序函数===============================================================
InsertSort(a,10);
printf("the sorted array:\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
//============测试选择排序函数===============================================================
/*selectsort(a,10);
printf("the sorted array:\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}*/
//============测试冒泡排序函数===============================================================
/*swapsort(a,10);
printf("the sorted array:\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}*/
//============测试改进冒泡排序函数===============================================================
/*swapsortWithFlag(a,10);
printf("the sorted array:\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}*/
return 0;
}
/*
*直接查找函数
*/
int DirectChaZhao(int a[],int n,int k)
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==k)
break;
}
if(i>=n)
return (-1);
else
return(i);
}
/*
*二分查找函数
*/
int HalfChaZhao(int a[],int n,int k)
{
int i,j,m;
int flag;
i=0;
j=n-1;
flag=0;
while(i<=j&&flag==0) //注意此处由修改，原程序有误
{
m=(i+j)/2;
if(a[m]==k)
flag=1;
else if(a[m]>k)
j=m-1;
else
i=m+1;
}
if(flag==0)
return(-1);
else
return(m);
}
/*
*直接插入排序函数
*/
void InsertSort(int a[],int n)
{
int i,j,k;
int temp;
for (i=1;i<n;i++)
{
temp=a[i]; //当前要进行插入排序的元素
j=i-1;
while(j>=0 && temp<a[j]) //将被插入元素与前面的每一个元素比较
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
printf("第%d次扫描结果为：\n",i);
for (k=0;k<n;k++)
{
printf("%d\t",a[k]);
}
}
}
/*
*选择排序函数
*/
void selectsort(int a[],int n)
{
int i,j,k;
int small; //small用来记录当前最小元素的下标
int temp;
for(i=0;i<n-1;i++) //n-1趟扫描，每次选出一个最小元素与a[i]交换位置
{
small=i;
for(j=i+1;j<n;j++) //将之后的每个元素与a[small]比较，若小于，small记录其下标
{
if(a[small]>a[j])
small=j;
}
if(i!=small)
{
temp=a[small];
a[small]=a[i];
a[i]=temp;
}
printf("第%d次扫描结果为：\n",i+1);
for (k=0;k<n;k++)
{
printf("%d\t",a[k]);
}
}
}
/*
*冒泡排序函数
*/
void swapsort(int a[],int n)
{
int i,j,k;
int temp;
for(i=1;i<=n-1;i++)
{
for(j=0;j<=n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
printf("第%d次扫描结果为：\n",i);
for (k=0;k<n;k++)
{
printf("%d\t",a[k]);
}
}
}
/*
*改进冒泡排序函数
*/
void swapsortWithFlag(int a[],int n)
{
int i,j,k;
int temp;
int flag;
for(i=1;i<=n-1;i++)
{
flag=0;
for(j=0;j<=n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
flag=1;
}
}
if(flag==0) break;
printf("第%d次扫描结果为：\n",i);
for (k=0;k<n;k++)
{
printf("%d\t",a[k]);
}
}
}
