文档章节

快速排序库函数qsort的使用

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:39
字数 2095
阅读 5
收藏 0

               快速排序库函数qsort的使用

    qsort,它包含在<stdlib.h>头文件里,函数一共四个参数,在函数头部加上#include<stdlib.h>,就可以直接调用,并且无需声明。一个典型的qsort的写法如下:

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

    其中第一个参数s是参与排序的数组名(或者也可以理解成开始排序的地址); 第二个参数n是参与排序的元素个数;第三个参数是单个元素的大小,必须 sizeof(s[0])这样的表达式;第四个参数cmp其实是个函数名字,它是为指导qsort如何进行排序而专门写的一个函数,称之为比较函数,其目的是为了告诉qsort要以什么样的方式进行排序(降序?升序?或者按照某个关键字进行排序等)(注:写成cmp只是一个名字,可以随便怎么写),cmp这个函数有形参,和返回值(int型),但是在调用时却不需要给它传递实参进去,直接调用其名字即可,这个函数是专门为qsort开发的一种函数形式,这个函数的典型定义是:

int cmp(const void *a,const void *b);(红色字体是其固定模式,必须这样写,黑色的则是自己随便起的名字),并且规定这个函数只能返回int型值。

关于快排的一些小问题:

1.快排的复杂度,当元素个数比较少时(10^2的数量级左右),快排的速度跟冒泡相比并没有快很多,还有如果要排序的元素大部分都已经是排好顺序了时,快排效率会下降,但是其最坏情况是N^2(当元素全部是已经排好的顺序时),一般情况(也即平均效率)是N*Log2(N),最好情况是N(当元素全部是逆序时),快排的特点是元素越乱排序速度越快,所以可以看出,虽然元素少时使用快排并没有很大优势,但是在快排的最坏情况跟冒泡、选择排序(冒泡、选择排序其复杂度不受元素顺序影响,永远为N^2)一样,所以快排永远是最快的。

2.快排是不稳定的,这里的稳定性是指对于相同元素的处理上,快排会打乱相同元素的先后顺序(原因就在于快排排序原理,其排序过程是不断把元素分组打乱进行的),当然如果单纯排序一列数字是没什么区别的,假设我们有这样一列数字3,3,3,但是三个3是有区别的,我们标记为3a,3b,3c,快排后的结果不一定就是3a,3b,3c这样的排列,所以在某些特定场合我们要用结构体来使其稳定(No.5的例子就是说明这个问题的)

3.快排的比较函数cmp的两个参数必须都是const void *的,这个要特别注意,写a和b只是个人喜好,写成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最常见的,对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 *)a定义了一个指向int型的指针,注意int*两边的括号不能少,然后(int *)a前面加上*就表示取其指向的值。这里返回的是*(int *)a-*(int *)b,两个数相减的顺序跟函数形参顺序一样这样就会将数组按升序排序,反之如果是return(*(int *)b-*(int *)a),就会将数组按降序排列*/

}

void 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\n",s[i]);

}

No.2对double型数组排序,原理和int相似,本来是要判断如果a==b返回0的,但是严格来说,两个double数是不可能相等的,只能说fabs(a-b)<1e-20之类的这样来判断,所以这里只返回了1和-1

#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型数组排序时那样直接返回*(double*)a-*(double*)b,因为这个cmp函数的返回值已经规定了是int型,而*(double*)a-*(double*)b是double型,这里是对这个double型数组进行了升序排列,如果return((*(double*)b-*(double*)a>0)?1:-1)或者return((*(double*)a-*(double*)b>0)?-1:1)则对数组进行降序排列*/

}

void 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\n",s[i]);

}

No.3对一个字符数组排序.原理同int

#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);//这里直接把字符的ASCII码相减来比较字符的先后顺序

}

int main()

{

scanf("%s",s);

n=strlen(s);

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

printf("%s",s);

}

No.4对结构体排序

#include <stdio.h>

#include <stdlib.h>

struct node

{

double date;

int flag;

} s[100];

int i,n;

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

{

return(((struct node *)a)->date > ((struct node *)b)->date?1:-1);/*注意,这里的structnode *跟前面的int*,double*原理一样,都是一种指针类型,这里是自己定义的一个指向结构体的指针类型,故写法为struct 结构体名称 *,这里date是double型数据,故不可能有相等情况出现,只需返回1和-1即可*/

}

int main()

{

scanf("%d",&n);

for(i=0;i<n;i++)

{

s[i].flag=i+1;

scanf("%lf",&s[i].date);

}

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

for(i=0;i<n;i++)

printf("%d%lf\n",s[i].flag,s[i].date);

}

No.5对结构体排序的补充,由于快排具有不稳定性,故需要加入flag标志记录先后顺序,来使其稳定(即data值相等的情况下按flag的值大小排序)

#include <stdio.h>

#include <stdlib.h>

struct node

{

double date;

int flag;

} s[100];

int i,n;

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

{

if(((struct node *)a)->date !=( (struct node *)b)->date)

return(((struct node *)a)->date > ((struct node *)b)->date?1:-1);

else

return(((struct node *)a)->flag - ((struct node *)b)->flag);

}

int main()

{

scanf("%d",&n);

for(i=0;i<n;i++)

{

s[i].flag=i+1;   //flag记录了输入的先后顺序

scanf("%lf",&s[i].date);

}

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

for(i=0;i<n;i++)

printf("%d%lf\n",s[i].flag,s[i].date);

}

No.6对字符串数组的排序(char s[][]型)

#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));/*这里调用了strcmp比较函数,这个函数根据字典序对字符串进行比较,按字符串的先后顺序依次返回1或0或-1*/

}

void 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("%s\n",s[i]);

}

No.7对指针数组排序(char *s[]型)

#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));//注意这里使用char**表示指针的指针

}

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("%s\n",s[i]);

}

附手工实现快排:

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

}

 

© 著作权归作者所有

N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
使用VC库函数中的快速排序函数

上一篇讲了快速排序的实现。但在很多场合,直接使用快速排序的库函数是很方便的。下面讲下VC中库函数qsort()的用法: 函数原型: void qsort(void *base,size_t num,size_t width, int (__cd...

长平狐
2012/12/10
92
0
使用VC库函数中的快速排序函数

上一篇讲了快速排序的实现。但在很多场合,直接使用快速排序的库函数是很方便的。下面讲下VC中库函数qsort()的用法: 函数原型: void qsort(void *base,size_t num,size_t width, int (__cd...

彭博
2012/04/12
193
0
C语言库函数qsort

在我们的实际编程中,我们经常要对数据进行排序,而C的标准库给我们提供了这样一个函数qsort,它的声明如下: void qsort( void *base, size_t num, size_t width, int (__cdecl *compare)(c...

长平狐
2013/12/25
119
0
VC库中快排函数的详解

Author: bakari Date: 2012.8.9 以前都是自己手动写这个算法,觉得也不是一件很麻烦的事,但现在写的程序基本上都用得着快排,重新去写这个算法很没有必要。直接使用VC库中提供的qsort方便了...

chambai
2012/08/11
0
0
关于字符串中字符按ascii码值排序的一些疑问

function template <algorithm> std::sort default (1) template <class RandomAccessIterator>void sort (RandomAccessIterator first, RandomAccessIterator last); custom (2) template <......

zray4u
2016/06/13
134
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部