有关排序的算法

目录

选择法排序

冒泡法排序

qsort排序(快速排序)

qsort排序整型

qsort排序结构体类型


排序是我们日常生活中比较常见的问题,这里我们来说叨几个排序的算法。

比如有一个一维数组 arr[8] ={2,5,3,1,7,6,4,8},我们想要把它排成升序,我们通过下面这几种不同的方式来进行排序!

选择法排序

这一种排序方式,首先第一轮认为第一个元素是最小的,把它的下标用 flag 记下来,不断与后面的元素进行比较,如果后面的元素有比它小的,就把 flag 改成比它小的元素下标,直到把整个数组下标遍历完,如果flag不等于最开始的下标就进行交换,这样就可以得到最小的那个数在第一位,依此类推,第二轮找到第二小的数字放在第二位,第三轮找到第三小的数字放在第三位……

当第七轮的时候已经找到了找到第七小的数字放在第七位,显然最后一位是最大的数字,所以一共进行七次就好了!

代码如下:

//选择法排序
#include<stdio.h>
int main()
{int arr[8] = { 2,5,3,1,7,6,4,8 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;int j = 0;int flag = 0;printf("排序前:\n");for (i = 0; i < sz; i++){printf("%d ", arr[i]);}for (i = 0; i < sz - 1; i++){flag = i;for (j = i + 1; j < sz; j++){if (arr[j] < arr[flag])flag = j;//如果后面的元素比flag为坐标的元素小,就把flag改成较小元素的坐标}if (flag != i){int temp = arr[i];arr[i] = arr[flag];arr[flag] = temp}}printf("\n排序后:\n");for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

当然,在学习了指针的基础上,我们可以把排序代码分装成函数的形式


#include<stdio.h>
void Print_arr(int* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", arr[i]);
}
void Choose_sort(int* arr, int sz)
{int flag = 0;for (int i = 0; i < sz - 1; i++){flag = i;for (int j = i + 1; j < sz; j++){if (arr[j] < arr[flag])flag = j;}if (flag != i){int temp = arr[i];arr[i] = arr[flag];arr[flag] = temp;}}
}
int main()
{int arr[8] = { 2,5,3,1,7,6,4,8 };int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);Choose_sort(arr, sz);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

冒泡法排序

这个与选择法排序有点相似,它的核⼼思想是两两相邻的元素进⾏⽐较,如果后面的元素比前面小,那么就立刻进行交换,第一轮最终会把最大的元素放在最后一位,依次往后面推进,在第七轮的时候,第二小的就在第二位了,所以只需要7趟就好了,每一趟就会找到一个元素放在相应的位置,所以每一趟比较的数组元素也会依次减1.

代码如下:


//冒泡排序
#include<stdio.h>
int main()
{int arr[8] = { 2,5,3,1,7,6,4,8 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;int j = 0;printf("排序前:\n");for (i = 0; i < sz; i++){printf("%d ", arr[i]);}for (i = 0; i < sz - 1; i++){//i代表趟数for (j = 0 ; j < sz - 1 - i; j++){//访问数组元素两两比较if ( arr[j+1]<arr[j]){int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}		}	}printf("\n排序后:\n");for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

我们也可以把排序代码分装成函数的形式:

#include<stdio.h>
void Print_arr(int* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", arr[i]);
}
void Bubble_sort(int* arr, int sz)
{int i = 0;int j = 0;for (i = 0; i < sz - 1; i++){for (j = 0; j < sz - 1 - i; j++){if (*(arr+j+1) < *(arr+j)){int temp = *(arr + j + 1);*(arr + j + 1) = *(arr + j);*(arr + j) = temp;}/*if (arr[j + 1] < arr[j]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}*/}}
}
int main()
{int arr[8] = { 2,5,3,1,7,6,4,8 };int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);Bubble_sort(arr, sz);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

我们来考虑一个问题,如果一个数组元素已经有序了,事实上,我们可以不用再进行排序了,那么应该怎么优化这个排序代码呢?

#include<stdio.h>
void Print_arr(int* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", arr[i]);
}
void Bubble_sort(int* arr, int sz)
{int i = 0;int j = 0;for (i = 0; i < sz - 1; i++){int flag = 1;//最开始就假设有序for (j = 0; j < sz - 1 - i; j++){if (*(arr + j + 1) < *(arr + j)){flag = 0;//进来就说明还没有有序,让flag=0int temp = *(arr + j + 1);*(arr + j + 1) = *(arr + j);*(arr + j) = temp;}}if (flag == 1)//一趟下来flag=1,说明没有机会让flag=0,已经有序{printf("\n已经有序!\n");break;}}
}
int main()
{int arr[8] = { 1,2,3,4,5,6,7,8 };int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);Bubble_sort(arr, sz);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

这里我们就可以使用一个flag来进行标记,flag=1,就说明已经有序,跳出循环,当一个数组已经已经有序或者接近有序的时候就可以减少运算次数

qsort排序(快速排序)

想要使用qsort函数呢?我们就需要先对这个函数进行一定的了解。

打开cplusplus网站,我们可以找到相关信息:

qsort(quick sort)事实上是C语言中的一个库函数,底层使用的是快速排序的思想,

并且对任意类型数据都可以进行排序

我们来看看每一个参数

base:指向需要排序数组的首元素地址(指针)

num:base指向数组中的元素个数

size:bas指向的数组中一个元素的字节大小

compar:函数指针,传递函数的地址

compar应该设计成下面这个样子,同时它的返回值也有要求

 
int compar (const void* p1, const void* p2);

当p1指向的元素小于p2指向的元素时,返回一个小于0的数字

当p1指向的元素等于p2指向的元素时,返回0

当p1指向的元素大于p2指向的元素时,返回一个大于0的数字

qsort排序整型

//测试qsort排序整型#include<stdio.h>
#include<stdlib.h>
void Print_arr(int* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", arr[i]);
}
int cmp_int(const void* p1, const void* p2)
{if (*(int*)p1 > *(int*)p2){return 1;}//知道比较整型,强制类型转换为整型,然后解引用else if (*(int*)p1 < *(int*)p2){return -1;}else{return 0;}
}
int main()
{int arr[8] = { 2,5,3,1,7,6,4,8 };int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);qsort(arr, sz, sizeof(arr[0]), cmp_int);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

我们可以看见qsort进行了很好的排序,当然这里因为它的规则是

当p1指向的元素小于p2指向的元素时,返回一个小于0的数字

当p1指向的元素等于p2指向的元素时,返回0

当p1指向的元素大于p2指向的元素时,返回一个大于0的数字

所以我们可以把return语句直接写成:

return *((int*)p1) - *((int*)p2);

#include<stdio.h>
#include<stdlib.h>
void Print_arr(int* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%d ", arr[i]);
}
int cmp_int(const void* p1, const void* p2)
{//return *((int*)p1) - *((int*)p2);//默认升序//知道比较整型,强制类型转换为整型,然后解引用return *((int*)p2) - *((int*)p1); // 降序
}
int main()
{int arr[8] = { 2,5,3,1,7,6,4,8 };int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);qsort(arr, sz, sizeof(arr[0]), cmp_int);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

使用qsort默认是升序,如果想要降序,交换p1,p2的位置就可以了,比如上面的代码就可以实现降序。

qsort排序结构体类型

//qsort排序结构体类型
#include<stdio.h>
#include<stdlib.h>//qsort头文件
#include<string.h>//strcmp头文件
struct Student
{char name[20];int age;
};
void Print_arr(struct Student* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%s %d\n", arr[i].name, arr[i].age);
}
int cmp_student_by_name(const void* p1, const void* p2)
{return strcmp(((struct Student*)p1)->name, ((struct Student*)p2)->name);//strcmp比较字符串,比较第一个不同字符的ASCII值
}
int main()
{struct Student arr[3] = { {"lihua",18},{"balla",56},{"guna",23} };//结构体数组int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);qsort(arr, sz, sizeof(arr[0]), cmp_student_by_name);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

这里依然是比较的时候强制类型转换为结构体类型,使用了结构体访问操作符【->】特殊的是比较字符串需要使用strcmp函数,不清楚的可以看看【数组的使用】那一篇博客对strcmp进行详细讲解。

我们也可以通过年龄来比较,代码如下:

#include<stdio.h>
#include<stdlib.h>//qsort头文件
//#include<string.h>//strcmp头文件
struct Student
{char name[20];int age;
};
void Print_arr(struct Student* arr, int sz)
{for (int i = 0; i < sz; i++)printf("%s %d\n", arr[i].name, arr[i].age);
}
int cmp_student_by_age(const void* p1, const void* p2)
{return (((struct Student*)p1)->age - ((struct Student*)p2)->age);
}
int main()
{struct Student arr[3] = { {"lihua",18},{"balla",56},{"guna",23} };//结构体数组int sz = sizeof(arr) / sizeof(arr[0]);printf("排序前:\n");Print_arr(arr, sz);qsort(arr, sz, sizeof(arr[0]), cmp_student_by_age);printf("\n排序后:\n");Print_arr(arr, sz);return 0;
}

当然排序算法永远不止于此,还有更多的内容等待着我们去发现,去应用。

加油吧!未来的顶尖程序员们!!!!

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

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

相关文章

力扣1901.寻找峰值II

力扣1901.寻找峰值II 二分每一行 并用函数找出每一行中最大值的下标若最大值比其下面相邻的元素大 则上方一定存在峰值若最大值比其下面相邻的元素小 则下方一定存在峰值 class Solution {int indexmax(vector<int> &a){return max_element(a.begin(),a.end()) - …

FPGA早鸟课程第二弹 | Vivado 设计静态时序分析和实际约束

在FPGA设计领域&#xff0c;时序约束和静态时序分析是提升系统性能和稳定性的关键。社区推出的「Vivado 设计静态时序分析和实际约束」课程&#xff0c;旨在帮助工程师们掌握先进的设计技术&#xff0c;优化设计流程&#xff0c;提高开发效率。 课程介绍 关于课程 权威认证&…

Spire.PDF for .NET【文档操作】演示:如何删除 PDF 中的图层

借助Spire.PDF&#xff0c;我们可以在新建或现有pdf文档的任意页面中添加线条、图像、字符串、椭圆、矩形、饼图等多种图层。同时&#xff0c;它还支持我们从pdf文档中删除特定图层。 Spire.PDF for .NET 是一款独立 PDF 控件&#xff0c;用于 .NET 程序中创建、编辑和操作 PD…

Redis协议规范简介

Redis客户端使用为名为RESP&#xff08;Redis序列化协议&#xff09;的协议与Redis服务器进行通信。虽然该协议是专门为Redis设计的&#xff0c;但它也可以用于其他的CS软件项目的通信协议。 RESP可以序列化不同的数据类型&#xff0c;如整型&#xff0c;字符串&#xff0c;数…

wsl报错在BIOS中启用虚拟化

解决&#xff1a; Enable-WindowsOptionalFeature -Online -FeatureName Microsoft-Hyper-V -All 以高级管理员身份运行powershell&#xff0c;执行如上命令。

在哪可以查到全网的司法诉讼信息?

司法涉诉信息指的是再司法活动中形成的各种记录和资料&#xff0c;涵盖了诉讼案件的立案&#xff0c;审判&#xff0c;执行等各个环节的记录和文件。比如基本案件信息&#xff0c;开庭信息&#xff0c;审判信息&#xff0c;执行信息等。有时候还会涉及到被执行人&#xff0c;司…

4大利好因素释放顺风车市场潜力,嘀嗒出行即将登陆港交所

经历了十多年发展&#xff0c;共享出行行业即将迎来第一个上市公司——专注顺风车和智慧出租车的嘀嗒出行。 近日&#xff0c;嘀嗒出行通过了港交所聆讯&#xff0c;根据招股书&#xff0c;嘀嗒出行2023年顺风车搭乘次数和交易额分别为约1.3亿次和86亿元&#xff0c;同比分别增…

如何设置antv x6中stencil节点的拖动样式?

问题 在设计自定义地图的时候&#xff0c;用到了antv x6 stencil&#xff0c;但是拖动里面的节点时&#xff0c;里面的文字总是总是显示不全&#xff0c;只有68px&#xff0c;如何把宽度设置宽一点呢&#xff1f; 过程 这个问题折磨了半天&#xff0c;最后仔细看看文档&#…

vue-cli 根据文字生成pdf格式文件 jsPDF

1.安装jspdf npm install jspdf --save 2.下载ttf格式文件 也可以用C:\Windows\Fonts下的字体文件&#xff0c;反正调一个需要的ttf字体文件就行&#xff0c;但有的字体存在部分字体乱码现象 微软雅黑ttf下载地址&#xff1a; FontsMarket.com - Download Microsoft YaHei …

XMLXXE实体注入

XML&XXE实体注入 原理 XML被设计为传输和存储数据&#xff0c;XML文档结构包括XML声明、DTD文档类型定义&#xff08;可选&#xff09;、文档元素&#xff0c;其焦点是数据的内容&#xff0c;其把数据从HTML分离&#xff0c;是独立于软件和硬件的信息传输工具。等同于JSO…

PPP-AR代码解析

本文主要解析函数pppamb&#xff08;&#xff09;&#xff1b; 前面的浮点的基础&#xff0c;可以参考下面的内容&#xff0c;不过解析的不是同一版本代码&#xff0c;逻辑基本一样 RTKLIB中ppp代码解析_rtklib ppp-rtk-CSDN博客 pppamb&#xff08;&#xff09;{ 1、 ave…

位图法-有效的数独

有效的数独&#xff0c;主要是判断每行每列每宫有无重复元素。 每行每列用二重循环&#xff0c;每宫比较复杂&#xff0c;需要考虑每一宫的坐标与二重循环ij对应关系 行i&#xff0c;每一宫3行&#xff0c;3列 x3*(i/3)j/3 y3*(i%3)j%3

如何覆盖!important修饰的属性

最简单的方法 如果这个!important修饰的属性 是自己的写的&#xff0c;去掉这种写法&#xff0c;使用优先级的方式来写这个属性&#xff08;.outter .inner 的优先级就会比 。outter的优先级高&#xff09; 复杂的方法&#xff1a;用魔法打败魔法 但是这个样式来自于全局css&am…

Maven 插件列表详解

Maven 是一个强大的项目管理和构建工具&#xff0c;广泛应用于 Java 项目中。作为一款优秀的构建管理工具&#xff0c;Maven 不仅提供了标准化的项目结构和依赖管理&#xff0c;还通过其丰富的插件系统&#xff0c;极大地扩展了其功能和灵活性。无论是代码编译、测试、打包&…

【NOI-题解】1431. 迷宫的第一条出路

文章目录 一、前言二、问题问题&#xff1a;1431. 迷宫的第一条出路 三、感谢 一、前言 二、问题 问题&#xff1a;1431. 迷宫的第一条出路 类型&#xff1a;深度搜索、回溯、路径打印 题目描述&#xff1a; 已知一 NN 的迷宫&#xff0c;允许往上、下、左、右四个方向行走…

git管理(Linux版本)

在Linux中我们如何把自己的代码上传到gitee中呢&#xff0c;本期将为大家讲解详细的步骤。 目录 查看Linux环境是否存在git工具 在gitee上创建代码仓库 复制仓库的HTTP路径到Linux中 代码上传 在仓库下创建文件或者将文件移动到仓库下 使用三板斧进行文件的上传 add …

网络安全复习笔记

概述 要素 CIA&#xff1a;可用性&#xff1b;完整性&#xff1b;保密性。 可控性&#xff1b;不可否认性&#xff1b;可审查性。 攻击 被动&#xff1a;窃听 - 保密性&#xff1b;监听 - 保密性主动&#xff1a;假冒 - 完整性&#xff1b;重放 - 完整性&#xff1b;改写 -…

2024年6月22日(星期六)骑行谷仓坝

2024年6月22日 (星期六) 骑行谷仓坝&#xff0c;早8:00到8:30&#xff0c; 龙泉小学门口(北京路尽头&#xff0c;高架桥下&#xff09;&#xff0c;9:00准时出发 【因迟到者&#xff0c;骑行速度快者&#xff0c;可自行追赶偶遇。】 偶遇地点:集合 &#xff0c;家住东&#xf…

phpStudy安装sqli-labs

phpStudy安装sqli-labs git地址&#xff1a;https://github.com/Audi-1/sqli-labs 点击管理–>根目录 将git下载的sqli-labs文件放进去并解压 进入sql-connections修改 修改db-creds.inc文件为自己数据库的账号密码 更改php版本为5.*&#xff0c;因为这个程序只能在php 5.…

《庆余年》在前,《玫瑰的故事》在后,阅文发现“新大陆”?

奋笔疾书的网文作家&#xff0c;即将迎来网络文学的高光时代。 近日&#xff0c;阅文集团于安徽省举办2024阅文创作大会。现场数据显示&#xff0c;2023年阅文活跃作家平均收入增长32%&#xff0c;创造近五年最大增幅。其中&#xff0c;中位数作家收入增幅达135%&#xff0c;已…