深入理解qsort

qsort用法

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *p1,const void *p2)
{
	int *m=(int *)p1;
	int *n=(int *)p2;
	return *m-*n;
}
int main()
{
	int a[10]={2,6,8,3,5,9,0,4,2,6};
	qsort(a,10,4,cmp);
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

1.引入库#include<stdlib.h>,否则不能用qsort。
2.根据实际需要写cmp函数。
3.在main函数中引用qsort。

是不是很方便,学过快排以后我都没有用过其他排序方式了,快排功能多,速度快,请务必掌握,为了理解快排为什么长这样,接下来讲一些预备知识。

内存中变量的储存方式

int a[5][5];

在我们的直观印象里,二维数组

a

[

5

]

[

5

]

a[5][5]

a[5][5]应该长得像是长方形,五行五列,就像取

x

y

xy

xy坐标一样,第

x

x

x行第

y

y

y列就是

a

[

x

]

[

y

]

a[x][y]

a[x][y]

当然这只是一种形象的理解而已,二维数组在内存中的储存方式,可以理解为把他们按行拆开,排成一大横排,地址连续。

在这里插入图片描述
什么叫地址连续?因为int类型变量占四个字节,所以大横排中相邻两个变量的地址都相差4。
如果

a

[

0

]

[

0

]

a[0][0]

a[0][0]在第40号地址,那么

a

[

0

]

[

1

]

a[0][1]

a[0][1]在第44号地址,

a

[

0

]

[

2

]

a[0][2]

a[0][2]在第48号地址…地址连续也是我们运用快排的基础。

那么如果我们把int a[5][5]改成char a[5][5]呢,一字排开的储存结构不会改变,只是因为char变量占据一个字节,所以如果

a

[

0

]

[

0

]

a[0][0]

a[0][0]在第40号地址,那么

a

[

0

]

[

1

]

a[0][1]

a[0][1]在第41号地址,

a

[

0

]

[

2

]

a[0][2]

a[0][2]在第42号地址…

在这里插入图片描述

指针+1

我们都知道,int类型占据四个字节,char类型占据一个字节,double占据8个字节。
那么假设现在有一个int类型指针p1,指向40号地址,那么p1+1指向几号地址呢?44号。
假设现在有一个char类型指针p2,指向40号地址,那么p2+1指向几号地址呢?41号。
假设现在有一个double类型指针p3,指向40号地址,那么p3+1指向几号地址呢?48号。

也就是说,我们对一个指针进行加减常数的操作,并不只是把指向的地址原封不动地加减对应的常数,而是根据指针指向的数据类型不同而变化。一次移动的步长是该数据类型占据的字节数。

可以假设一下,假如我们正在用指针来遍历数组元素,

int main()
{
	int a[10]={2,6,8,3,5,9,0,4,2,6};
	int *p=a;
	for(int i=0;i<10;i++)
	{
		printf("%d ",*p);
		p++;
	}
}

设现在a[0]在40号地址,a[1]在44号地址,a[2]在48号地址…

如果我们进行“p++”操作的时候,p只从40号地址移动到了41号地址,从41号地址移动到了42号地址…这该如何是好,这指向的根本就不是一个完整的int,而是指向了一个int的中间呀(a[0]的

1

/

4

1/4

1/4处,

2

/

4

2/4

2/4处),怎么可能正常输出呢。

所以指针是很智能的,可以根据指向的数据类型,自动决定,你对指针+1的时候,指针移动多少字节。

通过指针寻找数组元素

在第二小节里,我们知道了,无论是一维数组还是二维数组,他们在内存里都是一行排开的,且内存连续。
在第三小节里,我们知道了,可以通过指针遍历一维数组元素,并且不同类型的指针+1移动的步长不同。
对于一维数组int a[5],

a[4]//第56号地址里的元素

int *p=a;//p指向a的最开始的元素:a[0]的地址——40号地址
*(p+4)//p+4是40+4*4=56号地址,*(p+4)就是取出地址指向的元素

是一样的。

在这里插入图片描述
现在只看这个图片的后面一部分就好。
奇怪,我们只开了int a[5][5],行和列最大只开到了5,为什么还能用*(p+8)呢。
可以回想一下二维数组在内存里按一维储存这件事,并联系一下上面用指针遍历一维数组元素的内容。
在这里插入图片描述
p指向40号地址,先不要多想,p+8就是指向72号地址,看起来像是“越界”了,实际上,只是指向了72号地址上的a[1][3]罢了。

所以我们可以这样遍历二维数组a[5][5]:

for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			printf("%d ",a[i][j]);
		}
	}

