有關排序法qsort詳解

c語言qsort函數詳解

轉自網絡！

qsort函數是ansi c标準中提供的，其聲明在stdlib.h檔案中，是根據二分發寫的，其時間複雜度為n*log(n),其結構為：

void qsort(void *base,size_t nelem,size_t width,int (*comp)(const void *,const void *));

其中：

*base 為要排序的數組

nelem 為要排序的數組的長度

width 為數組元素的大小（一位元組為機關）

預設是從小到大排序的！

（* comp）(const void *p1,const void *p2) 為判斷大小函數的指針，這個函數需要自己定義，如果p1>p2,函數傳回-1；a<b,函數傳回1；a==b函數傳回0

排序方法有很多種：選擇排序，冒泡排序，歸并排序，快速排序等。

看名字都知道快速排序是目前公認的一種比較好的排序算法（我沒聽說速度比這快的了，特殊場合例外），比選擇排序，冒泡排序都要快。這是因為他速度很快，是以系統也在庫裡實作這個算法，便于我們的使用。

這就是qsort。

qsort 要求提供一個比較函數，是為了做到通用性更好一點。比如你不僅僅的是要排序一個數字而已，可能你要用來排序幾個數字，比如有一個結構

struct num

{

int a;

int b;

};

然後我有一個num 類型的數組， num dddd[100];

我想給 dddd這個數組排序，那怎麼辦？我想讓 a +b 最大的num元素排在數組的最前面，那又怎麼辦？

這都可以通過定義比較函數來做到的。

比較函數的作用就是給qsort指明元素的大小是怎麼比較的。

像這樣的比較函數 inline int mycmp(const void* a, const void* b)

都是有兩個元素作為參數，傳回一個int值，如果比較函數傳回大于0，qsort就認為 a>b , 如果比較函數傳回等于0 qsort就認為a 和b 這兩個元素相等，傳回小于零 qsort就認為 a。

qsort 知道元素大小，就可以把大的放到前面去。

如果你的比較函數放回本來應該是1 的（a>b),你比較函數卻傳回一個 -1 （小于零的）那麼qsort認為a的，就把 b放到前面去，但實際上是a大于b的，是以就造成升降序的差别了。

七種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];

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

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

}

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

三、對double類型數組排序（特别要注意）

double in[100];

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);

五、對結構體二級排序

int x;

int y;

//按照x從小到大排序，當x相等時按照y從大到小排序

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;

六、對字元串進行排序

int data;

char str[100];

//按照結構體中字元串str的字典順序排序

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

七、計算幾何中求凸包的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函數包含在<stdlib.h>的頭檔案裡，strcmp包含在<string.h>的頭檔案裡

有關排序法qsort詳解

繼續閱讀

qsort函數使用方法總結（詳細全面+代碼）

你知道的----qsort函數排序這篇之前發過了，介于許多小夥伴回報的排版問題，現已将此排版重發了一、 qsort 函數介紹二、qsort的四個參數解讀三、qsort函數具體例子：