qsort函数与mysort函数详解
菜鸡的我来发教程啦。
1.如何使用qsort
|
|
先看compare函数,传入了两个void指针,但是交换的时候使用了(int )a的强制类型转换。至于为什么,先放一放。
然后是qsort使用,这个上次的邮件里已经写了,我就不赘述了。
注意sizeof(nums1) / sizeof(int)可以获取所需的数组的长度。
2.关于void*指针
先看一下基本的内容,可能有错,但是对理解没什么影响。
1.指针有四个相关的参数:a.自己的名字。b.自己本身的地址。c.储存的、也就是指向的地址。d.指向的变量的类型。
2.现在如果int a有4个字节,也就是32位,那么int p = &a,那么首先p指向的地址是a的*第一个字节的地址。
3.继续,当p++时,p会跳过几个字节呢?答案是四个,也就是说现在p指向a的最后一个字节的后一个字节。
也就是说,指针需要知道自己指向的变量的地址,还要知道指向的变量的长度,这个长度一方面是为了做++的操作,另一方面是为了解引用(如*p=1)时,能够获取到完整的变量。
好了,现在回到void,先明确一点:void指针是没有“指向变量的类型”这个参数的。
所以:1.void不允许自增,2.void不允许解引用
3.回到compare函数
|
|
传入了两个常量void指针a,b,这个函数要做的就是比较待排序元素。
因为这里我要排序的是int数组,所以使用(int)a,把a变成一个int类型的指针,这样子a就拥有了指向的变量的长度这个参数,然后(int)a,对(int)a解引用,获取那个int类型的值。b同理。然后比较a和b的大小。注意,在compare函数中,要求compare返回的值的格式为:a要排在b后面,则a>b时返回正值,反之同理。
4.如何实现自己的mysort函数
先看mysort函数原型
可以发现,为了让mysort函数可以排序任意的类型的数组,就必须让base这个参数为void,因为任意的指针都可以赋值给void指针。
但是现在问题来了,我们手里只有三个值,没有保存变量类型的基地址base,待排序的元素数量num,待排序的元素的类型所占的字节大小size。
主要要实现以下三点:1.把每个待排序的元素区分开来。2.实现待排序元素之间的交换。3.实现待排序元素之间的比较。
这三点按理来说都是需要知道待排序元素的类型的,但是mysort是获取不到的。(其中第三点因为比较是使用compare函数实现的,而用户自定义的compare函数,用户肯定是知道元素类型的,这个可以不用烧脑了)
先看一段普通的带参选择排序
对比刚才要实现的三点,我们可以发现重点在第4行和第8-10行。
先上一段代码
其中exchangeVoid()函数定义如下。(此处征得sya同学的同意,偷懒的我直接用他写好的代码了)
先来解决第四行的问题,也就是使用comparator()来比较。
comparator()函数需要拿到已经分开的两个待排序的元素(这里只用把待排序的元素的void*地址传过去即可,因为在comparator()函数里已经实现了强制类型转换)
这一步呢,应该是比较nums[key]和nums[j]的大小,所以使用了(char)base + size key来拿到nums[key],nums[j]同理。
现在先暂停一下,看看为什么要突然使用一个char*。
回忆一下char的大小,是一个字节,而c语言中没有半个字节的变量,所以可以把char的大小当成单位长度。
所以我们先把base指针变成单位长度的指针,然后加上size*key,跳过key个size,拿到nums[key]。(推荐在草稿纸上画一个图来理解)。这里假如待排序的是整数,那么size就是4个单位长度。
实际上如果编译器6一点,可以直接这样写:base + size * key,但是推荐还是加上char*强制类型转换,比较稳妥。
好了第一个问题解决了,我们继续解决下一个问题:交换。
我们还是使用char*这个骚操作来完成。
现在先好好读一下sya大佬的exchangeVoid()函数,同样使用了类似上一步的方法,拿到了nums[key]和nums[i]。
但是这个函数与comparator()函数不同的是,这个函数不是由用户自定义的,也就是说需要适应所有的可能的数据类型,并对他们交换。
怎么做呢?其实第一部里面的(char *)理解了,这一步也就显而易见了。
假设现在有待排序元素是有46个字节大小(这个字节大小通过size参数获得)的结构体。同样,把这个结构体拆分成46个单位长度(也就是46个char)。
然后我们就有了第一组拆分成46个char的结构体,和第二组46个char的结构体,然后要实现他们的交换。显而易见,一次把第一个char和第一个char交换、把第二个char和第二个char交换······
这样我们就实现了比较和交换,就可以用来排序啦!
5.memcpy函数
先看百度百科:
void memcpy(void dest, const void *src, size_t n);
从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中
再来新的mysort函数:
我觉得已经不需要讲那么多啦,上面的能理解,这个soeasy。
然后部长我去翻了一翻qsort() memset() memcpy()的源码,惊讶的发现原来也是用char*来操作的,,,
不过这样写简洁一点嘛,而且库函数一定写的比自己好.jpg。