qsort()排序

C语言中用qsort()快速排序

C语言中排序的算法有很多种，系统也提供了一个函数qsort()可以实现快速排序。原型如下：

 

void qsort(void *base, size_t nmem, size_t size, int (*comp)(const void *, const void *));

它根据comp所指向的函数所提供的顺序对base所指向的数组进行排序，nmem为参加排序的元素个数，size为每个元素所占的字节数。例如要对元素进行升序排列，则定义comp所指向的函数为：如果其第一个参数比第二个参数小，则返回一个小于0的值，反之则返回一个大于0的值，如果相等，则返回0。

例：

#include <stdio.h>
#include <stdlib.h>

int comp(const void *, const void *);

int main(int argc, char *argv[])
{
    int i;
    int array[] = {6, 8, 2, 9, 1, 0};

    qsort(array, 6, sizeof(int), comp);

    for (i = 0; i < 6; i ++) {
        printf("%d\t", array[i]);
    }
    printf("\n");

    return 0;
}

int comp(const void *p, const void *q)
{
    return (*(int *)p - *(int *)q);
}

运行结果如下：

0 1 2 6 8 9

以上部分来自：http://blog.chinaunix.net/u/22520/showart_232703.html

qsort
　　功 能: 使用快速排序例程进行排序
　　用 法: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
　　各参数：1 待排序数组首地址 2 数组中待排序元素数量 3 各元素的占用空间大小 4 指向函数的指针，用于确定排序的顺序
　　程序例:
　　#include
　　using namespace std;
　　#include
　　#include
　　int compare( const void *a, const void *b);
　　char * list[5]= {"cat","car","cab","cap","can"};
　　int main()
　　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　　while x　　if i<=j then
　　begin
　　y:=a;a:=a[j];a[j]:=y;
　　inc(i);dec(x);
　　end;
　　until i>j;
　　if l　　if i　　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.
　　c/c++
　　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;
　　}
　　是对一个二维数组的进行排序：
　　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];
　　}
　　对字符串进行一个排序：
　　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
　　#include
　　#include
　　#define N 8
　　int compare(const void *a,const void *b);
　　void main()
　　{
　　char s[8][10]={"January","February","March","April","May","June","July","September"};
　　int i;
　　qsort(s,8,sizeof(char)*10,compare);
　　for(i=0;i　　cout<　　}
　　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));
　　}//vc++ 6.0
　　
　　// 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;i　　{
　　printf("%s ",argv);
　　printf("\n");
　　}
　　}
　　int compare(const void *arg1,const void *arg2)
　　{
　　return _stricmp(*(char **)arg1,*(char **)arg2);
　　}
　　在运行输入cmd,在qsort.exe 参数1 参数2
　　将会排序

Source：

以上部分来自：http://blog.csdn.net/maray/archive/2009/03/27/4030123.aspx

qsort函数应用大全(转)

七种qsort排序方法

<本文中排序都是采用的从小到大排序>

一、对int类型数组排序

int num[100];

Sample:

int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

qsort(num,100,sizeof(num[0]),cmp);

二、对char类型数组排序（同int类型）

char word[100];

Sample:

int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}

qsort(word,100,sizeof(word[0]),cmp);

三、对double类型数组排序（特别要注意）

double in[100];

int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}

qsort(in,100,sizeof(in[0]),cmp)；

四、对结构体一级排序

struct In
{
double data;
int other;
}s[100]

//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写

int cmp( const void *a ,const void *b)
{
return (*(In *)a)->data > (*(In *)b)->data ? 1 : -1;
}

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

五、对结构体二级排序

struct In
{
int x;
int y;
}s[100];

//按照x从小到大排序，当x相等时按照y从大到小排序

int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}

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

六、对字符串进行排序

struct In
{
int data;
char str[100];
}s[100];

//按照结构体中字符串str的字典顺序排序

int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}

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

七、计算几何中求凸包的cmp

int cmp(const void *a,const void *b) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上，则把远的放在前面
return 1;
else return -1;
}

PS:

其中的qsort函数包含在的头文件里，strcmp包含在的头文件里

最后一部分来自：http://www.cppblog.com/qywyh/articles/3405.html