用冒泡排序的思想模拟实现Qsort

简介: 用冒泡排序的思想模拟实现Qsort

什么是冒泡排序?

假设这里有一个一维数组

int arr1[10]={0,1,2,3,4,5,6,7,8,9};

我们要对他实现降序排列,

arr1[0]与arr[1]进行比较,如果arr1[0]<arr1[1],那么二者交换位置,即arr1[0]=1,arr1[1]=0.否则不交换位置,继续和下一个元素比较.直到它和最后一个元素比较完.
那么整个冒泡排序一共要经历几次呢?
arr1有10个元素,0要和1 2 3 4 5 6 7 8 9比,1要和2 3 4 5 6 7 8 9比,2要和3 4 5 6 7 8 9比...到8 时,它只用和9比,到9时,就不用比较了,因为9已经和所有元素比较过了。因此比较的次数是元素个数-1.
那么元素内要比较几次呢?
根据上述分析,我们可以知道,每到下一个元素时,比较的次数就-1.

以上就是冒泡排序的基本思想了。

那么使用冒泡排序的qsort到底是如何实现不同类型数据的排序的呢?

在qsort(升序版本)原本的定义中,它会获取数组内两个元素e1、e2的地址,并比较它们的大小,倘若e1-e2>0,那么就会交换e1,e2的值.

这是qsort的参数

 
模仿qsort创建自己的函数
void my_qsort(void* base, size_t sz, size_t width, int(*cmp)(const void* e1, const void* e2))
void* base是用来接受被比较数组的地址的
size_t sz是接受数组元素个数的
int(*cmp)(const void* e1,const void* e2)是用来接受函数指针的
接着是各函数的构建
void swap(char* e1, char* e2,int width)
{
    int i = 0;
    for (i = 0; i < width; i++)//一个字节一个字节的转换,具体取决于width的大小
    {
        char tmp = 0;
        tmp = *e2;
        *e2 = *e1;
        *e1 = tmp;
        e1++;
        e2++;
    }
}
int cmp_int(const void* e1, const void* e2)//这实际上是一个回调函数,my_qsort函数通过调用这个函数,得到一个返回值,再通过这个返回值进行判断是否交换数值
{
    return (*(int*)e1) - (*(int*)e2);
}
int cmp_by_name(const void*e1,const void*e2)
{
    return strcmp((struct stu*)e1,(struct stu*)e2);
    
}
int cmp_by_age(const void* e1, const void* e2)
{
    return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
void my_qsort(void* base, 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-i-1;j++)
{
   if(cmp((char*)base+j*width,(char*)base+(j+1)*width>0))
        //为什么要将转(char*)以及j和width的用处
        //因为我们无法确认传参进来的指针的类型,因此也就无法确定指针+1的步幅
        //通过width,我们可以确认指针+1的步幅,通过j与j+1,可以得出前后相邻的两地址
            {
               swap((char*)base+j*width,(char*)base+(j+1)*width);
            }
}
}
 
 
 
}
int main()
创建几个不同类型的数组,以便待会测试
{
int arr[10]={5,1,2,6,7,3,8,9,10}
struct stu
{
char name[20];
int age;
}
sturct stu s[3]={{"zhangsan",18},{"lisi",19},{"wangmazi",24}};
    int sz = sizeof(s) / sizeof(s[0]);
    my_qsort(s, sz, sizeof(s[0]), cmp_by_name);//测试不同类型的数组只需传递对应函数的地址即可
}


相关文章
SpringBoot入门(8) - 开发中还有哪些常用注解
SpringBoot入门(8) - 开发中还有哪些常用注解
111 0
SQL面试50题------(初始化工作、建立表格)
这篇文章提供了SQL面试中可能会遇到的50道题目的建表和初始化数据的SQL脚本,包括学生、教师、课程和成绩表的创建及数据插入示例。
SQL面试50题------(初始化工作、建立表格)
基于Python flask的豆瓣电影数据分析可视化系统,功能多,LSTM算法+注意力机制实现情感分析,准确率高达85%
本文介绍了一个基于Python Flask框架的豆瓣电影数据分析可视化系统,该系统集成了LSTM算法和注意力机制进行情感分析,准确率高达85%,提供了多样化的数据分析和情感识别功能,旨在帮助用户深入理解电影市场和观众喜好。
383 0
自动化AutoTalk第十期:应知必会的自动化工具-阿里云SDK
本期《自动化AutoTalk》第十期聚焦应知必会的自动化工具——阿里云SDK。主要内容分为三部分:1. 阿里云SDK概述,介绍其支持的300多款云产品和8种主流编程语言;2. 快速生成SDK示例,以Java语言为例展示如何通过OpenAPI门户快速生成并下载SDK工程;3. 进阶特性介绍,涵盖签名算法、Endpoint配置、代理设置、HTTPS请求配置、超时机制及异常处理等重要功能。通过这些内容,帮助开发者更高效、安全地使用阿里云SDK。
182 3
下一代研发大模型需要哪些关键能力?
CodeFuse 支持从设计到运维的整个软件开发生命周期。项目已开源多个项目,欢迎社区共建。其中Rodimus作为 CodeFuse 的重要组成部分,旨在降低推理复杂度,优化大模型性能,支持低资源设备上的高效运行。
157 6
【Java集合类面试九】、介绍一下HashMap的扩容机制
HashMap的扩容机制包括初始容量16,以2的次方进行扩充,使用负载因子0.75判断是否扩容,以及链表长度达到阈值时转换为红黑树,以优化性能。
【Java集合类面试九】、介绍一下HashMap的扩容机制
【分布式流控组件 Sentinel 快速入门】——图文详解操作流程(上)
【分布式流控组件 Sentinel 快速入门】——图文详解操作流程
363 0
【分布式流控组件 Sentinel 快速入门】——图文详解操作流程(上)
解决方案评测|通义万相AI绘画创作获奖名单
通义万相AI绘画创作获奖名单正式发布!
302 1
github Release 下载加速,绿色合法,遥遥领先
你有没有这样一个困惑,当你寻找了很久终于找到一个解决问题的方案,发现这个工具在 GitHub 上,接下来等待我们的就是遥遥无期的龟速下载。
761 0
github Release 下载加速,绿色合法,遥遥领先
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问