首页 > 其他分享 >C语言：qsort详解

C语言：qsort详解

时间：2024-08-06 18:23:22浏览次数：5  
标签：sz arr int void qsort C语言 char width 详解

在上一篇文章我们大致的了解了回调函数的用法和作用，在这一篇让我们来了解一下在回调函数qsort的使用吧。

一.qsort

qsort是一种用来排各种类型数据的函数，利用的是快速排序的方式。说到排序，我们就想到了之前学习的冒泡排序，但冒泡排序也有很明显的缺点：时间复杂度太高，效率慢，但qsort就快很多了，并且还支持各种类型的排序。

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*)：函数指针指向了一个函数，这个函数是用来比较两个元素的，存放的是需要比较的两个元素的地址。 

大于返回>0的数，小于返回<0的数，等于返回0

二.qsort的使用

1.使用qsort函数排序整型数据 

#include<stdio.h>
#include<string.h>
int cmp_t(const void* e1, const void* e2)
{
	return *(int*)e1 - *((int*)e2);
}
void print(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
void test()
{
	int arr[10] = { 3,5,7,9,1,2,8,4,6,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_t);
	print(arr, sz);
}
int main()
{
	test();
	return 0;
}

因为数组名为首元素地址所以我们第一个只需要将arr传过去，第二个我们用sizeof求出元素个数并赋给sz，第三个是一个元素的大小，所以我们只需要用sizeof求一个元素的大小即可，在最后传一个判断大小的函数名。在进入函数体，我们首先先确定我们的具体需求，我们要的是俩个整数进行比较，但是这里我们拿到的地址是 void* 类型的，所以我们需要进行强制转化，把俩个参数转化为整形，这样才能满足我们的需求。

在判断函数中，因为大于返回>0的数，小于返回<0的数，等于返回0，所以，我们只需要让e1-e2即可,现在我们求出来的是升序，如果我们想要求降序只需要让e2-e1即可。 

判断函数这里更是我们需要注意的地方，我们进入到判断函数中，这个两个参数，都是 void* 的类型，这样设定的目的是为了拿到一个地址，为了泛型编程的思想，我们这里只管拿到地址，不需要思考怎么处理这俩个地址，所以使用 void* 这样就能满足更多的需求。

 2. 使用qsort函数排序字符串

#include<stdio.h>
#include<string.h>
int cmp_t(const void* e1, const void* e2)
{
	return strcmp((char*)e1, (char*)e2);
}
void print(char* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%c ", arr[i]);
	}
}
void test()
{
	char arr[] ="dcfghta";
	int sz = strlen(arr);
	qsort(arr, sz, sizeof(arr[0]), cmp_t);
	print(arr, sz);
}
int main()
{
	test();
	return 0;
}

这段代码的运行方式跟上面的其实是一样的，但是对于字符串的比较和求个数是不一样的

所以我们接下来就要讲解一下strlen和strcmp 

1.strlen


我们知道字符串“abcdef"其实是由a b c d e f \0组成的，当我们用sizeof函数是会把\0算在里面，但我们却不需要它，这时候就要用到strlen函数了。

strlen的作用：他是用来计算字符串长度的函数，当他遇到‘\0'的时候就会停止。

需要包含头文件string.h

2.strcmp

strcmp函数是C语言中的一个标准库函数，用于比较两个字符串的大小。它的原型int strcmp(const char *str1, const char *str2);，其中str1和str2是两个要比较的字符串的指针。

大于返回>0的数，小于返回<0的数，等于返回0

好了既然我们已经了解了他们，现在就让我们来看一下结果吧

3.使用qsort排序结构数据 

#include<stdio.h>
#include<string.h>
struct S
{
	char name[20];
	int age;
};
int cmp_name(const void* e1, const void* e2)
{
	return strcmp((*(struct S*)e1).name , (*(struct S*)e2).name);
}

void test()
{
	int i = 0;
	struct S s[3] = { {"zhangsan",20},{"lisi",15},{"liliu",18}};
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_name);
	for (i = 0; i < sz; i++)
	{
		printf("%s ", s[i].name);
	}
}
int main()
{
	test();
	return 0;
}

