qsort

qsort函式C語言編譯器函式館自帶的快速排序函式。qsort 的函式原型是void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*)); 是base所指數組進行排序。qsort函式包含在C 標準庫 - <stdlib.h>中。

基本介紹

• 中文名：qsort
• 外文名：qsort
• 套用：C編程
• 類型：標準庫函式
• 頭檔案：stdlib.h
• 功 能：使用快速排序例程進行排序

函式簡介

函式聲明

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

參數

• base-- 指向要排序的數組的第一個元素的指針。
• nitems-- 由 base 指向的數組中元素的個數。
• size-- 數組中每個元素的大小，以位元組為單位。
• compar-- 用來比較兩個元素的函式，即函式指針（回調函式）

回調函式：

回調函式就是一個通過函式指針調用的函式。如果把函式的指針（地址）作為參數傳遞給另一個函式，當這個指針被用來調用其所指向的函式時，就說這是回調函式。

compar參數

compar參數指向一個比較兩個元素的函式。比較函式的原型應該像下面這樣。注意兩個形參必須是const void *型，同時在調用compar 函式（compar實質為函式指針，這裡稱它所指向的函式也為compar）時，傳入的實參也必須轉換成const void *型。在compar函式內部會將const void *型轉換成實際類型。

int compar(const void *p1, const void *p2);

如果compar返回值小於0（< 0），那么p1所指向元素會被排在p2所指向元素的前面；
如果compar返回值等於0（= 0），那么p1所指向元素與p2所指向元素的順序不確定；
如果compar返回值大於0（> 0），那么p1所指向元素會被排在p2所指向元素的後面。

功 能

使用快速排序例程進行排序。

說明

該函式不返回任何值。

頭檔案：stdlib.h；

套用示例

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

int compare( const void *arg1, const void *arg2 );

int main( int argc, char **argv ) {

int i; /* Eliminate argv[0] from sort: */

argv++; argc--; /* Sort remaining args using Quicksort algorithm: */

qsort( (void *)argv(size_t)argc, sizeof( char * ), compare ); /* Output sorted list: */

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

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

printf( "\n" );

}

int compare( const void *arg1, const void *arg2 ) { /* Compare all of both strings: */

return _stricmp( * ( char** ) arg1, * ( char** ) arg2 );

}

用法說明

qsort函式的用法說明如下：

例：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; 為由大到小排序。

以下為compare函式原型 //comp

compare( (void *) & elem1, (void *) & elem2 );

Compare 函式的返回值	描述
< 0	elem1將被排在elem2前面
0	elem1 等於 elem2
> 0	elem1 將被排在elem2後面

（1）對一維數組的排序實例（從小到大排序）：

#include<stdio.h>#include<stdlib.h>int comp(const void*a,const void*b){return *(int*)a-*(int*)b;}int main(){int i=0;int *array;int n;scanf("%d",&n);array=(int*)malloc(n*sizeof(int));for(;i<n;i++){scanf("%d",(array+i));}qsort(array,n,sizeof(int),comp);for(i=0;i<n;i++){printf("%d\t",array[i]);}return 0;}

對一個二維數組進行排序：

int a[1000][2]; 其中按照a[0]的大小進行一個整體的排序，其中a[1]必須和a[0]一起移動交換。//即第一行和第二行（a[0]和a[1]分別代表第一行和第二行的首地址）。使用庫函式排序的代碼量並不比用冒泡排序法小，但速度卻快很多。

qsort(a,1000,sizeof(int)*2,comp);int comp(const void*a,const void*b){return((int*)a)[0]-((int*)b)[0];}

（2）對字元串進行排序

int Comp(const void*p1,const void*p2){return strcmp((char*)p2,(char*)p1);}int main(){char a[MAX1][MAX2];initial(a);qsort(a,lenth,sizeof(a[0]),Comp);//lenth為數組a的長度

（3）按結構體中某個關鍵字排序（對結構體一級排序）：

structNode{double data;int other;}s[100];int Comp(constvoid*p1,constvoid*p2){return(*(Node*)p2).data>(*（Node*）p1).data?1:-1;}qsort(s,100,sizeof(s[0]),Comp);

按結構體中多個關鍵字排序（對結構體多級排序）[以二級為例]：

struct Node{int x;int y;}s[100];//按照x從小到大排序，當x相等時按y從大到小排序int Comp(const void*p1,const void*p2){struct Node*c=(Node*)p1;struct Node*d=(Node*)p2;if(c->x!=d->x)returnc->x-d->x;else return d->y-c->y;}

對結構體中字元串進行排序：

struct Node{int data;char str[100];}s[100];//按照結構體中字元串str的字典序排序int Comp(const void*p1,const void*p2){return strcmp((*(Node*)p1).str,(*(Node*)p2).str);}qsort(s,100,sizeof(s[0]),Comp);

（4）計算幾何中求凸包的Comp

int Comp(const void*p1,const void*p2)//重點Comp函式，把除了1點外的所有的點旋轉角度排序{struct point*c=(point*)p1;struct point*d=(point*)p2;if(cacl(*c,*d,p[1])<0) return1;elseif(!cacl(*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))//如果在一條直線上，則把遠的放在前面return1;elsereturn-1;}