C语言--- qsort函数

一.qsort函数

1.qsort函数的功能

2.四个参数讲解

(1)base

(2)num

(3)size

(4)compare

3.使用qsort函数对一个整形数组进行排序

4.qsort函数排序结构体数据

第一种：按照年龄进行比较

第二种：按照名字进行排序

二.利用冒泡排序模仿qsort函数

回顾：冒泡排序

代码实现：

一.qsort函数

void qsort(void* base, size_t num, size_t size,int (*compar)(const void*, const void*));

1.qsort函数的功能

qsort函数是用来进行快速排序的。

那么它的四个参数分别是什么呢？

2.四个参数讲解

参考网址：qsort - C++ Reference

(1)base

base是一个指针，它所指向的是被排序数组的第一个元素。

void*通常被我们叫做空指针，也叫泛型指针，因为不知道数组中元素的类型是什么，所以只能先将首元素的地址转化为一个空指针。

(2)num

num指的是数组元素的个数。

size_t是 unsigned int 类型.

(3)size

size是数组中元素的大小，单位是字节。

(4)compare

compare是什么呢？compare的意思是比较，对数组中的元素进行排序，必然离不开比较。

compare就是一个函数指针，它所指向的这个函数的返回类型是int,有两个参数，类型都是const void*.这个函数会被反复调用来进行两个元素的比较。

假设这两个参数变量名分别是p1和p2。

这个函数的返回值，取决于所指向的对象的大小的。这个函数是需要我们自行完成的。

如果p1所指向的元素小于p2所指向的元素，那么返回值小于0

如果p1所指向的元素大于p2所指向的元素，那么返回值大于0

如果p1所指向的元素等于p2所指向的元素，那么返回值等于0

3.使用qsort函数对一个整形数组进行排序

qsort函数的头文件是<stdlib.h>

代码：

#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* p1,const void*p2) {
	
}
void print(int *p,int sz)
{
	for (int i = 0; i < sz;i++) {
		printf("%d ",p[i]);
	}
}
int main()
{
	int arr[] = {1,3,5,7,9,2,4,6,8,0};
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr,sz,sizeof(int),cmp_int);//排序
	print(arr,sz);//打印
	
	return 0;
}

那么这个cmp_int函数怎么实现呢。

我们知道解引用操作符是不能解引用void*类型的指针的。所以我们需要先将p1和p2进行强制类型转换，再来比较大小。

int cmp_int(const void* p1,const void*p2) {
	if (*(int*)p1 < *(int*)p2){
		return -1;
	}
	else if (*(int*)p1 > *(int*)p2){
		return 1;
	}
	else {
		return 0;
	}
}

但是这样写其实有点复杂，因为qsort函数不管返回值是多少，而是返回值到底是正还是负，所以我们可以对cmp_int函数进行简化。

int cmp_int(const void* p1,const void*p2) {
	return *(int*)p2 - *(int*)p1;
}

输出结果：

这样我们就完成了这个整形数组的排序，继续仔细观察的话，我们发现这个是升序排列，如果我们改变一下返回值的比较方式，我们就可以实现降序排列。

return *(int*)p2 - *(int*)p1;

输出结果：

4.qsort函数排序结构体数据

排序结构体时，我们只能针对结构体中的一种数据进行排序。

假设有一个用于描述学生的结构体，有两个结构体成员，分别是名字和年龄

第一种：按照年龄进行比较

#include<stdio.h>
#include<stdlib.h>
struct stu
{
	char name[20];//名字
	int age;//年龄
};
int cmp_age(const void*p1,const void*p2) {
	return  ((struct stu*)p1)->age - ((struct stu*)p2)->age;
//因为p1和p2的类型是const void*,所以我们还是要强制类型转化为结构体指针。
}
int main()
{
	struct stu arr[3] = { {"zhangsan",38} ,{"lisi",28} ,{"wangwu",18} };//结构体数组
	int sz = sizeof(arr) / sizeof(arr[0]);
	//如何进行排序？
	//第一种：利用年龄进行排序
	qsort(arr,sz,sizeof(struct stu),cmp_age);
	return 0;
}

通过调试，我们在监视窗口中可以看到数组的第一个元素（结构体）变成了王五，18岁。不再是张三，38岁。

第二种：按照名字进行排序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct stu
{
	char name[20];//名字
	int age;//年龄
};
int cmp_age(const void*p1,const void*p2) {
	return  ((struct stu*)p1)->age - ((struct stu*)p2)->age;
}
int cmp_name(const void*p1,const void*p2) {
	return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name);
}
int main()
{
	struct stu arr[3] = { {"zhangsan",38} ,{"lisi",28} ,{"wangwu",18} };//结构体数组
	int sz = sizeof(arr) / sizeof(arr[0]);
	//如何进行排序？
	//第一种：利用年龄进行排序
	//qsort(arr,sz,sizeof(struct stu),cmp_age);
	//第二种：利用名字进行排序
	qsort(arr,sz,sizeof(struct stu),cmp_name);
	return 0;
}

这里我们还需要用到strcmp函数的，strcmp函数的两个参数是字符串，这个函数用于比较字符串，但是不是利用字符串的长度进行比较而是ASCII值进行比较。

如果前一个字符串大于后一个字符串，返回值大于0，反之小于0，如果相等就返回0，这和qsort函数中的compare所指向的函数返回值规则一致。

例如："abc"和"abcd"这两个字符串肯定就是第二个更大。

但是"abcd"和"abe"就是第二个大了，因为这个函数不会利用整个字符串的ASCII值之和来比较，而是一个字符一个字符进行比较，"abcd"和"abe"的前两个字符都一样，所以会看第三个字符，c的ASCII值明显小于e,所以后者更大，就不会管第四个字符了。

