冒泡排序模拟实现qsort()函数-Toy模板网

这篇具有很好参考价值的文章主要介绍了冒泡排序模拟实现qsort()函数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

要模拟qsort()函数，我们首先要知道qsort()函数的特点：

使用快速排序的方法。
适用于任何数据类型的排序。

但由于部分学者还没有学习快速排序算法，所以本篇博客采用冒泡排序来模拟功能类似于qsort（）的函数bubble_sort。

C库对qsort()函数解释：
冒泡排序模拟实现qsort()函数,排序算法,算法,数据结构

我们得到的关于qsort()函数参数信息：

void qsort(void* base, //指向排序的第一个元素
		   size_t num, //排序元素的个数
		   size_t size,//一个元素的大小，单位为字节
		   int (*cmp)(const void*, const void*)//函数指针类型 — 这个函数指针指向的函数，能够比较base指向数组的两个元素
);

1. 分析

我们首先来看一段普通的冒泡排序来排序整型数据

void bubblr_sort(int arr[], int sz)
{
	//排序趟数
	for (int i = 0; i < sz - 1; i++)
	{
		int tmp = 0;
		//每趟比较对数
		for (int j = 0; j < sz - 1 - i; j++)
		{
			//假设升序，交换元素
			if (arr[i] > arr[i + 1])
			{
				tmp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tmp;
			}
		}
	}
}
int main()
{
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	return 0;
}

既然是用冒泡排序来模拟qsort()函数，我们可以以上面这段代码为基础，需改模拟实现。但存在几个问题！！

如何接受不同的数据类型，而不仅仅是整型。
对于不同的数据，比如结构体不能简单的用>或<还比较，那如何实现呢？
对于不同的数据类型，交换略有差异

2. 解决一，如何接受不同数据

void* 是C语言中的通用指针类型，可以指向任意类型的数据。所以我们可以将参数base定义为void*类型指针，来接受不同的数据。

void*用法拓展：

在使用void* 指针时，因为它不知道指向的类型的大小，需要将其转换为具体的指针类型才能进行操作。例如，可以将void 指针转换为int 指针，然后*对其进行赋值或者解引用操作。
2. void * 是一个无类型指针，在由于进行算术运算时，需要知道指针指向的具体数据类型的大小以便确定移动的字节数，所以它不能直接进行算术运算。

3. 解决二，如何实现不同数据的比较

由于不同的数据类型有不同的比较方法，我们可以在模拟的bubble_sort()函数参数中添加一个函数指针。将两个元素的比较方法，函数参数的形式进行传递。

Tips:

目前传入的数据以整型为例，所以我们定义比较函数名为cmp_int。在文章结尾将给出传入结构体数据的实现代码。

代码实现

//bubble_sort()实参传入
bubble_sort(arr,sz, sizeof(arr[0]), cmp_int);

//bubble_sort()函数参数实现
void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*))

//cmp_int函数实现
int cmp_int(const void* p1, const void* p2)
{
	//强制类型转换为int* ,在进行解引用
	return (*(int*)p1 - *(int*)p2);//假设升序，则返回>0的数
	//至于为什么返回这个数据，参考qsort()函数模仿即可
}

4. 解决三，如何实现不同数据交换

对于不同的数据，我们可以交换的两个数的起始地址强制类型转化为（char*）,然后计算出两个数据大小，最后两则一个一个字节交换即可。

代码实现

//数据交换我们封装一个Swap()函数
void Swap(char* buf1, char* buf2, int size)//交换arr[i]和arr[i+1]
{
	char tmp = 0;
	while (size--)
	{
		tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

5. 模拟bubble_sort（）函数排序整型所有代码实现

由于是在冒泡排序的基础上来实现排序的，而排序的趟数和每趟排序的对数是不变的。所有我们只要解决上述问题，将相关代码进行替换即可。

代码实现

#include <stdio.h>

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

void Swap(char* buf1, char* buf2, int size)//交换arr[i]和arr[i+1]
{
	char tmp = 0;
	while (size--)
	{
		tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*))
{
	int i = 0;
	//趟数
	for (i = 0; i < num; i++)
	{
		//一趟比较对数
		//假设升序
		for (int j = 0; j < num - 1 - i; j++)
		{
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)//比较两个元素，需要将arr[j]和arr[j+1]的地址传给cmp
			{
				//交换
				Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
	}
}


//测试bubble_sort排序整型数据
void test1()
{
	int arr[] = { 4,2,5,8,3,8,34,23,1,54 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr,sz, sizeof(arr[0]), cmp_int);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}


int main()
{
	test1();
	return 0;
}

运行结果：
冒泡排序模拟实现qsort()函数,排序算法,算法,数据结构

6. 结构体排序实现

排序结构体时，Swap()和bubble_sort（）函数实现是相同的；我们只需要改变以下int_cmp函数即可（注：int_cmp()函数的名字依据比较数据不同，博主命名不同）

代码实现

#include <stdio.h>
#include <string.h>

void Swap(char* buf1, char* buf2, int size)//交换arr[i]和arr[i+1]
{
	char tmp = 0;
	while (size--)
	{
		tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*))
{
	int i = 0;
	//趟数
	for (i = 0; i < num; i++)
	{
		//一趟比较对数
		//假设升序
		for (int j = 0; j < num - 1 - i; j++)
		{
		    //比较两个元素，需要将arr[j]和arr[j+1]的地址传给cmp
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				//交换
				Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
	}
}


//测试bubble_sort排序结构体数据
struct Stu
{
	char name[20];
	int age;
};

int cmp_stu_by_name(const void* p1, const void* p2)
{
	//比较两个字符时，需要借助函数strcmp()来实现
	return strcmp(((struct Stu*)p1)->name ,((struct Stu*)p2)->name);
}

void test2()
{
	struct Stu arr[] = { {"zahngsan",20},{"lisi",12},{"wangwu",43} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
}


int main()
{
	test2();
	return 0;
}