虽然他是结构体类型，但是这段代码本质上比较字符串 ，按照我们的猜想应该长的在后短的在前，但是在我们排序字符串时我们发现字母他是按照循序依次增大的，在多个字符串比较时，他是对应这比较的例如：lisi和liliu,他是l和l，比i和i比，s和l比，比到这时s大于l，这就导致了，lisi大于liliu.那么让我们看一下是否是这样吧。

既然我们能按照名字来比， 我们肯定也可以来按照年龄来比

#include<stdio.h>
#include<string.h>
struct S
{
	char name[20];
	int age;
};
int cmp_age(const void* e1, const void* e2)
{
	return (*(struct S*)e1).age - (*(struct S*)e2).age;
}

void test()
{
	int i = 0;
	struct S s[3] = { {"zhangsan",20},{"lisi",15},{"liliu",18} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_age);
	for (i = 0; i < sz; i++)
	{
		printf("%d ", s[i].age);
	}
}
int main()
{
	test();
	return 0;
}

 三.qsort函数的模拟实现

既然qsort函数这么厉害，我们可不可以用冒泡排序的方法来实现qsort呢？

我们发现qsort的形式

void qsort (void* base， size_t num， size_t size, int (*compar)(const void*, const void*));

如果我们创造一个函数bubble_sort将他的形式按照qsort的模样仿制出来是不是就可以了

void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))

1.元素的判断

 在之前我们知道我们传过来的是什么类型的数据，所以我们可以直接进行判断，但现在我们并不知道会传过来什么类型的数据，导致在循环的过程中不知道跳过一个字节所以我们需要改变判断条件，但我们该如何进行改变呢，既然我们不知道他们的类型，但我们可以得到一个元素的大小，我们再用一个元素的大小去乘于j,就能得到跳过几个字节了在加上首元素的字节，同时也得到了元素的地址，只要我们在传到判断函数中就能的到大小了。

void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				
			}
		}
	}
}

2.元素的交换

既然我们已经的到了如何判断大小，接下来我们就应该进行交换了。 我们同样不知道会传过来什么类型的数据，但我们可以知道类型字节的大小，我们只要将字节的首地址传过去，在交换每个字节就可以交换两个数据了

void sort(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				sort((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
			}
		}
	}
}

3.完整代码

#include<stdio.h>
int cmp_t(const void* e1, const void* e2)
{
	return *(int*)e1-*(int*)e2;
}
void sort(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void print(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				sort((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
			}
		}
	}
}
void test()
{
	int arr[10] = { 3,5,7,9,1,2,8,4,6,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_t);
	print(arr, sz);
}
int main()
{
	test();
	return 0;
}

同样的我们也来看一看排字符串

#include<stdio.h>
#include<string.h>
int cmp_t(const void* e1, const void* e2)
{
	return strcmp((char*)e1, (char*)e2);
}
void sort(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				sort((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
			}
		}
	}
}
void test()
{
	char arr[] = "dcfghta";
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_t);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%c ", arr[i]);
	}
} 
int main()
{
	test();
	return 0;
}

排结构数据(名字)

#include<stdio.h>
#include<string.h>
struct S
{
	char name[20];
	int age;
};
int cmp_t(const void* e1, const void* e2)
{
	return strcmp((*(struct S*)e1).name, (*(struct S*)e2).name);
}
void sort(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				sort((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
			}
		}
	}
}
void test()
{
	struct S s[3]= { {"zhangsan",20},{"lisi",15},{"liliu",18} };
	int sz = sizeof(s) / sizeof(s[0]);
	bubble_sort(s, sz, sizeof(s[0]), cmp_t);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s ", s[i].name);
	}
}
int main()
{
	test();
	return 0;
}

排结构数据(年龄)

#include<stdio.h>
#include<string.h>
struct S
{
	char name[20];
	int age;
};
int cmp_t(const void* e1, const void* e2)
{
	return (*(struct S*)e1).age- (*(struct S*)e2).age;
}
void sort(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* arr, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				sort((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
			}
		}
	}
}
void test()
{
	struct S s[3] = { {"zhangsan",20},{"lisi",15},{"liliu",18} };
	int sz = sizeof(s) / sizeof(s[0]);
	bubble_sort(s, sz, sizeof(s[0]), cmp_t);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", s[i].age);
	}
}
int main()
{
	test();
	return 0;
}

