经常使用的排序算法
一、直接插入排序
#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,使用流程总结 整理和测试花了很大时间,如果对你有…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...