C语言进阶之冒泡排序

          

                              ✨ 猪巴戒:个人主页✨

               所属专栏:《C语言进阶》

        🎈跟着猪巴戒,一起学习C语言🎈

目录

前情回顾

1、回调函数

2、冒泡排序

3、库函数qsort

cmp(sqort中的比较函数,需要我们自定义)

整形的升序排列

整形的倒序排列

结构体的排序

结构体按照名字(char类型)排序

结构体按照年龄(int类型)排序

库函数qsort的模拟实现(bubble_sort)

呈现bubble_sort函数的整体代码:

 bubble_sort的结构体排序

age: 

name:


前情回顾

函数指针

我们有一个函数,为Add,我们将函数的地址用指针来存储,这个指针就叫做函数指针。

int Add(int x,int y)
{
    return x+y;
}

int main()
{
    int (*pf)(int,int) = Add;//pf就是函数指针。
    return 0;
}

函数指针数组

把函数指针放在数组中,就是函数指针的数组。

int Add(int x,int y)
{
    return x+y;
}
int Sub(int x,int y)
{
    return x-y;
}
int Mul(int x,int y)
{
    return x*y;
}
int Div(int x,int y)
{
    return x/y;
}
int main()
{
    int (*arr[4])(int ,int) = {Add,Sub,Mul,Div};//这个就是函数指针数组。
    return 0;
}

0ef772519fa440768e39c8e8e92b995b.png

函数指针数组就可以调用函数:

int main()
{
    int i = 0;
    scanf("%d",&i);
    int ret = arr[i](8,4);
    printf("%d\n",ret);
}

1、回调函数

回调函数就是应该通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数。回调函数不是由这个函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应。

我们可以把Add函数称为回调函数。

int Add(int x,int y)
{
    return x+y;
}
int main()
{
    int (*pf)(int,int) = Add;
    int ret = pf(8,4);
    return 0;
}

2、冒泡排序

对一个数组进行升序排序。

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-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 };
    //把数组排成升序
    int sz = sizeof(arr)/sizeof(arr[0]);
    bubble_sort(arr,sz);
    int i = 0;
    for(i=0;i<sz;i++)
    {
        printf("%d",arr[i]};
    }

这个冒泡排序不够高效,如果我们进行一趟冒泡排序,但是一个数字都没有交换,就说明这个数组已经排序好了,就不用继续排序了,

我们可以通过,在进行这一趟冒泡排序前设定int flag = 1;

如果数字进行了交换,就把flag的值改为0;

没有数字进行交换,那么flag的值还是1;

我们通过判断flag的值看数组是否已经排好序。

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-1-i;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 };
    //把数组排成升序
    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;
}

3、库函数qsort

使用快速排序的思想实现的一个排序函数。

qsort可以排序任何类型的数据

void qsort(void* base,//你要排序的数据的起始位置
           size_t num,//待排序的数据元素的个数
           size_t width,//待排序的数据元素的大小(单位是字节)
           int(* cmp)(const void* e1,const void* e2)//函数指针-比较函数
           );

cmp(sqort中的比较函数,需要我们自定义)

int(* cmp)(const void* e1,const void* e2)中的e1,e2就是我们要比较数据的地址。

在这个比较函数中我们实现不同类型的元素比较

void*是无具体类型的指针,可以接收任何类型的地址

void*是无具体类型的指针,所以不能解引用操作,也不能+-整数

当比较函数返回的是大于0的数字,那么两组数据就会进行交换。

进行整型数据的比较, 这是进行升序排列

int cmp_int(const void* e1,const void* e2)
{
   return (*(int*)e1 - *(int*)e2);
}

整形的升序排列

通过qsort来将数组进行升序排序

//比较两个整形元素
//e1指向一个整形
//e2指向另外一个整形
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1,const void* e2)
{
    return (*(int*)e1 - *(int*)e2);
}
int main()
{
    int arr[] = {9,8,7,6,5,4,3,2,1};
    
    int sz = sizeof(arr) / sizeof(arr[0]);
    
    qsort(arr,sz,sizeof(arr[0]),cmp_int);
    
    int i = 0;
    for(i=0;i<sz;i++)
    {
        printf("%d ",arr[i]);
    }    
    return 0;
}

