qsort函数的用法

2011-03-28 16:11:26|分类： 默认分类 |标签： |字号大中小订阅

六类qsort排序方法

前一段时间做题觉得qsort函数很好用，但有时不太会用比如按结构体一级排序、二级排序、字符串排序等，故通过查资料将其整理一番。

以下是其具体分类及用法(若无具体说明是以降序排列)：

1、对一维数组排序：

（Element_type是一位数组中存放的数据类型，可以是char, int, float, double, etc ）

  1. int Comp(const void *p1,const void *p2 )
  3. {
  5. return *((Element_type *)p2) > *((Element_type *)p1) ? 1 : -1;
  7. }
  9. int main()
  11. {
  12. Element_type list[MAX];
  14. initial(list);
  16. qsort(list, sizeof(list),sizeof(Element_type),Comp);
  18. return 0;
  20. }

复制代码

2、对字符串排序：

  1. int Comp(const void *p1,const void *p2)
  3. {
  5. return strcmp((char *)p2,(char *)p1);
  7. }
  9. int main()
  11. {
  13. char a[MAX1][MAX2];
  15. initial(a);
  17. qsort(a,lenth,sizeof(a[0]),Comp);
  19. //lenth 为数组a的长度

复制代码

3、按结构体中某个关键字排序（对结构体一级排序）：

  1. struct Node
  3. {
  5. double data;
  7. int other;
  9. }s[100];
  11. int Comp(const void *p1,const void *p2)
  13. {
  15. return (*(Node *)p2).data > (*（Node *）p1).data ? 1 : -1;
  17. }
  19. qsort(s,100,sizeof(s[0]),Comp);

复制代码

4、按结构体中多个关键字排序（对结构体多级排序）[以二级为例]：

  1. struct Node
  3. {
  4. intx;
  6. int y;
  8. }s[100];
  10. //按照x从小到大排序，当x相等时按y从大到小排序
  12. int Comp(const void *p1,const void *p2)
  14. {
  16. struct Node*c = (Node *)p1;
  18. struct Node *d = (Node *)p2;
  20. if(c->x != d->x) return c->x-d->x;
  22. else return d->y - c->y;
  24. }

复制代码

5、对结构体中字符串进行排序：

  1. struct Node
  3. {
  5. int data;
  7. char str[100];
  9. }s[100];
  11. //按照结构体中字符串 str 的字典序排序
  13. int Comp(const void *p1,const void *p2)
  15. {
  17. return strcmp((*(Node *)p1).str,(*(Node *)p2).str);
  19. }
  21. qsort(s,100,sizeof(s[0],Comp);

复制代码

6、计算几何中求凸包的Comp

  1. //以下是俺从别人那儿抄来的，暂时还没用过
  3. int Comp(const void *p1,const void *p2)
  5. //重点Comp函数，把除了1点外的所有的点旋转角度排序
  7. {
  9. struct point*c=(point *)p1;
  11. struct point *d=(point *)p2;
  13. if( cacl(*c, *d,p[1]) < 0) return 1;
  15. else if(!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 ) )
  17. //如果在一条直线上，则把远的放在前面
  19. return 1;
  21. elsereturn -1;
  23. }

复制代码

P.S.:qsort函数是ANSIC标准中提供的，其声明在stdlib.h文件中，是根据二分发写的，其时间复杂度为n*log(n),其结构为：

  1. 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。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。