用代码生撸qsort函数来实现冒泡排序

缺乏、安全感 2023-10-12 17:10 46阅读 0赞

> **作者主页：**paper jie的博客\_CSDN博客-C语言,算法详解领域博主
> 
> **本文作者：**大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。
> 
> **本文录入于**《C语言》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将C语言基础知识一网打尽，希望可以帮到读者们哦。
> 
> **其他专栏：**《系统解析C语言》《算法详解》《C语言-语法篇》
> 
> **内容分享：**本期将用代码生撸C语言中的qsort函数实现冒泡排序，各位看官姥爷快搬好小板凳坐好叭。
> 
>  \-------- 不要998，不要98，只要一键三连，三连买不了吃亏，买不了上当

# 前言 #

在之前的文章中我们讲了简单冒泡排序的实现(不熟悉可以去回顾回顾[http://t.csdn.cn/OI3hN][http_t.csdn.cn_OI3hN])，冒泡排序就是多种排序中的一种简单排序。核心思想就是相邻的元素两两比较，每一对都要比较，符合要求就交换位置，不断重复，直到没有元素需要比较。接下来我们将会了解C语言的库函数qsort，它也可以实现冒泡排序，而且比我们之前写的完善多了，可以适用于不同类型。

# 冒泡排序的实现 #

冒泡排序的核心思想是让相邻的元素两两比较，每一对都要比较，符合要求就交换位置，不断重复，直到没有元素需要比较

算法思想的实现：假设数组内有n个数随机排放。1.在数组初始状态下， 我们将整个数组设为排序范围，范围为数组下标为0-n-1的数。 2.从下标为0的数开始，两两相邻的数比较，如果前一个数大于后一个数，则进行交换。交换后再和后一个数进行比较，一直比较到最后一个数，这样最大的数就被排到到最后了。 3.前面为第一趟排序，我们需要进行n-1趟排序，假设第一次排序标记为0，标记数为i，每过一趟i+1，那么每次排序需要两两比较的次数为 n-1-i。4排序到没有元素可以排序后则排序完成。

下面的代码就是我们自己实现的冒泡排序，我们通过用i控制它的趟数，j控制它每一趟交换多少组来实现了升序。但是这里还有一个很大的问题：它只能对int类型的数据进行排序，换成其他的就不行了。那有没有什么可以让它可以用于不同的类型数据呢？

#include <stdio.h>
    void bubble_sort(int* arr, int sz)
    {
    	int i = 0;
    	int j = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
    		for (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[] = { 9,8,7,6,5,4,3,2,1,0 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	bubble_sort(arr, sz);
    	int i = 0;
    	for (i = 0; i < sz; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    }

# qsort函数 #

## qsort函数的定义 ##

qsort函数是C语言库中的一个函数，它的功能就是对不同的数据类型进行降序或者升序排序，就是相当于冒泡排序。不了解它也没关系，我们可以去 [qsort - C++ Reference (cplusplus.com)][qsort - C_ Reference _cplusplus.com] 上查询qsort函数。![75e19e8bb1b54161922ea940380eb2e6.png][]

我们通过文档可以发现：qsort有4个参数，第一个参数就是数组的首地址，第二参数是数组的元素，第三个参数是元素的大小，第四个参数是一个函数指针，它是用来比较待排序中的两个元素的，它的返回值就是这两个元素相减，>0的话，qsort函数就交换两个元素。这个函数指针指向的函数需要使用者自己设计，因为设计者不知道你要排序的是什么类型的。需要引用头文件是stdlib.h。![477a22ef94bf415fad5407403410a0c0.png][]

## qsort函数的使用 ##

这里我们就以int数组，和结构体数组为例：

**整型数组为例：**

#include <stdio.h>
    #include <stdlib.h>
    //整型数组 - 例
    int  compar_int(const void* e1, const void* e2)
    {
    	return *(int*)e1 - *(int*)e2;
    }
    
    int main()
    {
    	//数组
    	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
    	//元素个数
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	//传参
    	qsort(arr, sz, sizeof(arr[0]), compar_int);
    	//打印
    	for (int i = 0; i < sz; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    }

**结构体数组为例：**

#include <stdio.h>
    #include <stdlib.h>
    //整型数组 - 例
    struct Stu
    {
    	char name[20];
    	int age;
    };
    
    int  compar_int(const void* e1, const void* e2)
    {
    	return ((struct Stu*)e1)->age - ((struct Stu*)e2) -> age;
    }
    
    int main()
    {
    	//数组
    	struct Stu s[] = { {"zhngsan",34},{"lishi",25},{"wangwu", 20}};
    	//元素个数
    	int sz = sizeof(s) / sizeof(s[0]);
    	//传参
    	qsort(s, sz, sizeof(s[0]), compar_int);
    }

# qsort函数的模拟实现 #

**这里还是以int类型数组举例：**

#include <stdio.h>
    
    int compar_int(const void*e1, const *e2)
    {
    	return *(int*)e1 - *(int*)e2;
    }
    
    //交换函数
    //通过char类型加上width来跳过元素
    //char+width(类型的大小)刚好是一个类型的大小
    void swap(char *e1, char *e2, int width)
    {
    	int i = 0;
    	
    	for (i = 0; i < width; i++)
    	{
    		//每一次循环交换一个字节控制的空间的内容
    		//循环完width次彻底交换两个元素
    		char tmp = *e1;
    		*e1 = *e2;
    		*e2 = tmp;
    		e1++;
    		e2++;
    	}
    }
    //模拟函数
    void bublle_sort(void* base, int sz, int width, int (*compar)(const void*, const void*))
    {
    	int i = 0;
    	int j = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
    		for (j = 0; j < sz - 1 - i; j++)
    		{
    			//如果compar函数大于0 就交换
    			if (compar((char*)base + j * width, (char*)base + (j+1)*width)>0)
    			{
    				//交换函数实现
    				swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
    			}
    		}
    	}
    }
    
    int main()
    {
    	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	//模拟qsort函数
    	bublle_sort(arr, sz, sizeof(arr[0]), compar_int);
    		for (int i = 0; i < sz; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    	return 0;
    }

--------------------

# 总结 #

这就是qsort函数的使用和模拟，我们通过使用和模拟发现，qsort函数它非常的巧妙，不由的让我们感叹写出这些代码的人脑子怎么长的，不过我相信只要我们一直学习下去，总有一天我们也有写出这种代码的可能性，与君共勉！

[http_t.csdn.cn_OI3hN]: http://t.csdn.cn/OI3hN
[qsort - C_ Reference _cplusplus.com]: https://legacy.cplusplus.com/reference/cstdlib/qsort/?kw=qsort
[75e19e8bb1b54161922ea940380eb2e6.png]: https://img-blog.csdnimg.cn/75e19e8bb1b54161922ea940380eb2e6.png
[477a22ef94bf415fad5407403410a0c0.png]: https://img-blog.csdnimg.cn/477a22ef94bf415fad5407403410a0c0.png