分享一下快排+折半查找的C语言算法(大一时的作业) - 黑马程序员技术交流社区

#include "stdio.h"
#include "malloc.h"
int BinarySearch(int *pArr, int low, int high, int key)//查找函数
{
int mid;
if(low <= high)
{
mid = (low+high) / 2;
if(pArr[mid] == key)
return mid;
if(key > pArr[mid])
return BinarySearch(pArr,mid+1,high,key);
else
return BinarySearch(pArr,low,mid-1,key);
}
return -1;
}
int partitions(int *a,int low,int high)
{
int pivotkey=a[low];
while(low<high)
{
while(low<high && a[high]>=pivotkey)
--high;
a[low]=a[high];
while(low<high && a[low]<=pivotkey)
++low;
a[high]=a[low];
}
a[high]=pivotkey;
return high;
}
void qsort(int *a,int low,int high)
{
int pos;
if(low<high)
{
//递归调用
pos = partitions(a,low,high);
qsort(a,low,pos-1);
qsort(a,pos+1,high);
}
}
int main(void)
{
int len;
int *pArr; //定义指针变量pArr
int i, key, pos;
char x;
printf("请输入数组的长度：\n");
scanf("%d", &len);
/* 动态分配内存给pArr */
pArr = (int *)malloc( sizeof(int) * len );
printf("请输入你要存放的元素(空格分隔)：\n");
for(i=0; i<len; ++i)
scanf("%d", &pArr[i]);
printf("您输入的数组内容如下：\n");
for(i=0; i<len; ++i)
printf("pArr[%d] = %d\n" ,i, pArr[i]);
printf("\n您需要对数组内容进行快速排序并折半查找吗？(y or n):\n");
getchar();// 接收回车键字符
scanf("%c", &x);
if(x == 'y') //人机交互
{
qsort( pArr, 0, len-1 );//调用排序函数
printf("快速排序的结果如下:\n");
for(i=0;i<len;i++)
printf("pArr[%d] = %d\n" ,i, pArr[i]);
printf("请输入你需要查找的数据：");
scanf("%d",&key);
pos = BinarySearch( pArr, 0,len-1, key );//调用折半查找函数
printf("\n");
if(pos>=0)
printf("查找成功，该数字存储在排序后的数组下标为[%d]的位置。\n",pos);
else
printf("查找失败! 您的输入有误\n");
free(pArr); /*释放内存*/
}
return 0;
}

复制代码