基于冒泡排序思想的qsort函数的模拟实现

𝙉𝙞𝙘𝙚!!👏🏻???????👏🏻??????? 👏🏻?????:Solitary-walk

? ? ? ?? ? ━━━┓
? ? ?- 个性标签 - ：来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━ ?? ?

本人座右铭 ： ? 欲达高峰,必忍其痛;欲戴王冠,必承其重。

👑💎💎👑💎💎👑?
💎💎💎自💎💎💎
💎💎💎信💎💎💎
👑💎💎　💎💎👑 ? ?希望在看完我的此篇博客后可以对你有帮助哟

👑👑💎💎💎👑👑 ? 此外，希望各位大佬们在看完后，可以互赞互关一下，看到必回
👑👑👑💎👑👑👑

目录

一：冒泡排序的实现

二：qsort函数的简单介绍

三：基于冒泡排序思想的qsort函数的模拟实现

---

一：冒泡排序

首先我们需要先知道冒泡排序的核心是：两两相邻元素进行比较
冒泡排序的底层逻辑就是 ?双重for循环
1）外循环：需要进行9次比较对应代码

```c
for(int i = 0;i < sz - 1;i++)
```

2）内循环：一趟循环所需要比较的轮次

```c
for(int j = 0;j < sz-1-i;j++)
```

要求：对数组的各个数据按升序进行排列
首先我们先两两相邻元素进行比较：
第一趟比较后对应结果：

对应核心代码：

```c
if (arr[j] > arr[j + 1])
{
?? ?//交换
?? ?tmp = arr[j];
?? ?arr[j] = arr[j + 1];
?? ?arr[j + 1] = tmp;
}
```

```cpp
??

void bubble(int arr[], int sz)
{
?? ?for (int i = 0; i < sz - 1; i++)//确定总的趟数
?? ?{
?? ??? ?for (int 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;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
int main()
{
?? ?int arr[] = { 1,4,7,8,5,2,9,6,3,0 };
?? ?int sz = sizeof(arr) / sizeof(arr[0]);
?? ?bubble(arr, sz);
return 0;
}

}
```
其实对于这个代码还有很多地方可以进行优化，使之变得更具有鲁棒性

> 比如说，当我们这一趟的数据已经是有序的，我们就不需要再次进行比较了，以此节省效率
优化之后的版本：

void bubble(int arr[], int sz)
{
?? ?//确定sz 个元素对应的趟数;sz - 1
?? ?for (int i = 0; i < sz - 1; i++)
?? ?{
?? ??? ?//一趟冒泡排序的 执行
?? ??? ?int flag = 1;//假设一趟是有序的
?? ??? ?for (int 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;
?? ??? ??? ??? ?flag = 0;//这一趟是无序的
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if (flag == 1)
?? ??? ?{
?? ??? ??? ?break;//直接终止循环，无需在进行排序，提高了效率
?? ??? ?}
?? ?}
}

?二：qsort( )

1）qsort( )

void qsort (void* base,
            size_t num,
            size_t size,      
            int (*compar)(const void*,const void*));
参数介绍：
void*base:指向待排序的第一个元素的地址

size_t num:待排序元素的个数

size_t size:待排序的每一个元素的大小，单位字节

int (*compar)(const void*,const void*)) ：函数指针，用来实现数据的排序，需要使用者自己? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 设计，注意这里参数类型不能改变

2）qsort( )简单应用

对整型数据排序：

int  cmp_int(const void* p1, const void* p2)
{
		//return (*p1 - *p2);//err 对于void* 类型的指针只能进行强转，之后在进行解引用或者是指针运算
	return (*(int*)p1 -  *(int*)p2);
}
void Print(int* parr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", *(parr + i));
	}
}
int main()
{
	int arr[] = { 7,4,1,8,5,2,9,6,3,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(int), cmp_int);
	Print(arr, sz);
	return 0;
	/*
	直接对void*类型的指针解引用出现：非法的间接寻址
	 对于void*类型的指针只能进行强转，之后在进行解引用或者是指针运算

	*/
}

?

?qsort()函数不是很牛吗，接下来看看对结构体类型数据排序如何？

对结构体类型数据进行排序：

