Month: 八月 2008

快排qsort的用法详解 (两年前的原创)

发信人: snoopy (阿排/好好玩ICPC~), 信区: ACM_ICPC
标 题: 快排qsort的用法详解
发信站: 珞珈山水BBS站 (Sat Apr 29 21:02:35 2006), 转信

很多人问这个东西.我以前也看了好久,今天翻到以前学快排的时候写的练习code,基本上
能覆盖绝大部分用法了.

里面有很多地方没判断相等的情况,按道理来说相等情况下应该返回0的,这个请看代码的
时候注意.我尽量保证代码不出错了.

下面的这些说明和问题都是个人原创,没查什么资料,所以不保证其完全正确性,在此表示个
人不对出现的问题负任何责任,大家WA了或者干吗的不要怪我,不过至少目前来说我用起来
是没问题的 :)

/*—————————————————————————-*/

** 关于快排函数的一些说明 **

qsort,包含在stdlib.h头文件里,函数一共四个参数,没返回值.一个典型的qsort的写法如下

qsort(s,n,sizeof(s[0]),cmp);

其中第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&s[i]
这样的表达式,这个问题下面有说明); 第二个参数是参与排序的元素个数; 第三个三数是
单个元素的大小,推荐使用sizeof(s[0])这样的表达式,下面也有说明 :) ;第四个参数就是
很多人觉得非常困惑的比较函数啦,关于这个函数,还要说的比较麻烦…

我们来讨论cmp这个比较函数(写成cmp是我的个人喜好,你可以随便写成什么,比如qcmp什么
的).典型的cmp的定义是

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

返回值必须是int,两个参数的类型必须都是const void *,那个a,b是我随便写的,个人喜好.
假设是对int排序的话,如果是升序,那么就是如果a比b大返回一个正值,小则负值,相等返回
0,其他的依次类推,后面有例子来说明对不同的类型如何进行排序.

在函数体内要对a,b进行强制类型转换后才能得到正确的返回值,不同的类型有不同的处理
方法.具体情况请参考后面的例子.

/*—————————————————————————-*/

** 关于快排的一些小问题 **

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

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

3.快排的比较函数的两个参数必须都是const void *的,这个要特别注意,写a和b只是我的
个人喜好,写成cmp也只是我的个人喜好.推荐在cmp里面重新定义两个指针来强制类型转换,
特别是在对结构体进行排序的时候