通过调试的监视窗口，结果是：

之所以这样排序，是因为ASCII值 l < w < z.

二.利用冒泡排序模仿qsort函数

qsort函数实际上使用的是快速排序。

回顾：冒泡排序

冒泡排序的核心思想：两个相邻元素进行比较；

如果存在十个数无序排列，比如： 2，3，1， 4，10，7， 5，6， 8，9；

如果我们要将重新排列，变成左边小右边大的情况，我们就可以用到冒泡排序。如何进行冒泡排序呢？

首先我们先比较第一个数和第二个数，如果第一个数大于第二个数就交换位置，反之就不交换，然后我们再比较第二数和第三个数，同理如果第二个数更大就交换，就这样一直进行下去，直到完成第九个数和第十个数。就这样我们完成了一轮交换。

读者可以自行用上面的数进行尝试，我们会发现最大的那个数经过了一轮交换后（因为最大的数一定比它右边的数大，所以它会一直交换下去，直到最后一个位置），就到了最后一个位置，但其他的数还是乱的，所以我们要接着进行下一轮交换，但是因为最大的数已经在它该在的位置上了，这样在下一轮的交换中我们就不需要比较第九个数和第十个数了；同理后面也是如此…………。

第一轮中我们比较了9次，第二轮比较8次，第三轮比较7次，总共需要比较多少轮呢？

答案是9轮。第九轮的时候比较一次，也就是第一个位置上的数和第二个位置上的数进行比较，第二个位置上的数确定了后，同理第一个位置上的数也应该是最小的了，所以就不用比较了。

原文链接：http://t.csdnimg.cn/VWTYVhttp://t.csdnimg.cn/VWTYV

代码实现：

qsort函数的优点就是可以对任意类型的数据进行排序。模仿qsort函数我们仍然使用相同的变量

这里我们采用升序。

void bubble_qsort(void* base,size_t num,size_t size,int(*compare)(const void*,const void*)) {
//这里的sz指的是数组的元素个数
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

这里面是冒泡排序的代码，我们如何改变才能变得和qsort函数一样对任意函数进行排序。

首先if的判断条件需要更改，因为我们在compare所指向的函数中进行了比较了，当compare的返回值大于0时就需要交换元素。

那么if括号中应该怎么写呢？，首先我们要明白在比较的两个元素分别是数组的第（j）个元素和数组的第（j+1）个元素，也就是说我们需要找到这两个元素的地址。

base是数组首元素的地址，我们知道指针+-整数会根据指针的类型，跳过不同的字节，这样我们就可以找到其他元素的地址，但是base的类型是void*，这样我们就不能进行+-整数，所以我们需要先进行强制类型转化，那么转化为什么类型的指针呢？

答案是char*,为什么呢？

这里就跟我们没有使用的元素大小size有关了，char*类型的指针，在+-1的时候只会跳过一个字节，更方便我们使用，如果是int*而数组元素的大小是7个字节，无论如何我们也不能得到其他元素的地址了，因为跳过的字节数是4的倍数，永远不可能是7.

那么如何得到第j个元素的地址？

(char*)base+j*size,这就是第j个元素的地址。

所以if括号中应该这样写

if (compare((char*)base + j * size, (char*)base + (j + 1) * size) > 0)

然后就是如何进行元素的交换了。

为了代码的可读性，我们再写一个swap函数进行元素的交换。

//p1 = (char*)base + j * size, p2 = (char*)base + (j + 1) * size
void _swap(void *p1, void * p2, int size)

因为我们不知道元素的类型，我们是无法进行解引用的，那么如何解决这个问题呢？

同理我们可以先将其强制类型转化为char*的，但是char*的指针在解引用时，只会得到一个字节的数据，万一我们的元素大小是大于1的呢？

我们就可以一个字节一个字节的交换，这样又用到了数组的元素大小。

void swap(void* p1, void* p2, int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		char tmp = *((char*)p1 + i);
		*((char*)p1 + i) = *((char*)p2 + i);
		*((char*)p2 + i) = tmp;
	}
}

所有代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int cmp_int(const void* p1,const void*p2) {
	return *(int*)p1 - *(int*)p2;
}
void print(int *p,int sz)
{
	for (int i = 0; i < sz;i++) {
		printf("%d ",p[i]);
	}
}
struct stu
{
	char name[20];//名字
	int age;//年龄
};
int cmp_age(const void*p1,const void*p2) {
	return  ((struct stu*)p1)->age - ((struct stu*)p2)->age;
}
int cmp_name(const void*p1,const void*p2) {
	return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name);
}
void swap(void* p1, void* p2, int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		char tmp = *((char*)p1 + i);
		*((char*)p1 + i) = *((char*)p2 + i);
		*((char*)p2 + i) = tmp;
	}
}
void bubble_qsort(void* base,size_t num,size_t size,int(*compare)(const void*,const void*)) {
	int i = 0;
	for (i = 0; i < num - 1; i++)
	{
		int j = 0;
		for (j = 0; j < num - i - 1; j++)
		{
			if (compare((char*)base + j * size, (char*)base + (j + 1) * size) > 0) 
			{
				swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
			}
		}
	}
}


int main()
{
	struct stu arr1[3] = { {"zhangsan",38} ,{"lisi",28} ,{"wangwu",18} };
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	//qsort(arr,sz,sizeof(struct stu),cmp_age);
	bubble_qsort(arr1,sz1,sizeof(struct stu),cmp_name);

	int arr2[] = { 1,3,5,7,9,2,4,6,8,0 };
	int sz2 = sizeof(arr2) / sizeof(arr2[0]);
	bubble_qsort(arr2, sz2, sizeof(int), cmp_int);//排序
	print(arr2, sz2);//打印
	return 0;
}

输出结果：