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

发布时间:2024年01月06日

𝙉𝙞𝙘𝙚!!👏🏻???????👏🏻??????? 👏🏻?????: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~~~以上就是今日要为大家分享的。要是觉得还不错的话,希望咱一波赞走起,给个关注,同时也蟹蟹各位大佬的支持,看到必回!!!

文章来源:https://blog.csdn.net/X_do_myself/article/details/135423065
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。