cmp_int就是回调函数 

整形的倒序排列

当我们需要进行降序排列,只要将e2和e1的顺序倒过来就可以实现

int cmp_int(const void* e1,const void* e2)
{
    return (*(int*)e2 - *(int*)e1);
}

结构体的排序

结构体按照名字(char类型)排序

char类型的数据不能够直接比较,我们用到strcmp进行比较,

库函数strcmp

头文件<string.h>

int strcmp( const char *string1, const char *string2 );

如果string1小于string2,就会返回小于0的数

如果string1等于string2,就会返回0

如果string1大于string2,就会返回大于0的数

#include<stdlib.h>
#include<string.h>
struct Stu
{
    char name[20];
    int age;
};
int cmp_stu_by_name(const void* e1,const void* e2)
{
    return strcmp(((struct Stu*)e1)->name,((struct Stu*)e2)->name);
}
int main()
{
    struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s,sz,sizeof(s[0]),cmp_stu_by_name);
    return 0;
}

cmp_stu_by_name就是回调函数

结构体按照年龄(int类型)排序

#include<stdlib.h>
#include<string.h>
struct Stu
{
    char name[20];
    int age;
};
int cmp_stu_by_age(const void*e1,constvoid* e2)
{
     return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int main()
{
    struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s,sz,sizeof(s[0]),cmp_stu_by_age);
    return 0;
}

库函数qsort的模拟实现(bubble_sort)

如何实现qsort函数?库函数qsort的设计原理是什么?

创建自定义函数实现库函数qsort的功能。

基于qsort实现原理,实现将整形数组升序排列

设计自定义函数bubble_sort,等同于库函数qsort

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

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

base:数据的起始位置,首元素的地址

sz: 数据元素的个数,比较数组的话,就是数组中元素的个数

width:待排序的数据元素的大小(单位是字节),比较整形数组的话,就是4个字节,数组元素占内存的大小

cmp:自定义的比较函数。

 关于bubble_sort的设计细节

这是我们对解决整形数组升序排列问题,也就是冒泡排序,原来的的bubble_sort.

但是我们现在要设计的bubble_sort,需要与qsort有相同的功能(排序任何类型的数据)

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-1-i;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;
        }    
    }
    
}

1.

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

参数void类型可以接收任何类型的数据

2.

判断大小,

原来:数组元素比较大小

现在:比较一种无知类型元素大小,通过比较函数(cmp)来比较,由于我们不知道要比较的元素类型是什么,但是我们要找到每个元素的地址,就通过(char*)base + j * width,

第一个元素的地址就是首元素的地址,

第二个元素的地址就是首元素的地址加上一个元素的字节

width:待排序的数据元素的大小(单位是字节)

在bubble_sort中,cmp((char*)base + j * width, (char*)base + (j + 1) * width)

3.

自定义函数(cmp)的实现,已知我们要比较的是整形元素的大小,和库函数qsort解决整形的升序排列一样

int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

4.

交换元素

 cmp_int的功能

当比较函数返回的是大于0的数字,那么两组数据就会进行交换。

进行整型数据的比较, 这是进行升序排列

在bubble_sort中,当cmp判断>0时

if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)

进行交换

交换函数

我们要找到各个元素我们才能进行比较,所以和cmp函数的实现类似,

我们要传递的参数

Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);

找到了各个元素的地址,也知道元素的大小(字节),就可以进行比较,

一个一个字节进行比较,

Swap函数实现:

void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

 5.

为了函数的高效性,我们把原来的flag的设计保留。

也就是int flag = 1;(假设数组已经排列好)

如果在这一趟的冒泡排序的过程中,数字进行了交换,就把flag的值改为0;

没有数字进行交换,那么flag的值还是1,就可以直接跳出循环;

呈现bubble_sort函数的整体代码:

#include<stdio.h>
void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1;//假设数组是排好序
		//一趟冒泡排序的过程
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	//0 1 2 3 4 5 6 7 8 9
	//把数组排成升序
	int sz = sizeof(arr) / sizeof(arr[0]);
	//bubble_sort(arr, sz);

	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);

	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

