当前位置: 首页 > news >正文

【算法】(C语言):快速排序(递归)、归并排序(递归)、希尔排序

快速排序(递归) 

  1. 左指针指向第一个数据,右指针指向最后一个数据。取第一个数据作为中间值。
  2. 右指针指向的数据 循环与中间值比对,若大于中间值,右指针往左移动一位,若小于中间值,右指针停住。右指针指向的数据放入左指针指向的位置。
  3. 左指针指向的数据 循环与中间值比对,若小于中间值,左指针往右移动一位,若大于中间值,左指针停住。左指针指向的数据放入右指针指向的位置。
  4. 重复2和3,直到左指针和右指针指向同一个位置pos,则中间值放入该位置pos。
  5. 从中间值所在位置pos将数据分成左边和右边两部分。左边数值都比中间值小,右边数值都比中间值大。
  6. 重复1-5,直到左边或右边只有一个数据。到此排序完成。

(注:左指针指向的数据始终比中间值小,右指针指向的数据始终比中间值大。)

时间复杂度:最好情况 O(nlogn),最坏情况 O(n^{2}),平均情况 O(nlogn)

  • 左右指针依次从头或从尾与中间值比对,一轮比对约n次。
  • 若每次取的中间值正好是中间位置的数据,每次都是对半拆分,拆分层级logn,则所有数据需约logn轮的比对,总时间 约 O(nlogn)。
  • 若已经排好序了,则每次取的中间值都是最小或最大值,则每次都是依次从下一位数据重新开始,类似斜树,最坏时间约  O(n^{2})。

空间复杂度:最好情况  O(logn),最坏情况 O(n)。

  • 在原位置排序,使用栈作为辅助空间。每次递归,中间值入栈,递归结束,中间值出栈。
  • 若最好情况,拆分层级logn,最多logn个中间值在栈中,则即空间使用 O(logn)。
  • 若最坏情况,则递归n次,即空间使用约  O(n)。


C语言实现:(quicksort.c)

