C语言进阶之冒泡排序

news/2024/7/17 3:06:07

          

                              ✨ 猪巴戒:个人主页✨

               所属专栏:《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


https://www.xjx100.cn/news/3092697.html

相关文章

matlab设置背景颜色

matlab默认的背景颜色是纯白RGB(255,255,255)&#xff0c;纯白太刺眼&#xff0c;看久了&#xff0c;眼睛会酸胀、疼痛&#xff0c;将其改成豆沙绿RGB(205,123,90)&#xff0c;或者给出浅绿色RGB(128,255,255), 颜色就会柔和很多&#xff0c;眼睛感觉更舒适。     下面介绍在…

pygame播放视频并实现音视频同步

一、前言 在我接触pygame时最新的pygame已经不支持movie模块&#xff0c;这就导致在pygame播放视频变成一个问题&#xff0c;网上搜了下解决方案有两个&#xff1a; 一是使用opencv播放视频&#xff0c;再结合pygame.mixer来播放音频 二是使用moviepy播放视频&#xff0c;再…

正则笔记(持续更新)

1. java 正则替换 指定字符及其之前的字符 System.out.println("em_4b6add2cfb415db2".replaceFirst("\\.*._",""));//结果 -> e4b6add2cfb415db22. java 正则替换 指定字符及其之后的字符 String name "name.keyword^1.0" ; St…

sqlmap的使用笔记及示例

sqlmap的使用笔记 文章目录 sqlmap的使用笔记1. 目标2. 脱库2.1. 脱库&#xff08;补充&#xff09; 3. 其他3.1. 其他&#xff08;补充&#xff09; 1. 目标 操作作用必要示例-u指定URL&#xff0c;检测注入点sqlmap -u http://example.com/?id1-m指定txt&#xff0c;里面有…

【secureCRT连接Virtual Box里安装的Utuntu】

先说一下为什么要写这篇文章及一些背景问题介绍&#xff0c;楼主第一次使用secureCRT及securtFX这两个软件&#xff0c;在windows系统下访问虚拟机里面的ubuntu系统。看了网上的不少帖子&#xff0c;没有让我清晰明白地知道怎么使用secureCRT。连接不通&#xff0c;不知道是虚拟…

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

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

XDAG同步节点部署

系统环境要求 JDK : v17 Maven : v3.9.1-v3.9.5 MySQL : v8.0系列 1、MySQL8.0安装 1&#xff09;docker-compose安装详情 MySQL安装 2&#xff09;配置数据库账号密码及键表 # docker exec -it mysql8 /bin/bash # root0286a1fd60e6:/# mysql -uroot -p Enter password:…

【gpts】学算法题[缺失的第一个正数](https://leetcode.cn/problems/first-missing-positive/)

给出你的题解 (https://leetcode.cn/problems/first-missing-positive/) public class Solution { public int firstMissingPositive(int[] nums) {int len nums.length;for (int i 0; i < len; i) {while (nums[i] > 0 && nums[i] < len && nums…