struct Student
{
	char name[10];
	int age;
};
int cmp_by_name(const void* p1, const void* p2)
{
	//return (*(char*)p1 - *(char*)p2); //注意字符串比较不能直接相减，借助strcmp()函数
	//int strcmp ( const char * str1, const char * str2 );
	return strcmp ((char*)p1 , (char*)p2);
}
int main()
{
	/*int arr[] = { 7,4,1,8,5,2,9,6,3,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);*/
	struct Student arr1[] = { {"wisi,12"},{"langwu",14},{"zhangsan",13} };
	qsort(arr1, 3, sizeof(struct Student), cmp_by_name);
	return 0;
	/*
	直接对void*类型的指针解引用出现：非法的间接寻址
	 对于void*类型的指针只能进行强转，之后在进行解引用或者是指针运算

	*/
}

这是排序之前数组的内容：?

排序之后数组的内容：（注意是根据名字这个成员进行排序，也就是按对应位置的字母ASCII值进行比较）

?

3）qsort( ) 借助冒泡排序思想的模拟实现?

思路的分析：

1）首先知道冒泡排序的核心：两两相邻元素进行比较

2）qsort( )各个参数意义：见文章上面介绍

3）void*类型指针应用的小注意

4）借助画图更易于理解

?以交换整型数据为例：

首先我们需要思考2个重要问题：

你有思绪了吗？没关系，接下来，我们一起来分析：

?对于问题1：

? ? ? ? 我们需要借助一个函数指针，来实现对数据的比较；其次这里对指针的使用是有要求的，因为数据类型可以是任意的：int,long,float,结构体.......

那我们这里到底使用什么类型指针？

? ? ? ?毋庸置疑：char*? ,它是最小的，对他进行解引用是一个字节一个字节的，这样就会避免我们对指针访问不精确的问题

对应核心代码：注意这里我们假设以升序来排列

还是以整型数据来进行分析：

因为已经知道每个元素大小：width,

要比较的第一个元素地址已知

注意对 void* 类型指针不能直接用这里借助强转

下标为 j 对应地址? ?(char*)base + j * width

下标为 j + 1对应地址? ?(char*)base +（ j+1） * width

?

			// 假设按升序来排序
			if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0)  //借助cmp_int来进行判断大小，需要把当前下标为j ，j+1 的地址传进去  ，重点是以什么类型指针来传进去
			

?问题2分析：

这里我们另写一个交换函数Swap( ) ,避免看起来复杂

? 其实这个问题和上一个大同小异，既然是要交换元素，必然传地址，那么以什么类型指针接收呢？

显然是char*，同时我们还需要把这个要比较元素的大小传进来，

?

对应核心代码：

void Swap( char* p1,  char* p2,int size) //注意这里必须把要比较每一个元素大小传来
{
	// 一个字节一个字节交换
	char tmp = 0;
	for (int i = 0; i < size; i++)
	{
		tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		// p1,p2更新位置
		p1++, p2++;
	}
}

?对应完整代码：

int  cmp_int(const void* p1, const void* p2)
{
	//return (*p1 - *p2);//err 对于void* 类型的指针只能进行强转，之后在进行解引用或者是指针运算
	return (*(int*)p1 - *(int*)p2);
}
void Swap( char* p1,  char* p2,int size) //注意这里必须把要比较每一个元素大小传来
{
	// 一个字节一个字节交换
	char tmp = 0;
	for (int i = 0; i < size; i++)
	{
		tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
		// p1,p2更新位置
		p1++, p2++;
	}
}
void my_qsort(void* base, int num,int width,int (*cmp_int)(const void*,const void*))
{
	//借助冒泡进行排序
	for (int i = 0; i < num - 1; i++)  //确定趟数
	{
		for (int j = 0; j < num - 1 - i; j++)  //一趟的比较
		{
			// 假设按升序来排序
			if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0)  //借助cmp_int来进行判断大小，需要把当前下标为j ，j+1 的地址传进去  ，重点是以什么类型指针来传进去
			{
				// 进行交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);//把下标为j 和j+1的地址传进去
			}

		}
	}
}
int main()
{
	int arr[] = { 7,4,1,8,5,2,9,6,3,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//struct Student arr1[] = { {"wisi,12"},{"langwu",14},{"zhangsan",13} };
	my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
	Print(arr, sz);
	return 0;
	/*
	直接对void*类型的指针解引用出现：非法的间接寻址
	 对于void*类型的指针只能进行强转，之后在进行解引用或者是指针运算

	*/
}

?

?接下来我们试一下看看对结构体类型的数据排序效果如何

?

?ok~~~以上就是今日要为大家分享的。要是觉得还不错的话，希望咱一波赞走起，给个关注，同时也蟹蟹各位大佬的支持，看到必回！！！