qsort函数简介

c函数qsort()和bsearch()的用法

举例

c代码

qsort图

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 a[1000]; 那么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;

}

上面是由小到大排序，return *(int *)b-*(int *)a; 为由大到小排序。

是对一个二维数组的进行排序：

int a[1000][2]; 其中按照a[0]的大小进行一个整体的排序，其中a[1]必须和a[0]一起移动交换。

qsort(a,1000,sizeof(int)*2,comp);

int comp(const void *a,const void *b)

{

return ((int *)a)[0]-((int *)b)[0];

}

举例

举例1：

char a[1000][20];

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 str1[11];

char str2[11];

}str,*stri;

str strin[100001]=;

int compare(const void *a,const void *b)

{

return strcmp( ((str*)a)->str2 , ((str*)b)->str2 );

}

qsort(strin,total,sizeof(str),compare);

#include <iostream>

using namespace std;

#include <stdlib.h>

#include <string.h>

int compare( const void *a, const void *b);

char * list[5]= {"cat","car","cab","cap","can"};

int main()

举例2：(C/C++例程)

按字符串长度对字符串进行排序：

#include<iostream>

#include<cstdlib>

#include<string.h>

#define N 8

using namespace std;

int compare(const void *a,const void *b);

int main(void)

{

int i;

char s[8][10]={"January","February","March","April","May","June","July","September"};

qsort(s,8,sizeof(char)*10,compare);

for(i=0;i<8;i++)

cout<<s[i]<<endl;

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 <stdlib.h>

#include <stdio.h>

#include <string.h>

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;i<argc;++i)

printf("%s\",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 = array[1..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 a[i]<x do inc(i);

while x<a[j] do dec(j);

if i<=j then

begin

y:=a[i];a[i]:=a[j];a[j]:=y;

inc(i);dec(j);

end;

until i>j;

if l<j then sort(l,j);

if i<r 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..10000000]of 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 save[i]<mid do inc(i); //在中间这个数字的左边，找比中间数大的数字

while save[j]>mid do dec(j);//在中间数右边，找比中间数小的数字

if i<=j//如果左指针在右指针左边

then begin

em:=save[i];//交换2个数字的值，这个你会冒泡排序，或者选择排序任意一个，应该明白

save[i]:=save[j];

save[j]:=em;

inc(i);

dec(j);

end;

until i>j;//左指针跑到右指针右边了。。。

if i<y then qsort(i,y);//如果左指针，没到界限，那么 从左指针到界限进行上述排序

if j>x then qsort(x,j);//如果右指针没跑到，左界限，那么从右指针到左界限排序

end;

begin

randomize;//优化程序用的，暂时你不用会

readln(n);//读入，表示有N个数字

for i:=1 to n do//读入这N个数字

read(save[i]);

qsort(1,n);//从第一个数字，到最后一个数字排序

for i:=1 to n do//输出

write(save[i],' ');

end.

一个典型的qsort的写法如下qsort(s,n,sizeof(s[0]),cmp);

其中第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&s[i]这样的表达式);

第二个参数是参与排序的元素个数;

第三个参数是单个元素的大小,推荐使用sizeof(s[0])这样的表达式;

第四个参数就是让很多人觉得非常困惑的比较函数啦,关于这个函数,还要说的比较麻烦...

我们来讨论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 <stdio.h>

#include <string.h>

#include <stdlib.h>

int s[10000],n,i;

int cmp(const void *a, const void *b)

{

return(*(int *)a-*(int *)b);

}

int main()

{

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%d",&s[i]);

qsort(s,n,sizeof(s[0]),cmp);

for(i=0;i<n;i++)

printf("%d ",s[i]);

return(0);

}

No.3.对double型数组排序,原理同int这里做个注释,本来是因为要判断如果a==b返回0的,但是严格来说,两个double数是不可能相等的,只能说fabs(a-b)<1e-20之类的这样来判断,所以这里只返回了1和-1

#include <stdio.h>

#include <stdlib.h>

double s[1000];

int i,n;

int cmp(const void * a, const void * b)

{

return((*(double*)a-*(double*)b>0)?1:-1);

}

int main()

{

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%lf",&s[i]);

qsort(s,n,sizeof(s[0]),cmp);

for(i=0;i<n;i++)

printf("%lf ",s[i]);

return(0);

}

c代码

国际C语言混乱代码大赛

（IOCCC, The International Obfuscated C Code Contest）是一项国际编程赛事，从1984年开始，每年举办一次（1997年、1999年、2002年、2003年和2006年例外）。目的是写出最有创意的最让人难以理解的C语言代码。

作品从线上提交，并经过好几回合的裁判的审核。作品审核是基于滥用混乱代码的程度（以及创造性的滥用）。作品通过最后一轮审核的会被归成其特别的一类以示嘉奖，例如“最滥用C前处理器”或者“最古怪的行为”，并且发表在官方IOCCC网站。作品没有通过者会被删除或遗忘；该赛事主办声明：作品被宣告在IOCCC网站是竞赛的锦标。

历史

IOCCC是由蓝登·克特·诺尔（Landon Curt Noll）与拉里·贝索（Larry Bassel）在1984年受雇于国家半导体（National Semiconductor）的Genix程式移殖事业群时开始的。比赛的点子是来自他们俩比较彼此有关于它们得修正的某些写得很烂代码的笔记。

qsort图