4.快排qsort的第三个参数,那个sizeof,推荐是使用sizeof(s[0])这样,特别是对结构体,
往往自己定义2*sizeof(int)这样的会出问题,用sizeof(s[0)既方便又保险

5.如果要对数组进行部分排序,比如对一个s[n]的数组排列其从s[i]开始的m个元素,只需要
在第一个和第二个参数上进行一些修改:qsort(&s[i],m,sizeof(s[i]),cmp);

/*—————————————————————————-*/

** 标程,举例说明 **

No.1.手工实现QuickSort

#include <stdio.h>

int a[100],n,temp;

void QuickSort(int h,int t)
{
     if(h>=t) return;
     int mid=(h+t)/2,i=h,j=t,x;
     x=a[mid];
     while(1)
     {
         while(a[i]<x) i++;
         while(a[j]>x) j--;
         if(i>=j) break;
         temp=a[i];
         a[i]=a[j];
         a[j]=temp;
     }
     a[mid]=a[j];
     a[j]=x;
     QuickSort(h,j-1);
     QuickSort(j+1,t);
     return;
}

int main()
{
     int i;
     scanf("%d",&n);
     for(i=0;i<n;i++) scanf("%d",&a[i]);
     QuickSort(0,n-1);
     for(i=0;i<n;i++) printf("%d ",a[i]);

     return(0);
}

No.2.最常见的,对int数组排序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int s[10000],n,i;

int cmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

int main()
{
     scanf("%d",&n);
     for(i=0;i<n;i++) scanf("%d",&s[i]);
    
     qsort(s,n,sizeof(s[0]),cmp);
    
     for(i=0;i<n;i++) printf("%d ",s[i]);
    
     return(0);
}

No.3.对double型数组排序,原理同int

这里做个注释,本来是因为要判断如果a==b返回0的,但是严格来说,两个double数是不可能相等的,只能说fabs(a-b)<1e-20之类的这样来判断,所以这里只返回了1和-1 [code lang="c"]#include <stdio.h> #include <stdlib.h> double s[1000]; int i,n; int cmp(const void * a, const void * b) { return((*(double*)a-*(double*)b>0)?1:-1); } int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf",&s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%lf ",s[i]); return(0); } [/code] No.4.对一个字符数组排序.原理同int [code lang="c"]#include <stdio.h> #include <string.h> #include <stdlib.h> char s[10000],i,n; int cmp(const void *a,const void *b) { return(*(char *)a-*(char *)b); } int main() { scanf("%s",s); n=strlen(s); qsort(s,n,sizeof(s[0]),cmp); printf("%s",s); return(0); }[/code] No.5.对结构体排序 注释一下.很多时候我们都会对结构体排序,比如校赛预选赛的那个樱花,一般这个时候都在 cmp函数里面先强制转换了类型,不要在return里面转,我也说不清为什么,但是这样程序会 更清晰,并且绝对是没错的. 这里同样请注意double返回0的问题 [code lang="c"]#include <stdio.h> #include <stdlib.h> struct node { double date1; int no; } s[100]; int i,n; int cmp(const void *a,const void *b) { struct node *aa=(node *)a; struct node *bb=(node *)b; return(((aa->date1)>(bb->date1))?1:-1); } int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i].no=i+1; scanf("%lf",&s[i].date1); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d %lfn",s[i].no,s[i].date1); return(0); }[/code] No.6.对结构体排序.加入no来使其稳定(即data值相等的情况下按原来的顺序排) [code lang="c"]#include <stdio.h> #include <stdlib.h> struct node { double date1; int no; } s[100]; int i,n; 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)); } int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i].no=i+1; scanf("%lf",&s[i].date1); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d %lfn",s[i].no,s[i].date1); return(0); } [/code] No.7.对字符串数组的排序(char s[][]型) [code lang="c"]#include <stdio.h> #include <string.h> #include <stdlib.h> char s[100][100]; int i,n; int cmp(const void *a,const void *b) { return(strcmp((char*)a,(char*)b)); } int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%sn",s[i]); return(0); }[/code] No.8.对字符串数组排序(char *s[]型) [code lang="c"]#include <stdio.h> #include <string.h> #include <stdlib.h> char *s[100]; int i,n; int cmp(const void *a,const void *b) { return(strcmp(*(char**)a,*(char**)b)); } int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i]=(char*)malloc(sizeof(char*)); scanf("%s",s[i]); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%sn",s[i]); return(0); }[/code]

歌唱我们亲爱的祖国 – 奥运会开幕式

刚看完第三遍开幕式, 第一遍是 CCTV 直播的, 觉得不错, 第二遍是昨天晚上看的 TVB 高清翡翠台, 很好, 第三遍是刚看的 NBC 720p 高清的, 弥补细节, 更赞

直播时 CCTV 的还能凑合, 国家电视台通病, 领导人镜头太多, 表演镜头太少, 很多人抱怨为啥给那么多镜头到主席台及后面的领导人身上, 特别是前 core 夫人, 看起来病怏怏的, 太影响形象了. 其他的还好, 表演有不少精彩镜头被 CCTV 切回自己的信号导致错过一些, 然后就是镜头距离控制不好, 导致很多远景效果被拍演员拍傻了.

TVB 据说是和 CCTV 一个信号源, 看起来确实是, 但是就因为少了很多领导人镜头(几乎没有), 对场面的效果又要好很多, 特别是解说不跟 CCTV 那么聒噪, CCTV 解说的太烦了. 这个高清版本(720*576) 已经可以看到非常多原来没注意到的细节, 推荐下载, 粤语解说.

NBC 的镜头几乎都是自己剪的, 1280*720 的高清, 前面有很长一段对中国的介绍, 对比了下改革开放前和现在, 大赞中国, 不过中间比较不和谐的有几秒八九年的画面, 后面有特别提到四川. 整个过程表演效果是最好的, 但是中间有剪切, 就是表演每个大块中衔接的那部分, 看起来感觉会有点跳. 前面有一段对运动员的采访, 他们都说了一句话 “Not the Triumph but the struggle”, 中文, 我觉得我很难翻译出那种精妙的意思, “不是庆祝凯旋, 而是努力奋斗”, 这才是奥林匹克精神的精髓吧.

开场
数码缶倒计时, 推荐看 NBC 的, 大家镜头差不多, 高清的更爽, TVB 的这里有给解说词, 有朋自远方来, 不亦乐呼, NBC 的几个解说都很中国通, 用英语比较完美的介绍台词.

脚印, 五环焰火
看脚印去看 NBC 的, 高清的就是好, 一路过来都能看到地面上庆祝的人群, 最后的那个奥运五环焰火, 在三个版本中似乎都没看到, 只有一些照片有, 并且都不是特别好.

歌唱祖国
林妙可, 这个名字现在应该是家喻户晓, 相比较而言, NBC 的解说似乎更好一些, 还简要的介绍了一下这个北京的 9 岁小姑娘, 并且镜头一直给的是国旗正后方汉族小姑娘(ps. 以她的方位感, 在她右后方那个小 MM 似乎更 PP).

升旗
这个建议看 TVB 版的, 解说当时也都起立在唱国歌. 直播以及每场录像, 我还是会起立站好一起唱国歌, 这是民族荣耀和国家骄傲, 不需要国旗国歌国徽法来约束.

画卷, 论语, 活字印刷
NBC 的把这里剪掉了前面造纸, 文房四宝, 绘画过程, 如果只看这个会莫名其妙, 建议 TVB. 后面绘画以及活字印刷表演, NBC 的镜头挺好, 非常清楚主要是, 还有就是最后一片桃花, 强烈 bs 该死的 CCTV, 一点都没表现好, TVB 的也没给出太好的全景, NBC 的好一些, 不过对论语的解读, TVB 的要好. 经典一段, NBC 的解说, 在活字印刷表现桃花时, 说他们怎么做到的, oh~ people…. 没有使用计算机或者其他的高科技.

丝绸之路, 海上丝绸之路
这一段 CCTV 完全就在莫名其妙, 特别是海上那段, 一直都是近景, 出远景的时候又在给主席台, 让老谋子想表现的全没了, 实际上那么多划桨的组成过很多图案和大小船只(不仅仅是他们划的桨上的画), TVB 的就要好, NBC 的更好, 只是没解说.

礼乐
这一段我没什么鉴赏力, CCTV 的没把柱子上弹琵琶的人给出, TVB 的有, NBC 的有特写.

LED 绿人, 鸟巢, 和平鸽, 钢琴, 放风筝
推荐 NBC 的, 镜头就只有一开始给了下朗朗和那个被骂死了的跟盲人一样只知道看前方的傻丫头, TVB 的很明显能看到那小丫头在不停抠脸抠鼻孔, 倒是很能配合网络上的传闻. NBC 有介绍两人, 个人不喜欢朗朗, 弹琴都跟抽风一样, 还是李云迪更帅一些, 那个小姑娘叫李木子. 很佩服那些人最后搭鸟巢的时候, 完全就是超级人梯/叠罗汉啊, 太赞了.

太极, 小朋友绘画
NBC 似乎有剪掉点什么, 反正我觉得转换有点突然. 这一段 TVB 的解说好, NBC 的画面好, NBC 的解说其实说得也还不错, 介绍说 “气” 是中国人认为的一切起源和万物之本, blablabla(能感觉那个意思, 但是要我完全英语口译还是不行). 最后上色及给太阳加上笑脸的画稿最终版, NBC 的最清楚, 特别好看, 比 CCTV 的好看了不知道多少.

宇航员, 地球, 主题歌, 笑脸
NBC 的非常清晰, 主题歌 TVB 有中英文字幕, 才知道英文怎么唱的, 最后的笑脸, NBC 的表现最好, 地面上的全是最后运动员入场的志愿者撑开的伞面, 特别有感染力, CCTV 几乎就没给我们看到. 笑脸的焰火似乎只有 TVB 中有一点, NBC 的没看到, 在歌快唱完的时候在鸟巢上空出现的, 玩焰火, 果然还是咱们中国比较牛.

运动员入场
在此再次强烈鄙视 CCTV, 每个国家出来都只知道调侃人家的奥运会成绩, 从没拿过金牌什么的, 奥运会是更高更快更强, 又不是金牌大赛, 欺负小国.
NBC 的介绍就要好很多, 对每个国家棋手也都有字幕介绍, 当然, 这里镜头给美国的有点多, 特别是美国进去后别的国家进场后镜头还经常在美国运动员身上.
在 NBC 的版本里终于看清楚了志愿者腰上到底是什么, 开始看直播觉得是水, 后来看 TVB 的时候想是不是笑脸伞收起来挂腰上了, 后来看到确定还是矿泉水, 并且很多人到后面都空了, 不知道是不是给热死了的运动员. 志愿者跳的确实非常累, 两个多小时吧, 太辛苦了.
CCTV 的这里给了非常多他国领导人的镜头, 就看见一群人被热死了…

中国入场
从 NBC 版本里很清楚的看到, 林浩是姚明进来很有一段才走到他身边的, 被志愿者拉着跑进来, 脖子上的证件看起来也更临时一些, 网络上说他差点不能进场估计是真的, 跑的很匆忙, 手里居然还有一只白板笔, 那个被很多人指责的国旗, 应该只是拿倒了, 然后小棍戳到另一头. 很赞林浩, NBC 的特意介绍了很久, 比 TVB 都多, 更不用说那个几乎什么也没说的 CCTV 了, 后面 NBC 的镜头也一直在 big YaoMing and little LinHao (原文) 身上, 特别可爱.
TVB 的三个现场解说在中国入场的时候都站起来了, 在上面挥国旗, 现场效果非常好.

刘淇/罗格致辞, 会旗入场, 放飞和平鸽, 运动员/裁判员宣誓
还是感慨下现场观众的英文, 罗格的讲话经常被不恰当的掌声打断, 看来还是不习惯中国的领导特色, 怎么顿才能让别人恰到好处的鼓掌.
会旗入场有点久, NBC 的把前面直接掐掉了, 上来就是会旗给仪仗队. 放飞和平鸽和运动员/裁判员宣誓 NBC 也弄没了, 很有点不厚道.

火炬入场, 点火
NBC 对火炬手的介绍更好一些, 没太多废话. 最后李宁跑的那一圈, CCTV 一直给那么近, 就看见吊的钢丝了, 其实李宁是一路跑来, 就是圣火传递的路线的电视画面, 希腊, 北京, 土耳其, 国外一圈后回到国内, 最后在四川, 北京, 点火的时候看特别清楚.

离场
CCTV 点火后就没了, 害我一直还在等开始前 CCTV 采访韩红说结束时的演出, NBC 也没, TVB 据说有转, 但是下到的版本里就成龙唱了一句就完了, anyway, 赞 TVB 全程转播完了.


总结: 这样的大型活动还是在现场更好, 现场还是完全自主的观看, 并且能看到很多转播中不一定有的精彩画面, 要看细节回来还是有很多录播的看(比如 NBC 这个还是非常好的弥补和回忆用). 不过老谋子估计没考虑好现场是个圆形的, 似乎只有主席台那个方向效果好一些.

赞中国, 赞奥运, 奥林匹克是全民的更高更快更强, 而不是单纯的国家训练结果奖牌大比拼, 国内的某些宣传总有些走样, 所以导致很长一段时间都在反感, 再者带来的诸多不便也似乎过分了点.

Enjoy the games.