【c语言】--qsort快速排序【附模拟实现】

目录

一、qsort与一般排序的区别

二、qsort函数原型

三、qsort函数应用：

①、排整形数据【升序】

②、排结构体数据【升序】

四、qsort函数的模拟实现

一、qsort与一般排序的区别

• 它是库函数
• 它可以排任何类型的数据，如整形数据，字符串数据，结构体数据，而我们一般写的冒泡排序， 选择排序只能排一种数据，有一定的局限性
• qsort与冒泡排序相似，只是比较不同数据的方法不同，如字符串比较要用strcmp，不能直接用大于或等于比较，因为比较大小方法不同，需自己写个比较大小函数，再传给qsort才行

二、qsort函数原型

用qsort需引用头文件stdlib.h或search.h

qsort函数原型：

void qsort( void* base, size_t num, size_t size, int (*compar)（const void *e1,const void *e2）)

qsort函数参数：

• void* base:base中存放待排序数据中第一个对象的地址，设为void*是因为它是一个无地址的指针，可以接收任何类型的指针，所以base可以放任何类型的地址【void*不能进行解引用操作且不能对其进行加减整数】
• size-t num:待排序数据的元素个数
• size-t size:待排序数据中一个元素的大小，单位:字节
• int (*compar)(const void *e1,const void *e2):是一个函数指针，通过传入比较大小的函数（需要自己写）用来比较待排序数据中所传入两个元素的大小，（若排为升序，compar函数返回值>0就交换【第一个数>第二个数】，若排为降序compar函数<0就交换【第一个数<第二个数】，只要==0，不用交换）
• 本质上qsort函数就像冒泡排序两个元素一点一点往下比的
• 如果排为升序是e1-e2，即第一个元素-第二个元素，排为降序则是e2-e1，即函数第二个元素-第一个元素，因为对于qsort返回>0的数，就会排为升序，排为降序e1-e2和e2-e1正好为相反数那么就会产生升序和降序的效果

三、qsort函数应用：

①、排整形数据【升序】

#include
#include
int cmp_int(const void* e1, const void* e2)
{//返回类型:int 返回这个数>0或<0或=0根据此判断是否排序
 //写成void*可以接收任何类型的数据，因为不知道比较的是什么数据
 //加上const更具有严谨性，防止e1,e2内容被修改
 //因为本题比较的是整形数据，所以比较大小方法如下
	return *(int*)e1 - *(int*)e2;
 //先转化为int*因为e1和e2均为void*，void*不能解引用，因为void*不确定
 //访问几个字节的，*找不到要比较的数据，又因为要排序的数据是整形，所
 //以强制类型转换为int*，再解引用能够访问四个字节找到e1和e2的内容
 //第一个元素>第一个元素返回>0,反之返回<0,=0不用排序
}
int main()
{
	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	//第四个参数解释:函数名即函数地址，而qsort函数第四个参数用函数指针接收的
	//cmp_int函数是排什么数据的大小，需要自己写的函数，因为排不同数据方法不同
	//所以必须自己写排大小函数，再传给qsort函数地址就可以，原理：回调函数，qsort内部实现
	for (int i = 0; i < sz; i++)
	{
		printf("%d", arr[i]);
	}
	return 0;
}
//运行结果:0 1 2 3 4 5 6 7 8 9

②、排结构体数据【升序】

#include
#include
#include
 
struct stu
{
	char name[20];
	int age;
};
int sort_by_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int sort_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name,((struct stu*)e2)->name);
}
 
int main()
{
	struct stu s[3] = { {"zhang san",30},{"li si",34},{"wang wu",20} };
	int sz = sizeof(s) / sizeof(s[0]);
	//按年龄排序
	qsort(s, sz, sizeof(s[0]), sort_by_age);
	printf("排序后的年龄:");
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", s[i].age);
	}
	printf("\n");
 
	//按姓名排序
	printf("排序后名字:");
	qsort(s, sz, sizeof(s[0]), sort_by_name);
	for (int i = 0; i < sz; i++)
	{
		printf("%s ",s[i].name);
		//排序名字比的不是长短，比的是ASCii码的值
	}
	printf("\n");
	return 0;
}

四、qsort函数的模拟实现

模拟实现qsort，实现一个冒泡排序的通用算法，将arr数组排为升序
int arr[] = {1,3,5,7,9,2,4,6,8,0}；

注意：我模拟的是qsort函数实现排整型数据升序版本，降序版本还需进一步完善，但是与升序版本基本一样

①、如何找到两个元素相比？

思路与冒泡排序一样，但两个元素相比时，我并不知道怎么找到这两个元素，因为void*是无类型指针，但通过用传入的一个数据的大小，可利用指针访问两个元素，又因为void*不能直接加减运算，故转base为char*，char*指针+1等价于往后走一个字节，那排int类型数据,width = 4,(char*)base + 4就可访问下一元素地址，(char*)base + 8就可再访问下一个元素的地址，故(char*)base + j * width与(char*)base + (j + 1)* width就可作为比较的前后两个元素的地址，j是冒泡排序内层循环的变量，从0开始
 

②、如何交换两个元素？

可以一个一个字节交换，交换width次即可（因为width是一个数据的大小）

#include
int cmp(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)//要排sz-1趟，与冒泡排序原理同
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{//两个元素两个元素比较，每次比较完都会少比较一次
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}
int main()
{
	int arr[] = { 1,3,5,7,9,2,4,6,8,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}