qsort和sort学习与比较
阅读另一篇博文Uva 642 - Word Amalgamation sort qsort
1.qsort函数:
原 型: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
功 能: 使用快速排序例程进行排序
参 数:
1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的指针,用于确定排序的顺序
说 明:qsort函数是ANSI C标准中提供的,其声明在stdlib.h文件中,是根据二分法写的,其时间复杂度为n*log(n)。
qsort要求提供的函数是需要自己定义的一个比较函数,比较函数使得qsort通用性更好。有了比较函数qsort可以实现对数组、字符串、结构体等结构进行升序或降序排序。
如int cmp(const void *a, const void *b)中有两个元素作为参数(参数的格式不能变的。)返回一个int值,如果比较函数返回大于0,qsort就认为a > b,返回小于0,qsort就认为a < b。qsort知道元素的大小了,就可以把大的放前面去。如果你的比较函数返回本来应该是1的(即a > b),而却返回-1(小于0的数),那么qsort认为a < b,就把b放在前面去,但实际上是a > b的,所以就造成了降序排序的差别了。简单来说,比较函数的作用就是给qsort指明元素的大小事怎么比较的。
2.qsort中几种常见的cmp函数:
一、对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;
}
3.sort和qsoort比较:
1.cmp函数和qsort中cmp函数的不同
int cmp(const int &a,const int &b)
{
return a>b
}
Sort中的cmp函数参数可以直接是参与比较的引用类型。
2.cmp函数比较时qsort用“-”,而sort用”>”.这也是一个重要的区别。
3.sort函数是c++中标准模板库的的函数,在qsort()上已经进行了优化,根据情况的不同可以采用不同的算法,所以较快。在同样的元素较多和同样的比较条件下,sort()的执行速度都比qsort()要快。另外,sort()是类属函数,可以用于比较任何容器,任何元素,任何条件。使用时需调用<algorithm>
sort(begin(),end(),cmp),
最新文章
- jquery实现点击上移到顶部功能(转)
- 【Codeforces 723D】Lakes in Berland (dfs)
- 如何通过源码生成Gatling可执行工具
- 高校应该使用 Drupal 的10大理由
- hdu 2715 Herd Sums
- Extjs4-treepanel-解析json/fields中是否加入leaf的区别
- [置顶] 获取激活码,激活myeclipse
- JQuery解析HTML、JSON和XML实例详解
- Collaborative Filtering(协同过滤)算法详解
- ORACLE复杂查询之连接查询
- 防火墙iptables的简单使用
- ANTLR v4 权威参考笔记(目录)
- Docker入门基础(一)
- 用矩阵和待定系数法求数列的分析(复杂度log(n))
- strerror函数的总结【转】
- ZZNU 正约数之和 2094
- Python多线程-Barrier(障碍对象)
- 2016年蓝桥杯B组C/C++省赛(预选赛)试题
- 网易云音乐综合爬虫python库NetCloud v1版本发布
- ES6-let、const和块级作用域
热门文章
- 妙味课上利用splice进行数组去重为什么要 j--
- Vulkan移植GpuImage(二)Harris角点检测与导向滤波
- Android 之 使用 Intent 在活动间传递数据
- Spring IOC 特性有哪些,不会读不懂源码!
- [二分匹配]Asteroids
- 学习笔记-vue 打包去#和页面空白问题
- [.net] 关于Exception的几点思考和在项目中的使用(二)
- 梳理一下最近准备蓝桥杯时学习DP问题的想法
- 带你全面认识CMMI V2.0(四)——管理 赋能
- 201871030108-冯永萍 实验二 个人项目— D{0-1}背包问题项目报告