当前位置: 首页 > 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毕业设计…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...