e12eca3b78924dceba38b973cb8aff85.png

 bubble_sort的结构体排序

前面有完整的bubble_sort的实现,这里就不把bubble_sort写上了

#include<string.h>
struct Stu 
{
	char name[20];
	int age;
};
int cmp_stu_by_age(const void* e1, const void* e2)
{ 
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int cmp_stu_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct Stu*)e1)->name , ((struct Stu*)e2)->name);
}
void test()
{
	struct Stu s[] = { {"zhangsan", 15}, {"lisi", 30}, {"wangwu", 25} };
	int sz = sizeof(s) / sizeof(s[0]);
	bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	//bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{
	test();
	return 0;
}

age: 

90d276b4d2b4434996091f6029b1cc47.png

name:

f364844a2fa2439c82aef0a529082e32.png

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

c++|内联函数

一、概念 以inline修饰的函数叫做内联函数&#xff0c;编译时c编译器会在调用函数的地方展开&#xff0c;而不会建立栈帧&#xff0c;提升了程序运行的效率 例子&#xff1a; #include <iostream> using namespace std;int Add(int left, int right) {return left - ri…

详解硬盘的接口、总线和协议

总线&#xff1a;总线是计算机系统中用于连接各个硬件组件的一种通信方式&#xff0c;它可以实现数据、地址和控制信号的传输。在服务器中&#xff0c;内部总线起着承载数据和控制信号的重要作用。总线在单位时间内能传输数据量称为带宽。分为SATA&#xff0c;SAS&#xff0c;P…

Deep Learning for Monocular Depth Estimation: A Review.基于深度学习的深度估计

传统的深度估计方法通常是使用双目相机&#xff0c;计算两个2D图像的视差&#xff0c;然后通过立体匹配和三角剖分得到深度图。然而&#xff0c;双目深度估计方法至少需要两个固定的摄像机&#xff0c;当场景的纹理较少或者没有纹理的时候&#xff0c;很难从图像中捕捉足够的特…

模电 01

一.半导体基本知识 1.优点&#xff1a;体积小、重量轻、使用寿命长、输入功率小、功率转换效率高。 2.性能介于导体与绝缘体 3.常用半导体材料&#xff1a;硅&#xff08;SI&#xff09; 镉&#xff08;Ge&#xff09;,化合物半导体&#xff1a;砷化镓&#xff08;GaAs&…

centos安装kingbase(人大进仓)数据库

一、kingbase官网 https://www.kingbase.com.cn/rjcxxz/index.htm二、官网获取安装镜像文件和licence 三、安装步骤 1、创建新用户kingbase及其同名分组,以及家目录,并设置密码 useradd -m -U kingbase passwd kingbase2、创建自定义安装路径 su root mkdir -p /opt/Kingba…

Nacos介绍与使用

Nacos介绍与使用 文章目录 Nacos介绍与使用一. 什么是Nacos1 Nacos功能1.1 配置中心1.2 注册中心 2.为什么要使用Nacos 二.Nacos 部署安装1. Nacos 部署方式2. Nacos 安装3. 配置数据源4. 开启控制台授权登录&#xff08;可选&#xff09; 三. Nacos配置中心的使用1. 创建配置信…

暴力求解欲哭无泪之保安问题

身为程序员哪一个瞬间让你最奔溃&#xff1f; > 提醒&#xff1a;在发布作品前&#xff0c;请把不需要的内容删掉。 方向一&#xff1a;身为程序员遇到过的奔溃瞬间 写题目想到第一个方法便是暴力求解,然后少情况 题目如下: 方向二&#xff1a;如何解决遇到的奔溃瞬间 不…

[Docker]八.Docker 容器跨主机通讯

一.跨主机通讯原理 在主机192.168.31.140上的docker0(172.17.0.0/16)中有一个容器mycentos( 172.17.0.2/16), 在主机192.168.31.81上的docker0(172.17.0.0/16)中有一个容器mycentos( 172.17.0.2/16),然后在主机192.168.31.140上ping主机192.168.31.81,发现ping不通要实现两个主…

数字化转型导师坚鹏:数字化时代银行网点厅堂营销5大特点分析

