无类型排序【详解】

本期介绍🍖

主要介绍：什么是无类型排序，库函数qsort()的使用方法，如何自己模拟实现一个无类型的冒泡排序。👀。

---

---

一、什么是无类型排序🍖

  我想大家一定编写和实现过冒泡排序，但却只适用于某一种类型的数据，不能够对多种类型的数据进行排序。如若想排序多种类型的数据，就只能为每一种类型的数据单独设计一个冒泡排序，然后单独调用来实现。可这样做是不是太过于麻烦啦，我不禁想是否存在一个排序，能够适用于所有类型的数据？答案是：存在的，我们称这种排序为无类型排序。而且在C语言的库中就存在着这样一个函数qsort()（使用快速排序的思想实现的一个排序函数，适用于所有类型的数据）。

---

二、库函数qsort🍖

  qsort()函数无返回值，且四个参数分别为：

1. base：需要排序数据的起始位置
2. num：待排序数据元素的个数
3. width：待排序数据元素的大小（单位：字节）
4. compare：比较函数

  其中compare是一个函数指针，该函数需要我们自己来实现。函数的返回类型为int，参数为两个const void*的指针，指向两个需要被比较的元素。(若elem1 > elem2则返回值大于0，若elem1 = elem2则返回值等于0，若elem1 < elem2则返回值小于0)，举个例子：

#include
#include
#include

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

test1()
{
	int arr[] = { 1,3,5,7,3,4,9,0,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), sort_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	printf("\n");
}

int sort_str(const void* e1, const void* e2)
{
	return strcmp((char*)e1, (char*)e2);
}

test2()
{
	char name[][10] = {"zhangsan", "lisi", "wangwu", "tangqi"};
	int sz = sizeof(name) / sizeof(name[0]);
	qsort(name, sz, sizeof(name[0]), sort_str);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s\n", name[i]);
	}
	printf("\n");
}

struct Stu
{
	char neme[20];
	float score;
};

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

test3()
{
	struct Stu people[] = { {"zhangsan", 49.5},{"lisi", 96}, {"wangwu", 77.8}};
	int sz = sizeof(people) / sizeof(people[0]);
	qsort(people, sz, sizeof(people[0]), sort_struct);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %f\n", people[i].neme, people[i].score);
	}
	printf("\n");
}

int main()
{
	//排序整型数据
	test1();
	//排序字符串
	test2();
	//排序结构体(以结构体中浮点型大小的顺序)
	test3();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

  以上就是快速排序函数qsort的使用方法了，那下面就需要来实现一个类似于该函数的代码了。

---

三、实现冒泡排序（适用于所有类型）🍖

  我们可以通过模拟qsort函数来实现，来实现无类型的冒泡排序。首先我们需要了解它的参数有哪些，以及这些参数的类型，然后再来思考几个问题：

1. 该用什么类型的指针，来接收不同类型的数据的起始地址？
2. 为什么qsort函数需要知道待排序数据元素的大小？
3. 为什么qsort函数需要，调用函数的一方来另外实现一个比较函数，它不能在内部一起实现吗？

---

3.1 void*类型的指针🍖

  首先，想要能够对任意类型的数组进行排序，首先就先需要有能够接收任意类型数组起始位置地址的能力。我们观察发现qsort是用void*类型的指针来接收的，下面让我来介绍一下该类型的指针。void*是无类型的指针，又称：泛型指针。其能够用来接收所有类型的指针，但不能对该类型的指针进行解引用或加减整数的操作。因为指针的类型不明确，自然确定不了解引用时访问的权限和加减整数时的步长。如若强行对操作，编译器会报错。所以qsort函数的参数base可以设置为void*类型，这样就可以接收任意类型数组的起始地址了。

---

3.2 参数width的用处🍖

  大家注意，如若qsort仅仅只接收了数组的起始地址和元素个数，那该函数是无法访问到数组中的每一个元素的，因为void* base只确定了数组的起始地址，并不知道每一个数组元素的大小，故无法精准get到每一个数组元素。那我们该怎么做呢？ 传递一个数组元素大小的参数进去不就行了（用参数width来接收），然后通过先将base（数组的起始地址）强制类型转换char*类型后（这样就可以进行加减整数操作了），再对base进行加减一个元素大小整数的操作（这样不就等价于在知道指针类型情况下的加减整数的操作），如此就可以找到数组中每一个元素了。

---

3.3 回调函数的用法🍖

  我们需要自己先实现一个比较函数，然后再将这个函数的函数名（也就是函数的起始地址）作为参数传递给qsort函数。那为什么需要这么做呢？因为qsort的实现方是无法得知将来我们将来在用这个函数时会传递什么样类型的数据进来，故他就没有办法确定到底用什么样的比较方式（又因为不同类型的数据比较的方法是不同的，就譬如：整型数据和字符串的比较方式就不同，整型只需要用关系运算符>、<、==、>=、<=就能够得出大小，但字符串却不行，它需要用到strcmp函数才能够比较大小)，所以干脆就让调用qsort函数的人自己实现一个比较函数，然后再传进来，他直接调用不就完了嘛。这样不就做到了在不知道类型的情况下任能对数据进行比较，这也是回调函数的一种经典使用方法大家可要注意了。

---

3.4 如何用void*指针交换两个元素？🍖

  首先，想要交换两个元素的内容，就得先能够找到每一个元素的地址，然后再根据对地址的解引用操作，才能访问地址所对应的元素。根据之前所学，我们知道在确定数组的起始地址、数组元素的个数、数组元素的大小的情况下，可以确定每一个数组元素的地址。但由于指针base类型为void*我们是无法进行解引用操作的（也就是通过元素地址访问该元素的操作），那该怎么办呢？起始也不难，我们先将base强制类型转化为char*（这样就可以进行解引用操作了，虽然只能读一个字节），那我们一个字节一个字节的交换不就行了嘛，反正我们也知道每个要被交换元素的大小。

---

3.5 实现代码🍖

void swap(char* e1, char* e2, int width)
{
	while (width--)
	{
		char tmp = *e1;
		*e1 = *e2;
		*e2 = tmp;
		e1++; e2++;
	}
}

void bubble_sort(void* base, int num, int width, int (*cmp)(const void*, const void*))
{
	int i = 0;
	for (i = 0; i < num - 1; i++)
	{
		int j = 0;
		int flag = 1;
		for (j = 0; j < num - 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);
				flag = 0;
			}
		}
		//一趟下来flag为1，则表示数组已经有序；为0则表示数组还未有序。
		if (flag == 1)
		{
			break;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

这份博客👍如果对你有帮助，给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️，谢谢！！！
如果有什么疑问或不同的见解，欢迎评论区留言欧👀。