快排和二分查找的原理就不说了,网上一搜一大堆,这里主要是自己编写的快排、二分与系统自带的快排、二分代码,一般面试都会出冒泡,所以冒泡是才是最重要的。系统自带的快排函数在编写代码的时候用着挺方便的,代码如下:
// 快速排序
#include <stdio.h>
void q_sort(int arr[],int low,int high);
int main()
{
intarr[10] = {0};
inti = 0;
printf("输入 10 个整数:\n");
for(i= 0;i < 10;i++)
scanf("%d",&arr[i]);
q_sort(arr,0,9);
for(i= 0;i < 10;i++)
printf("%d",arr[i]);
printf("\n");
return0;
}
void q_sort(int arr[],int low,int high)
{
inti = 0,j = 0; //i-低 j-高
intbase = 0; // 基数
inttemp = 0;
if(low>= high) // 递归终止
return;
i= low;
j= high;
base= arr[low];
while(i< j){
while(arr[j]> base)// 高->低
j--;
temp= arr[j];
arr[j]= arr[i];
arr[i]= temp;
while(arr[i]< base)// 低->高
i++;
temp= arr[j];
arr[j]= arr[i];
arr[i]= temp;
if(i<j&& arr[i]==arr[j])
j--;
}
q_sort(arr,low,i-1);
q_sort(arr,i+1,high);
}
/***************************************
auth:肖乔
func:二分查找
***************************************/
#include<stdio.h>
#define N 5
int main(){
inti,j,a[N],t;
inthig,low,mid,k;
printf("请输入%d个整数:",N);
for(j=0;j<=N-1;j++){
scanf("%d",&a[j]);
}
for(i=0;i<N-1;i++)
for(j=0;j<N-1-i;j++)
if(a[j]>a[j+1]){
t=a[j];a[j]=a[j+1];a[j+1]=t;
}
printf("从小到大排列:");
for(j=0;j<=N-1;j++)
printf("%d",a[j]);
printf("\n");
#if 1
printf("请输入要查找的数:");
scanf("%d",&k);
low=0;hig=N-1;
while(low<=hig){
mid=(low+hig)/2;
if(a[mid]==k){
printf("%d在数组中第%d位\n",a[mid],mid+1);
break;
}
elseif(a[mid]<k)
low=mid+1;
else
hig=mid-1;
}
#endif
return0;
}
下面是系统自带快排和二分查找的函数。qsort和bsearch两个函数可以配合起来用,先排序,在查找,也可以分开使用。qsort在比较两个数大小的时候返回3个值,1、-1、0,改变1和-1的位置,就可以实现从大到小和从小到大排序。
qsort
功能:对数组base中nmemb块大小为size字节的数组快速排序。
参数:base 开始地址,nmenmb 数据块数 size 地址大小 compare 根据此指针指向的函数的返回结果来排序(0,正数和负数)
返回值:无
bsearch
功能:从地址base 开始空间的nmenmb块大小为size字节的数据中,二分查找key指针保存地址空间中的内容
参数:key查找内容的首地址base开始地址nmenmb
//qsort 函数的使用
//bseach函数使用
#include<stdio.h>
#include<stdlib.h>
int c_desc(const void *px,const void *py);
//int c_asc(const void *px,const void *py);
int main(){
intarr[10]={0};
inti=0,j=0,data=0;
int*p=&j;
printf("输入十个数:");
for(i=0;i<10;i++)
scanf("%d",&arr[i]);
printf("输入查找的数:");
scanf("%d",&data);
printf("升序排列:\n");
qsort(arr,10,sizeof(int),c_desc);
for(i=0;i<10;i++)
printf("%d",arr[i]);
printf("\n");
// printf("降序排列:\n");
// qsort(arr,10,sizeof(int),c_asc);
// for(i=0;i<10;i++)
// printf("%d",arr[i]);
p=bsearch(&data,arr,10,sizeof(int),c_desc);
if(p==NULL)
printf("不存在");
else{
printf("存在\n");
printf("%d在第%d个位置",data,p-arr+1);
}
printf("\n");
return0;
}
int c_desc(const void *px,const void *py){
const*p1=px;
const*p2=py;
if(*p1==*p2)
return0;
elseif(*p1>*p2)
return1;
else
return-1;
}
#if 0
int c_asc(const void *px,const void *py){
const*p1=px;
const*p2=py;
if(*p1==*p2)
return0;
elseif(*p1>*p2)
return-1;
else
return1;
}
#endif