qsort 排序

今天药忘吃喽~ 2022-08-25 05:28 159阅读 0赞

**原文地址：**[qsort 排序][qsort] **作者：** [小ZZ][ZZ]

1.快排是不稳定的,这个不稳定一个表现在其使用的时间是不确定的,最好情况(O(n))和最坏情况(O(n^2))差距太大,我们一般说的O(nlog(n))都是指的是其平均时间.

2.快排是不稳定的,这个不稳定表现在如果相同的比较元素,可能顺序不一样,假设我们有这样一个序列,3,3,3,但是这三个3是有区别的,我们标记为3a,3b,3c,快排后的结果不一定就是3a,3b,3c这样的排列,所以在某些特定场合我们要用结构体来使其稳定(No.6的例子就是说明这个问题的)

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

**一、** **对int类型数组排序**

int num\[100\];

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 \- \*(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;   
\}

**No.6.对结构体排序.加入no来使其稳定(即data值相等的情况下按原来的顺序排)**

int cmp(const void \*a,const void \*b)  
\{   
struct node \*aa=(node \*)a;  
struct node \*bb=(node \*)b;  
if(aa->date1!=bb->date1)  
return(((aa->date1)>(bb->date1))?1:-1);  
else  
return((aa->no)-(bb->no));  
\}

**PS:其中的qsort函数包含在<stdlib.h>的头文件里，strcmp包含在<string.h>的头文件里** **。**

[qsort]: http://blog.sina.com.cn/s/blog_63a1163f0100jxri.html
[ZZ]: http://blog.sina.com.cn/u/1671501375