数字化时代银行网点厅堂营销存在以下5大特点&#xff1a; 1、产品多样化&#xff1a;在数字化时代&#xff0c;银行的产品和服务变得更加多样化。除了传统的存款、贷款、理财等金融服务外&#xff0c;还新增了各种创新产品&#xff0c;如网上银行、移动支付、投资咨询、保险、…

C++刷题 -- 二分查找

C刷题 – 二分查找 文章目录 C刷题 -- 二分查找一、原理二、例题1.二分查找2.使用二分查找确定target左右边界3.x的平方根 一、原理 条件&#xff1a;数组为有序数组&#xff0c;数组中无重复元素&#xff0c;因为一旦有重复元素&#xff0c;使用二分查找法返回的元素下标可能…

Hibernate 一级缓存,二级缓存,查询缓存

概念&#xff1a; 1.什么是缓存呢&#xff1f; 缓存&#xff1a;是计算机领域的概念&#xff0c;它介于应用程序和永久性数据存储源之间。 缓存&#xff1a;一般人的理解是在内存中的一块空间&#xff0c;可以将二级缓存配置到硬盘。用白话来说&#xff0c;就是一个存储数据的…

问题 R: 胜利大逃亡(HUST)

#include <deque> #define inf 200000 #include<iostream> #include<queue> using namespace std;// 迷宫坐标 int map[59][59][59] { 0 };// 可访问标记 int visit[51][51][51] { 0 }; // 移动方式 int next1[7][4] { {1,0,0},{-1,0,0}, {0,1,0},{0,-1,…

gitlab安装配置及应用

安装 ##安装依赖 yum install -y curl policycoreutils-python openssh-server perl#上传包 rz gitlab-jh-16.5.2-jh.0.el7.x86_64.rpm 安装 yum install gitlab-jh-16.0.3-jh.0.el7.x86_64.rpm 初始化并启动 # 以下两种方法都可以配置访问地址&#xff0c;第一种需要在yum安…

千字文||无聊又数了一下千字文字数

千字文的字数去除标点符号真的整整一千个不多的不少 该文章无技术含量&#xff0c;仅三字经原文&#xff0c;学技术的同学可以止步了 千字文&#xff08;原文&#xff09; 【作者】周兴嗣 【朝代】南北朝 天地玄黄&#xff0c;宇宙洪荒。 日月盈昃&#xff0c;辰宿列张。 寒来…

【LeetCode】104. 二叉树的最大深度

104. 二叉树的最大深度 难度&#xff1a;简单 题目 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 …

Spring框架学习 -- 创建与使用

目录 (1) 创建spring 项目 ① 创建maven项目 ②添加spring框架支持 ③ 添加启动项 (2) 创建 Bean对象 (3) 将Bean注入到容器 (4) 获取Bean对象 (5) 注意事项 (6) Spring的创建和使用流程图 创作不易多多支持 (1) 创建spring 项目 首先我们使用的开发工具为idea 专业版…

渲染器——双端Diff算法

简单 Diff 算法利用虚拟节点的 key 属性&#xff0c;尽可能地复用 DOM 元素&#xff0c;并通过移动 DOM 的方式来完成更新&#xff0c;从而减少不断地创建和销毁DOM 元素带来的性能开销。但是&#xff0c;简单 Diff 算法仍然存在很多缺陷&#xff0c;这些缺陷可以通过双端 Diff…

[userfaultfd] 2019-BalsnCTF_KrazyNote

前言 题目不算难, 但是这代码逆向可逆死个人:) 悲悲悲 程序分析 内核版本: v5.1.9 保护: 开了 kaslr, smep, smap. 现在的题目基本都开了, 都不用看. 其中 note 模块中注册了一个 misc 设备, 其函数表中就只有 note_open 和 note_unlocked_ioctl 两个函数, 其中 note_open…

GAMES101—Lec 05~06:光栅化

目录 概念回顾&#xff08;个人理解&#xff09;光栅化1.采样2.采样出现的问题&#xff1a;走样 反走样 概念回顾&#xff08;个人理解&#xff09; 屏幕&#xff1a;在图形学中&#xff0c;我们认为屏幕是一个二维数组&#xff0c;数组里的每一个元素为一个二维像素。 光栅化…