好了今天的分享就到这里吧，还请大家多多关注，我们下一篇见！ 

标签：sz,arr,int,void,qsort,C语言,char,width,详解
From： https://blog.csdn.net/zm3rttqs9f/article/details/140917352

相关文章

  • 排序算法 选择排序 SelectSort -- C语言实现
    选择排序描述选择排序是一种简单直观的排序算法，无论什么数据进去都是O(n²)的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了。算法步骤首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻......
  • c语言11天笔记
    函数的概述函数：实现一定功能的，独立的代码模块。我们的函数一定是先定义，后使用。使用函数的优势：1.我们可以通过函数提供功能给别人使用。当然我们也可以使用别人提供的函数，减少代码量。2.借助函数可以减少重复性的代码。3.实现结构化（模块化）程序设计思想:结构化程序设......
  • C语言开发1——C语言基础1——第一章
    本章目录一、什么是C语言（一）、自然语言（二）、C语言（三）、自然语言与C语言的区别二、计算机语言的发展历史三、C语言特点（一）、优点（二）、缺点四、环境搭建（一）、下载软件（二）、安装软件五、第一个C程序（一）、创建项目 （二）、创建文件（三）、编写代码（四）、运行程序六、注释（一）、作......
  • 【验证码逆向专栏】某安登录流程详解与验证码逆向分析与识别
    声明本文章中所有内容仅供学习交流使用，不用于其他任何目的，不提供完整代码，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！本文章未经许可禁止转载，禁止任何修改后二次传播，擅自使用本文讲解的技术而导致的任何意外，作......
  • 排序算法 冒泡排序 BubbleSort -- C语言实现
    冒泡排序描述冒泡排序（BubbleSort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢......
  • cudart64_90.dll缺失？一文详解CUDA运行时环境修复步骤
    cudart64_90.dll是一个与NVIDIACUDA（ComputeUnifiedDeviceArchitecture）框架相关的动态链接库（DynamicLinkLibrary，简称DLL）。CUDA是NVIDIA开发的一种并行计算平台和编程模型，它允许开发者利用NVIDIAGPU的并行处理能力来进行高性能计算。cudart64_90.dll是CUDA运行时库的一部......
  • C语言学习笔记 Day9（指针--上）
    Day9 内容梳理：目录Chapter7  指针7.0内存的概述7.1 基础知识（指针&指针变量）7.2指针7.3指针变量（1）野指针（2）空指针（3）万能指针void*（4）const修饰的指针变量Chapter7  指针7.0内存的概述存储器：计算机中用来存储程序和数据以便辅助CPU进行运算处理的组件......
  • Mipi SoundWire Spec 详解
    4技术概览（参考性） 4.1引言本规范描述了SoundWire接口，该接口用于传输通常与音频功能相关的数据。SoundWire促进了低成本、高效、高性能系统的开发，其特性包括：通过单一的双针脚接口（时钟和数据线）传输所有负载数据通道、控制信息和设置命令；时钟缩放和可选的多个数据通道，以提供......
  • C#:具体类=＞抽象类=＞接口的进化过程详解
    文章目录简单复习继承与多态具体类抽象类及成员使用语法接口抽象类到接口的进化简单复习继承与多态下面,我用一个交通工具的例子来快速复习一下.1.首先我定义一个基类Vehicle,代表交通工具的总称.里面定义了一个可被重写的成员方法Run.classVehicle{......
  • HTML5 WebSocket 详解及使用
    1.WebSocket是什么？WebSocket是HTML5提供的一种在单个TCP连接上进行全双工通讯的协议。（双向通信协议）2.WebSocket的作用？实现客户端与服务器之间的双向通信，允许服务端主动向客户端推送数据。在WebSocketAPI中，浏览器和服务器只需要完成一次握手，两者之间就直......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99