也可以这样。

int *p=a;
	for(int i=0;i<25;i++)
	{
		printf("%d ",*(p+i));
	}

差不多到这里就可以开始深入理解qsort了!

理解函数原型

void qsort(void *base, int nelem, unsigned int width, int (* pfCompare)(const void *,const void *));

int 函数名(const void * elem1, const void * elem2);

这就是qsort函数的原型。


#include<stdio.h>
#include<stdlib.h>
int cmp(const void *p1,const void *p2)
{
	int *m=(int *)p1;
	int *n=(int *)p2;
	return *m-*n;
}
int main()
{
	int a[10]={2,6,8,3,5,9,0,4,2,6};
	qsort(a,10,4,cmp);
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

对照一下实际应用,方便理解。

qsort的第一个参数是void *类型,指向要参与排序的最开始的元素的指针。
qsort的第二个参数,代表“要有几个组参加排序”。
第三个参数代表,“每组占的字节数”。假如我们在第三个参数里填写了8,就代表,排序的时候,以八个字节位一个单位进行比较,这八个字节一定是挨在一起的,如果在排序中需要换位置,也只是这八个字节和那八个字节之间相对换位置,具体的某一组八个字节本身的内部排列是不会变的。
第四个就是我们自己根据需要写的cmp函数了。

现在试图理解一下第二个参数和第三个参数的应用。

在这里插入图片描述
第一次快排是我们最常用的普通快排。

假设a数组从40号地址开始,传进去的第一个参数就代表“从第40号地址开始比较”,第二个参数就代表“有10组参加比较”,第三个参数代表“每组占据4个字节”。
这个快排本质上就是第40到43号地址里的数据,第44到47号地址里的数据,第48到51号地址里的数据…参加比较排序。

第二次快排,我们稍微改了一下参数,为了让你了解一些这些参数的本质含义。

传进去的第一个参数就代表“从第40号地址开始比较”,第二个参数就代表“有5组参加比较”,第三个参数代表“每组占据8个字节”。
这样结果也变得可以理解了,原来在40到47号地址的2和6就是一组,在排序中永远保持相对顺序,原来在48到55号地址的8和3就是一组,在排序中永远保持相对顺序…

现在试图理解一下第一个参数的内涵。

在这里插入图片描述
a是40号地址,a+3是第52号地址,
这次的快排的前三个参数的意义分别是:
从第52号地址开始排序。(也就是40-51的前三个元素不参与排序,呆在原来的地方。)
有7组参加排序(前三个不用排序了,只有剩下7个需要排序)。
每组4字节。

综上所述,

qsort(a,b,c,cmp);

的本质意义就是:
从a代表的地址开始,每c个字节一组,一共有b组参加排序。

规则是人定的,怎么定的,用cmp函数定的。

cmp


#include<stdio.h>
#include<stdlib.h>
int cmp(const void *p1,const void *p2)
{
	int *m=(int *)p1;
	int *n=(int *)p2;
	return *m-*n;
}
int main()
{
	int a[10]={2,6,8,3,5,9,0,4,2,6};
	qsort(a,10,4,cmp);
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

再搬一遍代码。
关于cmp函数,你需要了解这么多:
1.cmp函数必须要写。
2.根据不同的你要的功能,写不同的cmp函数。
3.cmp函数的声明必须是

int 函数名(const void *参数名,const void *参数名)

不要说什么“我在我的电脑上试了,写const int *参数名不报错。”,那只是不报错而已,可能在别的编译器上就报错了,标准一些没有错。
4.
如果compar返回值小于0(< 0),那么p1所指向元素会被排在p2所指向元素的前面
如果compar返回值等于0(= 0),那么p1所指向元素与p2所指向元素的顺序不确定
如果compar返回值大于0(> 0),那么p1所指向元素会被排在p2所指向元素的后面

cmp和qsort之间如何传递信息

qsort(a,b,c,cmp);

这句话,向cmp函数传递了某些信息,而这些信息是这么传递的。
在这里插入图片描述

qsort从地址a开始,每隔c个字节设置一个小组,一共设置了b个小组。

qsort每次会在五组里按照一定规则选两组,把他们俩的头指针送给cmp函数,让这两个指针去cmp函数里一决高下,并根据cmp返回的值(正负零)决定这两个指针代表的小组要不要互换位置。
qsort会选取很多不同的一对小组,进行多次cmp,直到排序完成。

也就是说,外面的世界对cmp来说是黑箱,我们传进去的数组叫什么,是一维数组还是二维数组,这个数组从哪个地址开始,这个数组有多少元素,这个数组是什么数据类型,是int a[5][5]还是char b[4][6]…这些东西,cmp都不知道。

qsort每次给cmp的就是两个指针,这两个指针是cmp唯一知道的东西,我们要DIY的就是,在cmp函数里做造物主,制造根据两个指针返回不同的值的规则。

所以这也是cmp函数是

int 函数名(const void *参数名,const void *参数名)

而不是什么

int 函数名(const int *参数名,const int *参数名)

的原因。
cmp不知道我们要比较的数据类型,也不需要知道,她只要知道这两个指针指向几号地址就可以,所以我们用const void *。

但是我们是写代码的人,我们知道要比较的是什么类型的数据,所以我们在cmp函数里做一下类型转换,重开两个int类型的指针,并把两个const void指针的值赋给他们,方便身为造物主的我们发挥。

在这里插入图片描述
现在回到这个例子。
假设数组是从40号地址开始的(我假设这么多40号,可不要以为所有数组都从40号地址开始呀,我随便说的。),qsort函数便从40号地址开始,每隔8个字节设置一个小组,一共设置了五个。
在这里插入图片描述
假设这一次,qsort选的是第三组和第五组,把这两个小组的头指针传给cmp函数,一个指向56号地址,一个指向72号地址。
我们的cmp的规则是

int cmp(const void *p1,const void *p2)
{
	int *m=(int *)p1;//m是56号地址,对应数据5
	int *n=(int *)p2;//n是72号地址,对应数据2
	return *m-*n;//5-2>0,按规则,56-63号地址上的数据和72-79号地址上的数据得整体交换一下
}

这只是一次cmp,还有很多次cmp…总之,每次给cmp两个指针,让cmp根据我们写的规则返回正数负数或者0,决定这两个指针指向的小组要不要交换…这就是qsort的原理。

尝试分析双关键字快排

第一维相同时按第一维升序排序,第一位相同时按第二维升序排序。

在这里插入图片描述
根据刚刚讲述的“一字排开说”,“地址连续说”,可以得到下面一张图。

在这里插入图片描述
因为

qsort(a,5,8,cmp);

所以我们从地址a开始,每隔8字节放一个小组,一共5个。每次选两个的头指针送给cmp,让cmp在只知道这两个指针指向哪里的情况下,给我们返回一个值,决定这两个指针代表的小组要不要换位置。

假设这次送给cmp的是40号地址和48号地址。

int cmp(const void *p1,const void *p2)
{
	int *m=(int *)p1;
	int *n=(int *)p2;
	if(*m!=*n)//1
	{
		return *m-*n;
	}else//2
	{
		return *(m+1)-*(n+1);
	}
}

cmp进行到1处,m指针是40号地址指向4,n指针是48号地址指向4,因为4==4,所以进不去第一个if,去到2处。

m+1指针是44号地址指向8,n+1指针是52号地址指向2,因为8>2,所以按规则这两个小组整体要交换位置。

k关键字排序

请添加图片描述

在这里插入图片描述
是不是也能稍微理解一些了。

这位同学的cmp是,只返回1,-1或0,但是实际上排序只看cmp返回的数是正是负还是0,所以我更习惯直接用两个数相减。

但是我写的是不标准的,有的时候可能会出错,产生溢出错误。
如果*m=2000000000,*n=-2000000000.他们相减的结果会溢出成负数,而不是我们想象中的400000000。

所以还是建议向这位同学学习,返回1或-1或0。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>