用qsort函数来模拟实现全类型的冒泡排序

目录

1.冒泡排序

2.qsort函数的认识 

3.qsort函数的实现

4.模拟实现全类型冒泡排序

参数设置：

 接收参数：

​编辑 编写cmp函数中的参数：

交换顺序：

5.整体展示

1.冒泡排序

算法思想：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 

冒泡排序优点： 简单，通俗易懂

       缺点：效率不高 （如果一个数组有n个数，那么排序完成后需要比较n*(n-1)/2次)  并且一般适用于整形 如果是结构体类型，浮点型类型或者其他类型，就会很麻烦 

2.qsort函数的认识 

 推荐一个网站 ：cplusplus.com  

如果有不认识或不知如何使用的函数，可以使用改网站查询

 这个函数专门用于排序 并且它可以适用于多种类型

qsort()函数：快速排序的函数  -引用stdlib.h头文件

 

参数说明：

 void qsort ( 

      void* base,     //要排序的目标数组
      size_t num,     //待排序的元素个数
      size_t width,    //待排序单个元素的大小
      int(*cmp)(const void* e1, const void* e2)

);  // cmp为函数指针，用来比较e1和e2中俩个元素的大小 需要自己结合元素类型编写

 

3.qsort函数的实现

 接下来我们来实现这个函数

步骤少，比较简单，这里就不打印了，调试一下看一下结果

 

 主要难点在于qsort函数中的第四个参数 那个是一个函数指针 我们需要自己根据不同的类型来制定这个函数 

 为什么用void*接收  

 void*：无具体类型的指针   它能够接收任意类型的地址 所以不管是什么类型的地址，我们可以用一个通用的void*接收

但是不能直接对e1和e2进行解引用操作，现在他们现在还是viod*类型 所以必须得强制转化成指针自己的类型  

比如现在float型类型 我们应该写成  return *(float*e1)-*(float*e2).....

例如：现在我排序一个结构体类型的数据，

 

 

这里是按年龄排序，如果按名字排序也是一样的 但是名字排序因为排序的字符，得借助一个函数strcmp函数 字符是不能通过加减排序的

 strcmp刚刚好比较俩个字符的大小

 

快速排序可以排序所有的类型，接下来我们将用qsort函数的方法来实现全类型的冒泡排序

4.模拟实现全类型冒泡排序

 

首先这只是一个最普通的冒泡排序，我们需要对于原冒泡排序进行改造，按qsort函数的方式进行增加内容；

参数设置：

前三个参数很好写，第四个参数是一个函数指针，得需要自己根据类型来编写

例如现在编排一个整形类型

 接收参数：

注：因为我们要编写一个适应于全类型的函数，所有第一个参数用void*来接收

 编写cmp函数中的参数：

接下来我们应该开始比对大小，我们要编写一个适用于全类型的函数来进行比对大小

我们可以套用我们写的cmp函数 因为它那个就是比较大小的 

难点就是如何获取他们要比较的e1和e2的地址

因为我们不知道是什么类型的排序，所有我们先给它强制转化为（char*）类型的(char* 类型的变量加减是一个一个字节加减的)，随后跟size这个参数我们便能知道它们每个字节占的大小 ，我们就能获取到每一个元素的地址

交换顺序：

 交换我们最好编写一个函数

注：因为是char*类型，它是一个字节一个字节交换，我们把它的size传过去即可

5.整体展示

int类型：

#include 
void swap(char* buf1, char* buf2, int size)
{
	int i;
	for (i = 0; i < size; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void *base, int sz,int size,int (*cmp)(const void* e1,const void* e2))
{
	int i;
	for (i = 0; i < sz - 1; i++)
	{
		int j;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				swap( (char*)base + j * size , (char*)base + (j + 1) * size , size);
			}
		}
	}
}
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
test1()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	int i;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	test1();
}

 排序一个结构体类型的数据，按名字排序：

#include 
struct stu
{
	char name[10];
	int age;
};
void swap(char* buf1, char* buf2, int size)
{
	int i;
	for (i = 0; i < size; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void* base, int sz, int size, int (*cmp)(const void* e1, const void* e2))
{
	int i;
	for (i = 0; i < sz - 1; i++)
	{
		int j;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
	}
}
int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
 
int main()
{
	struct stu s[] = { {"zhangsan",15},{"lisi",18},{"wangwu",11},"mahua",8 };
	int sz = sizeof(s) / sizeof(s[0]);
	bubble_sort(s, sz, sizeof(s[0]), cmp_by_name);
	int i;
	for (i = 0; i < sz; i++)
	{
		printf("%s ", s[i].name);
	}
	
}