快速排序和qsort函数详解详解qsort函数

  💕是非成败转头空,青山依旧在,几度夕阳红💕

作者:Mylvzi 

 文章主要内容:快速排序和qsort函数详解 

前言:

我们之前学习过冒泡排序,冒泡排序尽管很方便,但也存在一些局限性,冒泡排序只能排序整型数据,对于浮点型的数据以及结构体数据的排序无能为力,但是在C语言的库中,有一个库函数能够实现这样的排序-->qsort函数 

qsort函数其实是一种基于快速排序的算法,其时间复杂度为O(N*logN),下面带大家了解一下快速排序算法:

一.快速排序:QuickSort 

分析: 

 可以知道,快速排序的核心在于“分区操作”,即每次都要根据基准元素进行分区;

代码实现:

//QuickSort  排序  的实现
//找基准元素,分区,递归,合并//交换函数
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//分割函数:以基准元素为轴,分而治之
int Partition(int arr[], int left, int right)//返回值:基准元素的下标
{//设置默认基准元素int pivot = arr[right];int i = left-1;//将小于基准元素的值放在左边,i是左子数组的下标//遍历数组,移动元素for (int j = left; j <= right; j++){if (arr[j] < pivot)//小于,就放到左边,交换值{i++;Swap(&arr[i], &arr[j]);}}//将基准元素置于轴Swap(&arr[i + 1], &arr[right]);return i + 1;
}void QuickSort(int arr[], int left, int right)//left左下标  right右下标
{if (left < right){//找到基准元素的下标int PivotIndex = Partition(arr, left, right);//对左子数组进行递归分区QuickSort(arr, left, PivotIndex - 1);//对右子数组进行递归分区QuickSort(arr, PivotIndex + 1, right);}}int main()
{int arr[] = { 6, 3, 8, 5, 2, 7, 4 };int n = sizeof(arr) / sizeof(arr[0]);//打印原数组printf("Original array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}// 调用快速排序函数对数组进行排序QuickSort(arr, 0, n-1);//打印排序之后的数组printf("\nSorted array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

验证:

 

优化QuickSort: 

优化一:

缺陷:选取的pivot如果是整个序列的中间值,在第一次partition之后,会得到一个较为平均的分区,处理这样的分区更加简单,效率更高(处理4 4比处理1 8更简单)

解决方法:利用三数取中法使我的pivot是中间值的概率更高

得到数组左中右下标的数据,使pivot为中间值

    //设置默认基准元素int pivot;//优化一:三数取中法优化pivot的取值(处理4 4比处理1 8简单)//不能固定取同一位置的元素为pivotint m = left+ (right - left) / 2;if (arr[left] < arr[right])//保证右边元素较小{Swap(&arr[left], &arr[right]);}if (arr[left] < arr[m])//保证中间元素较小{Swap(&arr[m], &arr[right]);}if (arr[m] > arr[right])//保证右边元素是中间值{Swap(&arr[m], &arr[left]);}pivot = arr[right];//将左中右三个元素的中间值赋给pivot

 

二.基于快速排序的函数-->qsort函数

原型:

代码1:比较整形数据 

//qsort函数
//快速的排序算法,适用于不同的数据类型
//void qsort(
//	void* base,//需要被排序的数组(首地址)
//	size_t num,//数组元素个数
//	size_t size,//元素类型大小
//	int(*cmp)(const void* ptr1, const void* ptr2)//比较函数
//	//ptr1 >ptr2 返回>0  交换位置  默认是升序排序的
//);//利用qsort函数进行冒泡排序
int cmp_int(const void* ptr1, const void* ptr2)
{//默认是升序排序的//结果>0,就会交换位置return (*(int*)ptr1 - *(int*)ptr2);//降序-->添加负号/*return -(*(int*)ptr1 - *(int*)ptr2);*/
}int main()
{int arr[6] = { 4,25,6,78,534,94 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, 6, sizeof(arr[0]), cmp_int);//打印输出排序后的数组int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

 代码2:比较结构体数据

typedef struct Stu
{char name[20];int age;
}Stu;/*按年龄排序*/
int cmp_by_stu_age(const void* ptr1, const void* ptr2)
{return ((struct Stu*)ptr1)->age - ((struct Stu*)ptr2)->age;
}void test()
{Stu arr[3] = { {"zhangsan",13},{"lisi",5},{"wangwu",18} };//按年龄排序int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_by_stu_age);}/*按照姓名排序*/
int cmp_stu_by_name(const void* ptr1, const void* ptr2)
{return strcmp(((Stu*)ptr1)->name, ((Stu*)ptr2)->name);
}
void test2()
{Stu arr[3] = { {"zhangsan",13},{"lisi",5},{"wangwu",18} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
}//排序结构体
int main()
{//test();test2();return 0;
}

代码3:利用冒泡排序的思想模拟实现qsort函数

//利用冒泡排序的思想模拟qsort函数
//模仿qsort的参数
//未知类型数组-->void* base  -->起始地址
//元素个数-->int num
//未知类型-->int size
//比较函数-->将需要比较的数据传递给cmp函数,根据其返回值判断是否需要交换位置//如果返回值>0,就交换元素位置(一个一个字节交换)
void Swap(char* buf1, char* buf2,int size)
{int i = 0;for (i = 0; i < size; i++){int tmp = *buf1; *buf1 = *buf2; *buf2 = tmp;buf1++;buf2++;}}
void bubble_sort(void* base, int num, int size, int(*cmp)(const void* ptr1, const void* ptr2))
{//基本逻辑不变,两两比较,一次确定一个元素的位置int i = 0;//趟数  sz-1趟int j = 0;//每次需要比较的元素个数for (i = 0; i < num - 1; i++){for (j = 0; j < num - 1 - i; j++)  {                                                           //初始地址if (cmp((char*)base + j * size, (char*)base + (j+1) * size) > 0)//比较的的是前后两个元素的地址的数据-->计算地址-->(char*)base+j*size-->返回值>0,就交换{//前面的元素>后面元素就交换位置Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}int main()
{int arr[6] = { 4,25,6,78,534,94 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, 6, sizeof(arr[0]), cmp_int);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/80471.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue+iviewUi+oss直传阿里云上传文件

前端实现文件上传到oss&#xff08;阿里云&#xff09;适用于vue、react、uni-app&#xff0c;获取视频第一帧图片 用户获取oss配置信息将文件上传到阿里云&#xff0c;保证了安全性和减轻服务器负担。一般文件资源很多直接上传到服务器会加重服务器负担此时可以选择上传到oss&…

字节C++后端面试总结

字节的面经,技术栈是 C++ 后端。 计算机网络 UDP和TCP区别 先说了概念一个是面向连接的基于字节流的可靠连接,一个是不需要连接的基于数据报的不可靠传输 然后说了几个小点,比如首部长度、应用场景、服务对象什么的。 补充: 还有一个很重要的点:UDP 的实时性比 TCP 好…

Java的抽象类不能被实例化

Java的抽象类不能被实例化。如果试图实例化&#xff0c;会编译报错。 示例&#xff1a; 定义一个抽象类&#xff1a; package com.thb;public abstract class AbstractPoint {public AbstractPoint() {} }再定义一个主类&#xff1a; package com.thb;public class Test4 {p…

从源码层面深度剖析Spring循环依赖 | 京东云技术团队

以下举例皆针对单例模式讨论 图解参考 https://www.processon.com/view/link/60e3b0ae0e3e74200e2478ce 1、Spring 如何创建Bean&#xff1f; 对于单例Bean来说&#xff0c;在Spring容器整个生命周期内&#xff0c;有且只有一个对象。 Spring 在创建 Bean 过程中&#xff0…

中电金信:ChatGPT一夜爆火,知识图谱何以应战?

随着ChatGPT的爆火出圈 人工智能再次迎来发展小高潮 那么作为此前搜索领域的主流技术 知识图谱前路又将如何呢&#xff1f; 事实上&#xff0c;ChatGPT也并非“万能”&#xff0c;作为黑箱模型&#xff0c;ChatGPT很难验证生成的知识是否准确。并且ChatGPT是通过概率模型执行推…

全新二开美化版UI好看的社区源码下载/反编译版

2023全新二开美化版UI精美的社区源码下载/反编译版 之前我分享过Rule原版&#xff0c;相信大家已经有很多人搭建好了。这次我要分享的是RuleAPP的二开美化版&#xff08;请尊重每个作者的版权&#xff09;&#xff0c;这个版本没有加密&#xff0c;可以进行反编译&#xff0c;…

大数据——推荐系统

1 推荐系统的发展 推荐系统是指面对没有需求的用户在进入产品时&#xff0c;要给用户推荐什么东西&#xff0c;现在的APP基本上都会采用推荐系统。 从一开始的1990s开始的门户网站&#xff0c;像Yahoo、搜狐和Hao123等等&#xff0c;都是基于分类目录的网页导航网站&#xff0…

Llama 2:开放基础和微调聊天模型

介绍 大型语言模型(llm)作为高能力的人工智能助手,在复杂的推理任务中表现出色,这些任务需要广泛领域的专家知识,包括编程和创意写作等专业领域。它们可以通过直观的聊天界面与人类进行交互,这在公众中得到了迅速而广泛的采用。 法学硕士的能力是显著的考虑到训练的表面上…

产业互联网-跨境电商B2B平台

【背景】&#xff1a;互联网已经进入web3.0时代&#xff0c;产业互联网是互联网关键时点&#xff0c;特别是跨境电商&#xff0c;速卖通&#xff0c;亚马逊&#xff0c;wish Ebay&#xff0c;还有出海的titok,temu等&#xff0c;中国企业或平台走出来也是一条光明大通&#xff…

3.4 网络安全管理设备

数据参考&#xff1a;CISP官方 目录 IDS (入侵检测系统)网络安全审计漏洞扫描系统VPN&#xff08;虚拟专网&#xff09;堡垒主机安全管理平台 一、IDS (入侵检测系统) 入侵检测系统&#xff08;IDS&#xff09;是一种网络安全设备&#xff0c;用于监测和检测网络中的入侵行…

【TypeScript】交叉类型联合类型(四)

【TypeScript】交叉类型&联合类型&#xff08;四&#xff09; 【TypeScript】交叉类型&联合类型&#xff08;四&#xff09;一、简介二、交叉类型2.1 交叉类型使用的注意点2.2 基本数据类型交叉2.3 对象类型交叉 三、联合类型四、类型缩减 一、简介 TypeScript 中的交…

坐标转换-使用geotools读取和转换地理空间表的坐标系(sqlserver、postgresql)

前言&#xff1a; 业务上通过GIS软件将空间数据导入到数据库时&#xff0c;因为不同的数据来源和软件设置&#xff0c;可能导入到数据库的空间表坐标系是各种各样的。 如果要把数据库空间表发布到geoserver并且统一坐标系&#xff0c;只是在geoserver单纯的设置坐标系只是改了…

jvm-程序计数器

1、是什么 4 学习路线 类加载器 内存结构方法区 类堆 对象虚拟机栈程序计数器本地方法栈 执行引擎解释器编译器 热点代码 5 程序计数器–作用 java源代码编译蛏二进制字节码 jvm指令。 对所有平台保持一致性。记住下一条jvm指令的执行地址。寄存器&#xff0c;cpu中读取速度…

从零开始学习 Java:简单易懂的入门指南之API、String类(八)

常用API 1.API1.1API概述1.2如何使用API帮助文档 2.String类2.1String类概述2.2String类的特点2.3String类的构造方法2.4创建字符串对象两种方式的区别2.5字符串的比较2.5.1号的作用2.5.2equals方法的作用 2.6用户登录案例2.6.1案例需求2.6.2代码实现 2.7遍历字符串案例2.7.1案…

elementUi select下拉框触底加载异步分页数据

在Element UI中&#xff0c;可以通过监听select下拉框的visible-change事件来实现触底加载下一页的效果。 方式一&#xff1a;利用elementUi的事件 具体步骤如下&#xff1a; 首先&#xff0c;在select组件中设置&#xff1a;visible-change"handleVisibleChange"…

【代码解读】RRNet: A Hybrid Detector for Object Detection in Drone-captured Images

文章目录 1. train.py2. DistributedWrapper类2.1 init函数2.2 train函数2.3 dist_training_process函数 3. RRNetOperator类3.1 init函数3.1.1 make_dataloader函数 3.2 training_process函数3.2.1 criterion函数 4. RRNet类&#xff08;网络模型类&#xff09;4.1 init函数4.…

【GitOps系列】如何实施自动化渐进式交付?

文章目录 前言自动渐进式交付概述自动渐进式交付准备创建生产环境创建 AnalysisTemplate访问生产环境安装Prometheus配置 Ingress-Nginx 和 ServiceMonitor验证 Ingress-Nginx 指标 自动渐进式交付实战自动渐进式交付成功自动渐进式交付失败 结语 前言 在实施金丝雀发布的过程中…

无涯教程-Perl - References(引用)

Perl引用是一个标量数据类型&#xff0c;该数据类型保存另一个值的位置&#xff0c;该值可以是标量&#xff0c;数组或哈希。 创建引用 变量&#xff0c;子程序或值创建引用很容易&#xff0c;方法是在其前面加上反斜杠&#xff0c;如下所示: $scalarref \$foo; $arrayref …

Linux下的环境变量

目录 一、环境变量是什么&#xff1f;二、常见的环境变量三、查看环境变量的方法四、和环境变量相关的命令五、命令行参数五、环境变量通常是具有全局属性的 一、环境变量是什么&#xff1f; 环境变量通俗来说就是一种存储系统和应用程序运行需要的配置信息的方式。可以把环境…

OPENCV C++(四)形态学操作+连通域统计

形态学操作 先得到一个卷积核 Mat kernel getStructuringElement(MORPH_RECT,Size(5,5)); 第一个是形状 第二个是卷积核大小 依次为腐蚀 膨胀 开运算 闭运算 Mat erodemat,dilatemat,openmat,closemat;morphologyEx(result1, erodemat, MORPH_ERODE, kernel);morphologyEx…