深入理解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。