-
qsort
鎖定
- 中文名
- qsort
- 外文名
- qsort
- 應 用
- C編程
- 類 型
- 標準庫函數
- 頭文件
- stdlib.h
- 功 能
- 使用排序例程進行排序
qsort函數簡介
qsort函數聲明
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
qsort參數
- 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所指向元素的順序不確定；
qsort功 能
使用排序例程進行排序。
qsort説明
該函數不返回任何值。
頭文件：stdlib.h；
qsort應用示例
#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;
}
