经常使用的排序算法
一、直接插入排序
#include <stdio.h>void insert_sort(int arr[], int n){int i, j, tmp;for (i = 1; i < n; i++){tmp = arr[i];j = i - 1;while (j >= 0 && arr[j] > tmp){ // 将要插入的元素与数组中的元素比较(从后向前比)arr[j + 1] = arr[j]; // 将排列好的数组后移j--;}arr[j + 1] = tmp; // 不满足以上条件,即待插入元素tmp比数组中的某个元素大,插在它后面}
}int main(){int arr[] = {5, 2, 8, 9, 1, 3};int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}insert_sort(arr, n);printf("\nAfter sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}
arr是待排序的数组,n是数组的长度。算法从数组的第二个元素开始遍历,将当前元素存储到临时变量tmp中,并将j初始化为已排序序列的最后位置。然后,算法通过比较tmp和已排序序列中的元素,找到合适的插入位置,并将大于tmp的元素往后移动一位。最后,将tmp插入到合适的位置。
插入排序算法的时间复杂度为O(n^2),不适用于大规模数据排序。但对于小规模或基本有序的数据,插入排序是一种高效的排序算法。
以上的排序是升序排序,你能把它改成降序排序吗? >>> 把tmp<arr[j]改为tmp>arr[j]即可
二、选择排序
#include <stdio.h>void select_sort(int arr[], int n){int i, j, min_idx, tmp;for (i = 0; i < n - 1; i++){min_idx = i;// 查找最小元素的索引for (j = i + 1; j < n; j++){if (arr[j] < arr[min_idx]){min_idx = j;}}// 将最小元素与当前位置交换tmp = arr[i];arr[i] = arr[min_idx];arr[min_idx] = tmp;}
}int main(){int arr[] = {5, 2, 8, 9, 1, 3};int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}selection_sort(arr, n);printf("\nAfter sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}
三、冒泡排序
#include <stdio.h>void bubble_sort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {// 标志位,用于判断是否发生了交换操作int flag = 0;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j+1]) {// 交换位置int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;flag = 1;}}// 如果没有发生交换操作,说明列表已经有序,提前结束排序if (flag == 0) {break;}}
}int main() {int nums[] = {5, 2, 8, 12, 3};int n = sizeof(nums) / sizeof(nums[0]);bubble_sort(nums, n);for (int i = 0; i < n; i++) {printf("%d ", nums[i]);}return 0;
}
四、希尔排序
#include <stdio.h>// 希尔排序函数
void shell_sort(int arr[], int n) {int gap, i, j, temp;for (gap = n / 2; gap > 0; gap /= 2) { // 用来选取间隔// 内部循环采用的是插入排序for (i = gap; i < n; i++) {temp = arr[i];for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}// 测试希尔排序
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组:\n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}shell_sort(arr, n);printf("\n排序后的数组:\n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}
希尔排序的性能取决于增量序列的选择。通过使用更优化的增量序列,可以进一步提高希尔排序的性能。需要注意的是,希尔排序并不是稳定的排序算法。
五、快速排序
#include <stdio.h>void quickSort(int arr[], int low, int high) {if (low < high) {// 将数组分为两部分并获取分割点int pivot = partition(arr, low, high);// 递归对左侧子数组排序quickSort(arr, low, pivot - 1);// 递归对右侧子数组排序quickSort(arr, pivot + 1, high);}
}int partition(int arr[], int low, int high) {// 取最后一个元素作为分割点int pivot = arr[high];int i = low;for (int j = low; j < high; j++) {if (arr[j] < pivot) {// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++;}}// 交换 arr[i] 和 arr[high]int temp = arr[i];arr[i] = arr[high];arr[high] = temp;return i;
}int main() {int arr[] = {10, 80, 30, 90, 40, 50, 70};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("Sorted array: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;
}
在快速排序算法中,有两个关键的函数:quickSort()
和 partition()
。
quickSort()
函数是快速排序算法的入口函数,它接受一个数组、起始索引 low
和结束索引 high
作为参数。该函数通过递归调用自身来实现对数组的排序。具体过程如下:
- 如果
low
小于high
,意味着仍然存在待排序的子数组。 - 调用
partition()
函数将数组分割为两部分,并获取分割点pivot
。 - 递归调用
quickSort()
函数对左侧子数组进行排序(起始索引为low
,结束索引为pivot - 1
)。 - 递归调用
quickSort()
函数对右侧子数组进行排序(起始索引为pivot + 1
,结束索引为high
)。
partition()
函数用于确定分割点,并将数组分割为左右两部分。具体过程如下:
- 选择数组的最后一个元素
arr[high]
作为分割点pivot
。 - 初始化索引
i
为low
。 - 使用索引
j
遍历数组元素,从low
到high - 1
。 - 如果
arr[j]
小于pivot
,则交换arr[i]
和arr[j]
的值,并将i
加1。 - 遍历结束后,交换
arr[i]
和arr[high]
的值。 - 返回
i
作为新的分割点。
快速排序算法通过不断选择分割点,并递归处理左右两部分,最终完成整个数组的排序。
六、c语言库stdlib中自带的qsort
#include <stdio.h>
#include <stdlib.h>// 比较函数,用于qsort排序
int compare(const void *a, const void *b) {return *(int *)a - *(int *)b;
}int main() {int arr[] = {9, 5, 7, 3, 1};int size = sizeof(arr) / sizeof(int);printf("Before sorting:");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}qsort(arr, size, sizeof(int), compare);printf("\n After sorting: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}return 0;
}
功能:进行排序
函数原型:void qsort(void *base, size_t nitems, size_t size, int (*compare)(const void , const void))
参数:
base - 指向要排序的数组的第一个元素的指针。
nitems - 由 base 指向的数组中元素的个数。
size - 数组中每个元素的大小,以字节为单位。
compare - 用来比较两个元素的函数。(自定义)
制作不易,希望大家多多点赞评论支持。
相关文章:
经常使用的排序算法
一、直接插入排序 #include <stdio.h>void insert_sort(int arr[], int n){int i, j, tmp;for (i 1; i < n; i){tmp arr[i];j i - 1;while (j > 0 && arr[j] > tmp){ // 将要插入的元素与数组中的元素比较(从后向前比)arr[j …...

msyql 24day 数据库主从 主从复制 读写分离 master slave 有数据如何增加
目录 环境介绍读写分离纵向扩展横向扩展 数据库主从准备环境主库环境(master)从库配置(slave)状态分析重新配置问题分析 报错解决从库验证 有数据的情况下 去做主从清理环境环境准备数据库中的锁的机制主库配置从库配置最后给主库解锁常见错误 环境介绍 将一个数据库的数据 复…...

使用 Taro 开发鸿蒙原生应用 —— 探秘适配鸿蒙 ArkTS 的工作原理
背景 在上一篇文章中,我们已经了解到华为即将发布的鸿蒙操作系统纯血版本——鸿蒙 Next,以及各个互联网厂商开展鸿蒙应用开发的消息。其中,Taro作为一个重要的前端开发框架,也积极适配鸿蒙的新一代语言框架 —— ArkTS。 本文将…...
Linux下 自定义多线程并发快速压缩解压缩脚本
文章目录 自定义多线程压缩解压缩脚本使用 Linux下 自定义多线程并发快速压缩解压缩脚本 Linux下常用的tar工具无法支持并行 压缩和解压,对于大量小文件的解压缩,可借助pigz工具实现多线程并行工作,实现更为高效的压缩和解压缩。 自定义多线…...

ubuntu20.04下安装pcl_ubuntu安装pcl
pcl点云数据库,用来进行3D信息的获取与处理,和opencv相比较,opencv是用来处理二维信息,他是学术界与工业界针对点云最全的库,且网络上相关的资料很多。以下是pcl的安装步骤以及遇到的问题。 提前说明,本人…...
阿里云常用配置:日志采集、OSS、RAM 权限策略
文章目录 引言I 日志采集1.1 具体查询语法1.2 查询示例1.3 设置token时间(登录过期时间)II OSS2.1 设置防盗链2.2 验证Referer防盗链是否生效III 通义灵码 (智能编码)IV RAM 权限策略4.1 短信策略4.2 内容风险检测引言 SLS I 日志采集...

回顾丨2023 SpeechHome 第三届语音技术研讨会
下面是整体会议的内容回顾: 18日线上直播回顾 18日上午9:30,AISHELL & SpeechHome CEO卜辉宣布研讨会开始,并简要介绍本次研讨会的筹备情况以及报告内容。随后,CCF语音对话与听觉专委会副主任、清华大学教授郑方,…...

【flink】状态清理策略(TTL)
flink的keyed state是有有效期(TTL)的,使用和说明在官网描述的篇幅也比较多,对于三种清理策略没有进行横向对比得很清晰。 全量快照清理(FULL_STATE_SCAN_SNAPSHOT)增量清理(INCREMENTAL_CLEANUP)rocksdb压缩清理(ROCKSDB_COMPACTION_FILTER) 注意&…...

4. 行为模式 - 中介者模式
亦称: 调解人、控制器、Intermediary、Controller、Mediator 意图 中介者模式是一种行为设计模式, 能让你减少对象之间混乱无序的依赖关系。 该模式会限制对象之间的直接交互, 迫使它们通过一个中介者对象进行合作。 问题 假如你有一个创建…...

2015年第四届数学建模国际赛小美赛A题飞机上的细长座椅解题全过程文档及程序
2015年第四届数学建模国际赛小美赛 A题 飞机上的细长座椅 原题再现: 航空公司座位是指在旅途中乘客可以乘坐的座位。一些航空公司现在推出了新的经济舱“超薄”座位。这些座椅除了重量较轻外,理论上还允许航空公司在不显著影响乘客舒适度的情况下增加运…...
机器学习笔记(二)使用paddlepaddle,再探波士顿房价预测
目标 用paddlepaddle来重写之前那个手写的梯度下降方案,简化内容 流程 实际上就做了几个事: 数据准备:将一个批次的数据先转换成nparray格式,再转换成Tensor格式前向计算:将一个批次的样本数据灌入网络中ÿ…...

【Linux】权限篇(二)
权限目录 1. 前言2. 权限2.1 修改权限2.2 有无权限的对比2.3 另外一个修改权限的方法2.3.1 更改用户角色2.3.2 修改文件权限属性 3. 第一个属性列4. 目录权限5. 默认权限 1. 前言 在之前的一篇博客中分享了关于权限的一些知识,这次紧接上次的进行,有需要…...
reduce累加器的应用
有如下json数据,需要统计Status的值为0和1的数量 const data {"code": "001","results": [{"Status": "0",},{"Status": "0",},{"Status": "1",}] }方法一:用reduce方…...

助力硬件测试工程师之EMC项目测试。
1:更新该系列的目的 接下来的一个月内,将更新硬件测试工程师的其中测试项目--EMC项目,后续将会出安规等项目,助力测试工程师的学习。 2:如何高效率的展现项目的基础以及一些细节知识点 通过思维导图以及标准的规定进行…...

Github 2023-12-23 开源项目日报 Top10
根据Github Trendings的统计,今日(2023-12-23统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目6C项目2C项目1Jupyter Notebook项目1HTML项目1Go项目1非开发语言项目1 免费API集体清单 创建周期…...
Quartz.net 正则表达式触发器
1、创建项目 项目类型控制台应用程序,.Net Framework框架版本 4.7.2 2、引入框架 NuGet\Install-Package Quartz -Version 3.8.0 3、创建Job 自定义Job实现接口IJob,在Execute方法实现定时逻辑, using Quartz; using System; using Sys…...

【已解决】修改了网站的class样式name值,会影响SEO,搜索引擎抓取网站及排名吗?
问题: 修改了网站的class样式name值,会影响搜索引擎抓取网站及排名吗? 解答: 如果你仅仅修改了网站class样式的名称,而没有改变网站的结构和内容,那么搜索引擎通常不会因此而影响它对网站的抓取和排名。但…...

微信小程序开发系列-02注册小程序
上一篇文章,创建了一个最小的小程序,但是,还有3个疑问没有弄清楚,还是基于demo1工程,这篇文章继续探索。 当前的目录结构是否是完备的呢?(虽然小程序可以运行起来)app.js文件内容还…...

安装 PyCharm 2021.1 保姆级教程
作者:billy 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 前言 目前能下载到的最新版本是 PyCharm 2021.1。 请注意对应 Python 的版本: Python 2: 2.7Python 3: >3.6, <3.11…...

浏览器 cookie 的原理(详)
目录 1,cookie 的出现2,cookie 的组成浏览器自动发送 cookie 的条件 3,设置 cookie3.1,服务端设置3.1,客户端设置3.3,删除 cookie 4,使用流程总结 整理和测试花了很大时间,如果对你有…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...