#include <stdio.h>/* function prototype */
void quicksort(int *, int, int);	// quick sort (recursion)
void traverse(int *, int);		// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);quicksort(arr, 0, n - 1);printf("[ after quick sort ] ");traverse(arr, n);return 0;
}
/* subfunction */
void quicksort(int *array, int start, int end)		// quick sort (recursion)
{if(start >= end) return ;int low = start, high = end;int middata = array[low];	// the first element as middle datawhile(low < high){// right side, data is bigger than middle data.High index move a step to left  while(low < high && array[high] >= middata) high--;// right side, if data is smaller than middle data, data change to low index  array[low] = array[high];// left side, data is smaller than middle data.Low index move a step to rightwhile(low < high && array[low] < middata) low++;// left side, if data is bigger than middle data, data change to high indexarray[high] = array[low];}// the middle data in the correct positionarray[low] = middata;// from the position of the middle data, split to two sidesquicksort(array, start, low  - 1);quicksort(array, low + 1, end);
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接: gcc -o quicksort quicksort.c

执行可执行文件: ./quicksort



归并排序(递归)

  1. 从中间位置,将数据拆分成左右两部分。再分别将左右两部分从各自中间位置再拆分成左右两部分。直到左边或右边只有一个元素。
  2. 将最多只有一个元素的左右两边,排序合并在一起。
  3. 将排好序的左右两边,排序合并在一起。
  4. 重复3,直到全部排好序。

时间复杂度:最好情况 O(nlogn),最坏情况 O(nlogn),平均情况 O(nlogn)

  • 每次对半拆分,拆分层级logn,所有数据都需要比对 进行重新排序合并,一轮比对合并约n次,共约logn轮,则总时间约 nlogn,即 O(nlogn)。

空间复杂度:O(n)

  • 有多少数据,就需要多少额外的空间存储 已排好序的数据,即 O(n)。


C语言实现:(mergesort.c)

#include <stdio.h>
#include <math.h>/* function prototype */
void mergesort(int *, int, int);	// merge sort (recursion)
void traverse(int *, int);		// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);mergesort(arr, 0, n - 1);printf("[ after merge sort ] ");traverse(arr, n);return 0;
}
/* subfunction */
void mergesort(int *array, int start, int end)		// merge sort (recursion)
{if(start >= end) return ;// from the middle, split the array to the left side and the right sideint mid = start + ceil((end - start) / 2);mergesort(array, start, mid);mergesort(array, mid + 1, end);// merge the left and right, sort to the new arrayint tmparr[end - start + 1];int i = start, j = mid + 1;for(int k = 0; k <= end - start; k++){// the right side is over or left data < right data, copy the left dataif(j > end || (i <= mid && array[i] < array[j])){tmparr[k] = array[i];i++;}// the left side is over or left data >= right data, copy the right dataelse{tmparr[k] = array[j];j++;}}// elements in the new array copy to the original arrayfor(int i = start, k = 0; i <= end; i++, k++){array[i] = tmparr[k];}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接: gcc -o mergesort mergesort.c

执行可执行文件: ./mergesort



希尔排序

  1. 取一定间隔(开始一般为数据量的一半),将数据分为多个组,每个组分别排序。
  2. 将间隔减半,数据分为多个组,每个组分别排序。
  3. 重复2,直到间隔为1,完成最后的排序。

时间复杂度:O(n^{1.3}) - O(n^{2})

  • 插入排序的升级。先根据大间隔,按组进行插入排序,再依次减小间隔,按组进行插入排序。
  • n^{2}快,但比nlogn慢。

空间复杂度:O(1)

  • 在原位置排序,只重复使用了用于交换的临时空间,不随数据量的变动而变动,空间使用为常量(1)。


C语言实现:(shellsort.c)

#include <stdio.h>
#include <math.h>/* function prototype */
void shellsort(int *, int);			// shell sort
void traverse(int *, int);			// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);shellsort(arr, n);printf("[ after shell sort ] ");traverse(arr, n);return 0;
}
/* subfunction */
void shellsort(int *array, int length)		// shell sort
{int gap = ceil(length / 2);	// steps of two comparative datawhile(gap > 0){// from gap to the end, each element compare with data before gap stepsfor(int i = gap; i < length; i++){// element cycle compare with data before gap steps, until 0 indexfor(int j = i; j >= gap; j -= gap){if(array[j] < array[j - gap]){int tmp = array[j];array[j] = array[j - gap];array[j - gap] = tmp;}}}// reduce the stepgap  = ceil(gap / 2);}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接: gcc -o shellsort shellsort.c

执行可执行文件: ./shellsort

相关文章:

【算法】(C语言):快速排序(递归)、归并排序(递归)、希尔排序

快速排序&#xff08;递归&#xff09; 左指针指向第一个数据&#xff0c;右指针指向最后一个数据。取第一个数据作为中间值。右指针指向的数据 循环与中间值比对&#xff0c;若大于中间值&#xff0c;右指针往左移动一位&#xff0c;若小于中间值&#xff0c;右指针停住。右…...

模型驱动开发(Model-Driven Development,MDD):提高软件开发效率与一致性的利器

目录 前言1. 模型驱动开发的原理1.1 什么是模型驱动开发1.2 MDD的核心思想 2. 模型驱动开发的优势2.1 提高开发效率2.2 确保代码一致性2.3 促进沟通和协作2.4 方便维护和扩展 3. 实现模型驱动开发的方法3.1 选择合适的建模工具3.1.1 UML3.1.2 BPMN3.1.3 SysML 3.2 建模方法3.2.…...

记录discuz修改用户的主题出售价格

大家好&#xff0c;我是网创有方的站长&#xff0c;今天遇到了需要修改discuz的主题出售价格。特此记录下 方法很简单&#xff1a; 进入用于组-》选择论坛-》批量修改...

WGAN(Wassertein GAN)

WGAN E x ∼ P g [ log ⁡ ( 1 − D ( x ) ) ] E x ∼ P g [ − log ⁡ D ( x ) ] \begin{aligned} & \mathbb{E}_{x \sim P_g}[\log (1-D(x))] \\ & \mathbb{E}_{x \sim P_g}[-\log D(x)] \end{aligned} ​Ex∼Pg​​[log(1−D(x))]Ex∼Pg​​[−logD(x)]​ 原始 GAN …...

Maven基本使用

1. Maven前瞻 Maven官网&#xff1a;https://maven.apache.org/ Maven镜像&#xff1a;https://mvnrepository.com 1.1、Maven是什么 Maven是一个功能强大的项目管理和构建工具&#xff0c;可以帮助开发人员简化Java项目的构建过程。 在Maven中&#xff0c;使用一个名为 pom.…...

在Linux系统中配置GitHub的SSH公钥

在Linux系统中配置GitHub的SSH公钥&#xff0c;可以让您无需频繁输入密码即可与GitHub仓库进行交互&#xff0c;提高工作效率。以下是配置步骤: 第一步&#xff1a; 检查SSH密钥是否存在 首先&#xff0c;检查您的用户目录下的.ssh文件夹中是否已有SSH密钥。打开终端&#xff0…...

小酌消烦暑|人间正清欢

小暑是二十四节气之第十一个节气。暑&#xff0c;是炎热的意思&#xff0c;小暑为小热&#xff0c;还不十分热。小暑虽不是一年中最炎热的时节&#xff0c;但紧接着就是一年中最热的节气大暑&#xff0c;民间有"小暑大暑&#xff0c;上蒸下煮"之说。中国多地自小暑起…...

C语言结构体的相关知识

前言 从0开始记录我的学习历程&#xff0c;我会尽我所能&#xff0c;写出最最大白话的文章&#xff0c;希望能够帮到你&#xff0c;谢谢。 1.结构体类型的概念及定义 1.1、概念&#xff1a; 结构体是一种构造类型的数据结构&#xff0c; 是一种或多种基本类型或构造类型的数…...

RabbitMQ入门教程(精细版二带图)

目录 六 RabbitMQ工作模式 6.1Hello World简单模式 6.1.1 什么是简单模式 6.1.2 RabbitMQ管理界面操作 6.1.3 生产者代码 6.1.4 消费者代码 6.2 Work queues工作队列模式 6.2.1 什么是工作队列模式 6.2.2 RabbitMQ管理界面操作 6.2.3 生产者代码 6.2.4 消费者代码 …...

IO、零拷贝、多路复用、connection、池化

目录 一、IO 模型 二、什么是网络IO 三、什么是零拷贝 四、多路复用 五、java程序、mysql JDBC connection关系 六、connection怎么操作事务 七 、java里面的池化技术 八、线程池7个核心参数 九、线程的状态 一、IO 模型 BIO &#xff1a;同步阻塞io&#xff0c;单线程 内存上下…...

Lua 错误处理

Lua 错误处理 Lua是一种轻量级的编程语言&#xff0c;广泛用于游戏开发、脚本编写和其他应用程序中。在编程过程中&#xff0c;错误处理是一个重要的方面&#xff0c;它可以帮助开发者创建更健壮和可靠的程序。本文将详细介绍Lua中的错误处理机制。 错误类型 在Lua中&#x…...

二刷力扣——单调栈

739. 每日温度 单调栈应该从栈底到栈顶 是递减的。 找下一个更大的 &#xff0c;用递减单调栈&#xff0c;就可以确定在栈里面的每个比当前元素i小的元素&#xff0c;下一个更大的就是这个i&#xff0c;然后弹出并记录&#xff1b;然后当前元素i入栈&#xff0c;仍然满足递减…...

elementPlus-vue3-ts表格单选和双选实现方式

记录在vue3、ts、element-plus环境下表格单选和多选的实现方式 单选 html部分 <el-table...reftaskTableRefselect"selectClick"... ><el-table-column type"selection" width"50" />... </el-table>ts部分 const taskTabl…...

Linux系统中卸载GitLab

在Linux系统中卸载GitLab&#xff0c;主要可以通过包管理器&#xff08;如apt、yum、rpm等&#xff09;来实现&#xff0c;但具体步骤可能会因GitLab的安装方式&#xff08;如使用包管理器安装、从源代码安装、使用Docker等&#xff09;和Linux发行版的不同而有所差异。以下是一…...

基于STM32F407ZG的FreeRTOS移植

1.从FreeRTOS官网中下载源码 2、简单分析FreeRTOS源码目录结构 2.1、简单分析FreeRTOS源码根目录 &#xff08;1&#xff09;Demo&#xff1a;是官方为一些单片机移植FreeRTOS的例程 &#xff08;2&#xff09;License&#xff1a;许可信息 &#xff08;3&#xff09;Sourc…...

【IT领域新生必看】Java编程中的神奇对比:深入理解`equals`与`==`的区别

文章目录 引言什么是操作符&#xff1f;基本数据类型的比较示例&#xff1a; 引用类型的比较示例&#xff1a; 什么是equals方法&#xff1f;equals方法的默认实现示例&#xff1a; 重写equals方法示例&#xff1a; equals与的区别比较内容不同示例&#xff1a; 使用场景不同示…...

WEBHTTP

目录 理解HTTP协议请求流程 1 1 Web基础 2 Hosts文件 1 1 2网页与HTML 2 HTML概述 1 1 3静态网页与动态网页 1.2HTTP协议 1 2 1 HTTP协议概述 1 2 2 HTTP方法 HTTP支持几种不同的请求命令&#xff0c;这些命令被称为HTTP方法(HTTP method 表1一3 HTTP方法 表1&#…...

nodejs 获取客服端ip,以及获取ip一直都是127.0.0.1的问题

一、问题描述 在做登录日志的时候想要获取客户端的ip, 网上查了一下 通过 req.headers[x-forwarded-for] || req.connection.remoteAddress; 获取&#xff0c; 结果获取了之后不管是开发环境&#xff0c;还是生产环境获取到的一直都是 127.0.0.1&#xff0c;这是因为在配置N…...

微软与OpenAI/谷歌与三星的AI交易受欧盟重点关注

近日&#xff0c;欧盟委员会主管竞争事务的副主席玛格丽特维斯塔格(Margrethe Vestager)在一次演讲中透露&#xff0c;欧盟反垄断监管机构将就微软与OpenAI的合作&#xff0c;以及谷歌与三星达成的AI协议寻求更多第三方意见。这意味着微软与 OpenAI、谷歌与三星的 AI 交易及合作…...

微信小程序毕业设计-学生实习与就业管理系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

2.2.2 ASPICE的需求分析

ASPICE的需求分析是汽车软件开发过程中至关重要的一环&#xff0c;它涉及到对需求进行详细分析、验证和确认&#xff0c;以确保软件产品能够满足客户和用户的需求。在ASPICE中&#xff0c;需求分析的关键步骤包括&#xff1a; 需求细化&#xff1a;将从需求收集阶段获得的高层需…...