【qsort函数实现】

函数介绍

第一步
我们可以先查询知道函数的使用方法

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

使用qsort()函数的好处就是可以排序任意类型的数据不像冒泡排序只能排序整形数组
此函数使用的排序算法通过调用指定的函数来比较元素对并将指向它们的指针作为参数
可以看到这个函数有四个参数
第一个参数指向要排序的数组的第一个对象的指针转换为 .void*
第二个参数是数组中元素的个数
第三个是数组中每个元素的大小以字节为单位是无符号整型。size_t
第四个指向比较两个元素的函数的指针。

具体可以参见
https://legacy.cplusplus.com/reference/cstdlib/qsort/?kw=qsort

函数实现

第二步
使用qsort函数对int类型进行排序

int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

//测试qsort函数排序整型数据
void test()
{
	int arr[] = { 2,1,3,7,5,9,6,8,0,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	print(arr, sz);
}

可以看到我们要比较两个整形元素的大小关系所以我们设计函数cmp_int()函数指向比较两个元素的函数的指针。
重复调用此函数以比较两个元素。它应遵循以下原型qsort

int compar (const void* p1, const void* p2);

将两个指针作为参数都转换为常量 void*。该函数通过返回以稳定和传递的方式来定义元素的顺序

使用qsort函数对结构体类型进行排序

struct Stu
{
	char name[20];
	int age;
};

int cmp_stu_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
	//字符串大小的比较是以ASCII 码表上的顺序来决定此顺序亦为字符的值
}

int cmp_stu_by_age(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

//测试qsort排序结构体数据
void test()
{
	struct Stu s[] = { {"张三", 30}, {"李四", 40}, {"王五", 50} };
	int sz = sizeof(s) / sizeof(s[0]);
	//按照名字比较
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	//'按照年龄比较
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}

在这里我们按照结构体中的名字和年龄来排序我们设计函数 cmp_stu_by_name和cmp_stu_by_age来进行实现,首先通过强制类型转化e1,e2为结构体指针这里要将(S*)e1先用括号括起来因为箭头的优先级更高。

到此qsort函数如何实现的我们清楚了那么我们可以怎么使用呢接下来我们通过改造冒泡排序把冒泡排序改为可以比较任何类型排序即用冒泡排序的思想模拟qsort。

首先我们先来实现冒牌函数

//bubble_sort 函数只能排序整型数据
void bubble_sort(int arr[], int sz)
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		//一趟冒泡排序的过程
		int j = 0;
		for (j = 0; j < sz-1-i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1]; 
				arr[j + 1] = tmp;
			}
		}
	}
}
void print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void test1()
{
	//冒泡排序
	//对整型数据进行排序 - 排序为升序
	int arr[] = { 2,1,3,7,5,9,6,8,0,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	print(arr, sz);
}

我们想要改造首先就是对我们参数的进行改变变得一致函数体中的比较部分我们也提出相邻的个自比较改造如下
函数参数部分

void bubble_sort2(void* base, int sz, int width, int (*cmp)(const void* e1, const void*e2))

比较部分

if (cmp((char*)base+j*width, (char*)base+(j+1)*width)>0)
//交换
Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);

cmp的参数是这两个元素的地址之后在自己所创作的函数中再去强制类型转化为所需类型第一个元素地址就是base,如何找到之后的呢首先将其转化为char的指针其加即就是原地址越过一个字节的地址这里就需要到了第三个参数int width代表所占的字节空间数可以用sizeof直接计算第一个元素的地+1width就跳到了第二个元素了后面同理可得(char)base + width * j widthj跳过第j个元素的地址这就代表了第j+1个元素的地址(char)base + width * (j + 1)代表j+2个元素的地址 这样就可以访问到所有元素了比较完后if如果大于0.交换两个元素所以我们还需要设计一个交换的函数即如下

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++;
	}
}

我们将两个元素的地址交给Swap(),char类型来接收但是char只能访问一个字节接下来我们就需要引入Swap的第三个参数了width交换width个字节及实现了相应的功能。

最后代码如下

void bubble_sort2(void* base, int sz, int width, int (*cmp)(const void* e1, const void*e2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		//一趟冒泡排序的过程
		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);
			}
		}
	}
}

到此qsort函数的介绍便结束了希望大家多多支持