qsort与bsearch函数组合.docx

qsort函数简介功 能: 使用快速排序例程进行排序 用 法: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *); 参数：1 待排序数组首地址 2 数组中待排序元素数量 3 各元素的占用空间大小 4 指向函数的指针，用于确定排序的顺序 编辑本段c函数qsort()和bsearch()的用法使用qsort()排序 并 用 bsearch（）搜索是一个比较常用的组合，使用方便快捷。 qsort 的函数原型是void _cdecl qsort ( void *base, size_t num, size_t width, int (_cdecl *comp)(const void *, const void* ) ) 其中base是排序的一个集合数组，num是这个数组元素的个数，width是一个元素的大小，comp是一个比较函数。 比如：对一个长为1000的数组进行排序时，int a1000; 那么base应为a，num应为 1000，width应为 sizeof(int)，comp函数随自己的命名。 qsort(a,1000,sizeof(int ),comp); 其中comp函数应写为: int comp(const void *a,const void *b) return *(int *)a-*(int *)b; 是对一个二维数组的进行排序： int a10002; 其中按照a0的大小进行一个整体的排序，其中a1必须和a0一起移动交换。 qsort(a,1000,sizeof(int)*2,comp); int comp(const void *a,const void *b) return (int *)a)0-(int *)b)0; 编辑本段举例举例1： char a100020; qsort(a,1000,sizeof(char)*20,comp); int comp(const void *a,const void *b ) return strcmp(char *)a,(char *)b); 对一个结构体进行排序： typedef struct str char str111; char str211; str,*stri; str strin100001=; int compare(const void *a,const void *b) return strcmp( (str*)a)-str2 , (str*)b)-str2 ); qsort(strin,total,sizeof(str),compare); #include using namespace std; #include #include int compare( const void *a, const void *b); char * list5= cat,car,cab,cap,can; int main() 举例2：(C/C+例程) 按字符串长度对字符串进行排序： #include #include #include #define N 8 using namespace std; int compare(const void *a,const void *b); int main(void) int i; char s810=January,February,March,April,May,June,July,September; qsort(s,8,sizeof(char)*10,compare); for(i=0;i8;i+) coutsiendl; return 0; int compare(const void *a,const void *b) if(strlen(char *)a)!=strlen(char *)b) return strlen(char *)a)-strlen(char*)b); return (strcmp(char *)a,(char *)b); 下面这个例程在VS2008中运行通过，比较具有代表性： #include #include #include int compare(const void *arg1,const void *arg2); int main(int argc,char *argv) int i; argv+; argc-; qsort(void *)argv,(size_t)argc,sizeof(char *),compare); for(i=0;iargc;+i) printf(%sn,argv); return 0; int compare(const void *arg1,const void *arg2) return _stricmp(*(char *)arg1,*(char *)arg2); 在运行输入cmd,在qsort.exe 参数1 参数2将会排序。 举例3： pascal 例程 program quicksort; const max = 100000; max = 1000; type tlist = array1.max of longint; var data : tlist; i : longint; procedure qsort(var a : tlist); procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a(l+r) div 2; repeat while aix do inc(i); while xaj do dec(j); if ij; if lj then sort(l,j); if ir then sort(i,r); end; begin sort(1,max); end; begin write(Creating ,Max, random numbers between 1 and 500000); randomize; for i:=1 to max do data:=random(500000); writeln; writeln(Sorting.); qsort(data); writeln; for i:=1 to max do begin write(data:7); if (i mod 10)=0 then writeln; end; end. 下面讲解下Pascal的快排代码 program kuaipai; var save:array-1.10000000of longint;/保存数字的数组 n,i:longint; procedure qsort(x,y:longint); var a,b,c,em,d,mid,e,i,j,k,l:longint; begin i:=x;/i代表第一个数字的数组坐标,下面叫“左指针” j:=y;/j代表第二个数字的数组坐标 叫右指针 mid:=save(x+y)div 2;/取，这2个数字中间的数组坐标（二分） repeat while saveimid do dec(j);/在中间数右边，找比中间数小的数字 if ij;/左指针跑到右指针右边了。 if ix then qsort(x,j);/如果右指针没跑到，左界限，那么从右指针到左界限排序 end; begin randomize;/优化程序用的，暂时你不用会 readln(n);/读入，表示有N个数字 for i:=1 to n do/读入这N个数字 read(savei); qsort(1,n);/从第一个数字，到最后一个数字排序 for i:=1 to n do/输出 write(savei, ); end. 一个典型的qsort的写法如下qsort(s,n,sizeof(s0),cmp); 其中第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&si这样的表达式); 第二个参数是参与排序的元素个数; 第三个参数是单个元素的大小,推荐使用sizeof(s0)这样的表达式; 第四个参数就是让很多人觉得非常困惑的比较函数啦,关于这个函数,还要说的比较麻烦. 我们来讨论cmp这个比较函数(写成cmp是我的个人喜好,你可以随便写成什么,比如qcmp什么的).典型的cmp的定义是int cmp(const void *a,const void *b); 返回值必须是int,两个参数的类型必须都是const void *,那个a,b是我随便写的,个人喜好. 假设是对int排序的话,如果是升序,那么就是如果a比b大返回一个正值,小则负值,相等返回 0,其他的依次类推,后面有例子来说明对不同的类型如何进行排序. 下面举例: No.2.最常见的,对int数组排序 #include #include #include int s10000,n,i; int cmp(const void *a, const void *b) return(*(int *)a-*(int *)b); int main() scanf(%d,&n); for(i=0;in;i+) scanf(%d,&si); qsort(s,n,sizeof(s0),cmp); for(i=0;in;i+) printf(%d ,si); return(0); No.3.对double型数组排序,原理同int这里做个注释,本来是因为要判断如果a=b返回0的,但是严格来说,两个double数是不可能相等的,只能说fabs(a-b)1e-20之类的这样来判断,所以这里只返回了1和-1 #include #include double s1000;