qsort函数与mysort函数详解

菜鸡的我来发教程啦。

1.如何使用qsort

#include<stdio.h>
#include<stdlib.h>
int compare(const void* a, const void* b) { return *(int*)a - *(int*)b; }
int main() {
	int nums1[] = {1, 489, 4591, 189, 123, 189, 56, 6};
	qsort(nums1, sizeof(nums1) / sizeof(int), sizeof(int), compare);
	for (int i = 0; i < sizeof(nums1) / sizeof(int); i++)
	{
		printf("%d ", nums1[i]);
	}
}

先看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函数

1
2
3

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

传入了两个常量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函数原型

1	void mysort(void* base, size_t num, size_t size, int(comparator)(const void, const void*)) ;

可以发现，为了让mysort函数可以排序任意的类型的数组，就必须让base这个参数为void，因为任意的指针都可以赋值给void指针。

但是现在问题来了，我们手里只有三个值，没有保存变量类型的基地址base，待排序的元素数量num，待排序的元素的类型所占的字节大小size。

主要要实现以下三点：1.把每个待排序的元素区分开来。2.实现待排序元素之间的交换。3.实现待排序元素之间的比较。

这三点按理来说都是需要知道待排序元素的类型的，但是mysort是获取不到的。（其中第三点因为比较是使用compare函数实现的，而用户自定义的compare函数，用户肯定是知道元素类型的，这个可以不用烧脑了）

先看一段普通的带参选择排序

for (i = 0; i < num; i++) {
		key = i;
		for (j = i + 1; j < num; j++) {
			if (nums[key]>nums[j]) {
				key = j;
			}
			if (key != i) {
                int temp = nums[key];
                nums[key] = nums[i];
                nums[i] = temp; 
			}
		}
	}

对比刚才要实现的三点，我们可以发现重点在第4行和第8-10行。

先上一段代码

for (i = 0; i < num; i++) {
		key = i;
		for (j = i + 1; j < num; j++) {
			if (comparator((char*)base + size * key, (char*)base + size * j) > 0) {
				key = j;
			}
			// 进行交换
			if (key != i) {
				exchangeVoid((char*)base + size * key, (char*)base + size * i, size);
			}
		}
	}

其中exchangeVoid()函数定义如下。（此处征得sya同学的同意，偷懒的我直接用他写好的代码了）

void exchangeVoid(void * from, void *  to, size_t size) {
	char * fromPtr = (char *)from;
	char * toPtr = (char *)to;
	char temp;
	for (int i = 0; i < (int)size; i++) {
		temp = *(fromPtr + i);
		*(fromPtr + i) = *(toPtr + i);
		*(toPtr + i) = temp;
	}
}

先来解决第四行的问题，也就是使用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函数：

void mysort(void* base, size_t num, size_t size, int(*comparator)(const void*, const void*)) {
	int i, j, key;
	void* temp = malloc(size);
	for (i = 0; i < num; i++) {
		key = i;
		for (j = i + 1; j < num; j++) {
			if (comparator((char*)base + size * key, (char*)base + size * j) > 0) {
				key = j;
			}
			// 进行交换
			if (key != i) {
				//exchangeVoid((char*)base + size * key, (char*)base + size * i, size);
				memcpy(temp, (char*)base + size * key, size);
				memcpy((char*)base + size * key, (char*)base + size * i, size);
				memcpy((char*)base + size * i, temp, size);
			}
		}
	}
};

我觉得已经不需要讲那么多啦，上面的能理解，这个soeasy。

然后部长我去翻了一翻qsort() memset() memcpy()的源码，惊讶的发现原来也是用char*来操作的，，，

不过这样写简洁一点嘛，而且库函数一定写的比自己好.jpg。