【C语言】qsort的使用 && Bubble_sort模拟实现qsort

约定不等于承诺〃 2023-09-28 09:03 20阅读 0赞

今天主要讲解一下qsort函数的使用，以及通过冒泡排序来模拟qsort函数

**目录**

Bubble\_sort

冒泡排序

冒泡排序优化

qsort的使用

void\*类型

qsort实现各种类型排序

Bubble\_sort模拟实现qsort

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

# Bubble\_sort #

## 冒泡排序 ##

*先来看段简单的冒泡排序（升序）代码：*

#include<stdio.h>
    void Bubble_sort(int* arr, int sz)
    {
    	int i = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
    		int j = 0;
    		for (j = 0; j < sz - i - 1; 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;
    }

*想象一下，如果数组本身的数据排序就是升序，没有必要再去排序，但对于这种冒泡排序岂不是也要在排一遍，不够优化。*

# 冒泡排序优化 #

#include<stdio.h>
    void Bubble_sort(int* arr, int sz)
    {
    	int i = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
    		int flag = 1;//假设数组是升序
    		int j = 0;
    		for (j = 0; j < sz - i - 1; 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;
    		}
    	}
    }
    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;
    }

*这样是不是效率就提高了不少呢？*

*但是*

*有没有思考过这样一个问题，这样的冒泡排序再怎么优化只能实现对整形数组的排序，（形参接收类型为int\*）对其他的类型却无法实现排序?*

***对于qsort函数来说，这都不是问题，她说：“我可以排序任意类型的数据~”。***

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

# qsort的使用 #

## void\*类型 ##

先看一下qsort类型函数是如何定义的

![859bba9fbe48489c8c7093fbe1f58113.png][]

**第一个参数：数组首元素地址**

**第二个参数：需要排序的长度**

**第三个参数：每个元素的类型大小（单位：字节）**

**第四个参数：函数指针——比较函数,e1和e2是需要比较的两个元素的地址**

*为什么会出现void\*的指针呢？*

*viod\*是无类型指针，可以接收任意类型的数据，但是要注意，对于void\*指针，不能进行解引用操作，也不能+1-1操作，需要进行强制类型转换，例如我传入一个整形，如下代码*

int* a = (int*)e1;

*创建一个整形指针来存放强制转换后的指针。*

*这第四个参数是什么意思呢？*

*qsort函数可以排序任意类型的数据，但是，她也不知道你要让他排什么类型的数据，因为不同类型的数据比较的方法不一样，（整形数据，大于小于号就可以比较，那对于结构体呢？）所以这个时候，就引入了第四个参数——函数指针，这个比较函数需要自己设计，此函数返回类型是int，规定若返回于一个大于零的数就按降序排序，若返回一个小于零的数就按升序排序*

还是有点懵？继续往下看~

## qsort实现各种类型排序 ##

为了便于理解，比较函数写成以下形式：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    int cmp_int(const void* _a, const void* _b)
    {
    	int* a = (int*)_a;
    	int* b = (int*)_b;
    	return *a - *b;
    }
    int cmp_char(const void* _a, const void* _b)
    {
    	char* a = (char*)_a;
    	char* b = (char*)_b;
    	return strcmp(a, b);
    }
    int cmp_double(const void* _a, const void* _b)
    {
    	double* a = (double*)_a;
    	double* b = (double*)_b;
    	return *a > *b ? 1 : -1;
    }
    int main()
    {
    	int in[] = { 2,5,6,4,8,7,1,3 };
    	char ch[] = "helloworld";
    	double dou[] = { 5.6,5.2,7.2,5.6,4.8,9.1,4.2 };
    	int size_in = sizeof(in) / sizeof(in[0]);
    	int size_ch = sizeof(ch) / sizeof(ch[0]);
    	int size_dou = sizeof(dou) / sizeof(dou[0]);
    	qsort(in, size_in, sizeof(in[0]), cmp_int);
    	qsort(ch, size_ch, sizeof(ch[0]), cmp_char);
    	qsort(dou, size_dou, sizeof(dou[0]), cmp_double);
    	//打印整形
    	int i = 0;
    	for (i = 0; i < size_in; i++)
    	{
    		printf("%d ", in[i]);
    	}
    	printf("\n");
    	//打印字符串
    	for (i = 0; i < size_ch; i++)
    	{
    		printf("%c", ch[i]);
    	}
    	printf("\n");
    
    	//打印浮点数
    	for (i = 0; i < size_dou; i++)
    	{
    		printf("%lf ", dou[i]);
    	}
    	printf("\n");
    	return 0;
    }

*这里可以明显体现出不同类型之间的不同比较方式。*

*当然比较函数也可做如下调整，看起来更简洁~*

int cmp_int(const void* e1, const void* e2)
    {
    	return *(int*)e1 - *(int*)e2;
    }
    int cmp_char(const void* e1, const void* e2)
    {
    	return strcmp((char*)e1, (char*)e2);
    }
    int cmp_double(const void* e1, const void* e2)
    {
    	return *(double*)e1 > *(double*)e2 ? 1 : -1;
    }

*接下来看一下结构体类型的比较*

*实际上也是整形、字符、字符串...等类型的比较。*

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    struct stu
    {
    	char name[30];
    	int age;
    };
    int cmp_struct(const void* e1, const void* e2)
    {
    	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
    }
    int main()
    {
    	struct stu s[] = {
       {"Franz Liszt",36},{"F.F.Chopin",45},{"Johann Sebastian Bach",35}};
    	int sz = sizeof(s) / sizeof(s[0]);
    	qsort(s, sz, sizeof(s[0]), cmp_struct);
    	return 0;
    }

*想知道qsort内部是如何运作的吗？*

*往下走~*

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

## Bubble\_sort模拟实现qsort ##

这回我们试试通过改造冒泡排序来实现qsort函数

#include<stdio.h>
    int cmp_int(const void* e1, const void* e2)
    {
    	return *(int*)e1 - *(int*)e2;
    }
    void Swap(size_t width, char* e1,char* e2)
    {
    	int i = 0;
    	for (i = 0; i < width; i++)
    	{
    		char tmp = *e1;//以最小单位一个一个字节的交换
    		*e1 = *e2;
    		*e2 = tmp;
    		e1++;//两地址加加，向后访问，直到到达此类型大小为止
    		e2++;
    	}
    }
    void Bubble_sort(void* base, size_t sz, size_t width, int(*cmp)(const void* elem1, const void* elem2))
    {
    	int i = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
    		int flag = 1;//假设数组是升序
    		int j = 0;
    		for (j = 0; j < sz - i - 1; j++)
    		{
    			if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0)//找到交换的起始位置地址
    			{//这里用char类型是因为不知道这个函数会传入什么类型，所以就用char类型，char类型可以一个一个字节的访问
    				//乘上每个元素的大小（width）就可以跳过该类型的大小
    				Swap(width, (char*)base + j * width, (char*)base + (j + 1) * width);
    				flag = 0;//数组不是升序
    			}
    		}
    		if (flag == 1)
    		{
    			break;
    		}
    	}
    }
    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, sizeof(arr[0]), cmp_int);
    	int i = 0;
    	for (i = 0; i < sz; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    }

解释说明都在代码注释里啦~

**困~**

[859bba9fbe48489c8c7093fbe1f58113.png]: https://img-blog.csdnimg.cn/859bba9fbe48489c8c7093fbe1f58113.png