本地资讯网站做的最好的/seo排名优化推广报价
文章目录
- 一、归并排序
- 1、概念
- 2、过程
- 3、代码实现
- 4、复杂度
- 5、稳定性
- 二、 计数排序
- 1、思路
- 2、代码实现
- 3、复杂度:
- 4、稳定性
一、归并排序
1、概念
是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
2、过程
假设前提:
左半区间 ->有序
右半区间 ->有序
怎么使左右排序呢?
当只剩下一个元素时我们可以默认其为有序的,所以我们可以利用递归将数组中的元素划分为一个,再两组两组合并,以此类推。
归并,依次对比取小的放到新到临时数组中,完成排序后再将临时数组的数据拷贝回原来的数组
过程图:
3、代码实现
递归:
void Print(int* arr, int n) {for (int i = 0; i < n; i++)printf("%d ", arr[i]);
}
//递归void _MergeSort(int *a,int *t,int left,int right) {//结束条件if (left >= right)return;int mid = (left + right) >> 1;//取中间数,划分区间//[left mid] [mid+1 right]//递归_MergeSort(a, t, left, mid);_MergeSort(a, t, mid + 1, right);//回归int begin1 = left, end1 = mid;//左区间int begin2 = mid + 1 , end2 = right;//右区间//临时数组下标->对应的是数组a的下标int index = left;//当左区间或者右区间,遍历完了就结束了while (begin1 <= end1 && begin2 <= end2) {//选择小的放进临时数组if (a[begin1] < a[begin2])t[index++] = a[begin1++];elset[index++] = a[begin2++];}//判断左右两边是否都空了,不为空将后面补上while (begin1 <= end1)t[index++] = a[begin1++];while (begin2 <= end2)t[index++] = a[begin2++];//最后拷贝回去for (int i = left; i <= right; ++i)a[i] = t[i];}
void MergeSort(int* a, int n) {int* t = (int*)malloc(sizeof(int) * n);_MergeSort(a, t, 0, n - 1);free(t);
}int main() {int a[] = { 3,7,1,0,9,6,2,3,8,5 };MergeSort(a, sizeof(a) / sizeof(a[0]));Print(a, sizeof(a) / sizeof(a[0]));return 0;
}
递归图(左边,先递后归):
非递归:
我们通过循环来实现非递归
(1)设置一个gap来划分归并个数,先设置gap=1,这样控制第一次是两个数合并,gap再乘2,来递增,当 gap>n(数组大小)时结束
(2)在合并的过程中可能出现两种情况
a.合并过程中右边没元素
如:
解决办法:因为已经排好了,直接打破循环即可
b,右边有元素但是不够
如:
解决办法:进行纠正,将右端的下标改为 n-1(数组大小-1)
代码实现:
//非递归void MergeSortNonR(int* a, int* t,int n) {int gap= 1;//划分一次归并多少个元素//结束条件while (gap<n) {for (int i = 0; i < n; i += 2*gap) {//通过gap划分区间int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;//情况a,此时直接打破即可if (begin2 >= n)break;//情况b,进行纠正if (end2 >= n)end2 = n - 1;int index = i;//从控制的区间最小的位置开始//下面过程与递归过程一样while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2])t[index++] = a[begin1++];elset[index++] = a[begin2++];}while (begin1 <= end1)t[index++] = a[begin1++];while (begin2 <= end2)t[index++] = a[begin2++];for (int j = i; j <= end2; j++)a[j] = t[j];}gap *= 2;//每次加倍}
}void MergeSort(int* a, int n) {int* t = (int*)malloc(sizeof(int) * n);MergeSortNonR(a, t, n);free(t);
}int main() {int a[] = { 6,3,7,1,9,5,2,8,0,4 };MergeSort(a, sizeof(a) / sizeof(a[0]));Print(a, sizeof(a) / sizeof(a[0]));return 0;
}
4、复杂度
时间复杂度:
(1)循环部分:N
(2)递归部分:因为每次都减半所以就是logN(以2为底)
所以时间复杂度为:O(N*logN)
空间复杂度:
因为要重新开辟一个数组,所以空间复杂度为O(N)
5、稳定性
在归并过程中相同的元素的顺序不会发生改变,所以是稳定的
二、 计数排序
1、思路
通过映射统计每个数出现的次数,再使用次数排序
如:
上述是以最大数去创建空间
但是如果遇到一个很大的数的话就需要我们创建空间时就会很浪费
如:
解决:找到范围,使用范围+1去创建临时空间
2、代码实现
//计数排序
void CountSort(int* a, int n) {int max = a[0];int min = a[0];//求出数组的范围for (int i = 0; i < n; i++) {if (max < a[i])max = a[i];if (min > a[i])min = a[i];}int t = max - min+1;//临时空间int* p = (int*)calloc(t,sizeof(int));//统计个数for (int j = 0; j < n; j++) {//a[j]-min当下标,我们下次直接加回min即可p[a[j] - min]++;}int i = 0;//按顺序拷贝回原来的数组for (int j = 0; j < t; j++) {while (p[j]) {a[i] = j + min;i++;p[j]--;}}free(p);p = NULL;
}
3、复杂度:
空间复杂度:因为要创建临时的空间,所以复杂度为O(N);
时间复杂度:O(N+t)
4、稳定性
在统计和重新排序过程中相同元素可能位置发生交换,所以为不稳定
以上就是我的分享了,如果有什么错误,欢迎在评论区留言。
最后,谢谢大家的观看!
相关文章:

排序-归并排序与计数排序
文章目录 一、归并排序1、概念2、过程3、代码实现4、复杂度5、稳定性 二、 计数排序1、思路2、代码实现3、复杂度:4、稳定性 一、归并排序 1、概念 是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已…...

国产数据库适配-人大金仓(kingbase V8R3)
金仓数据库是基于POSTGRE_SQL 参考资料 国产数据库人大金仓踩坑记录和函数适配_金仓数据库关系不存在-CSDN博客 Springboot工程 适配人大金仓 kingbase V8R3 引入驱动包和方言包 hibernate-5.2.17.Finaldialect.jar kingbase8-8.2.0.jar application.yml文件 driver-cla…...

HAAS 哈斯机床 读写刀补数据
哈斯机床不管是串口机床还是网口机床 都提供了Q命令 可以使用Q命令 进行刀具补偿的读取和写入 最多支持200把刀的 读取和写入...

Visual studio+Qt开发环境搭建以及注意事项和打开qt的.pro项目
下载qt-然后安装5.14.2_msvc2017 不知道安装那个就全选5.14.2的父级按钮 https://download.qt.io/archive/qt/5.14/5.14.2/ 安装Visual studio,下载直接下一步就行 配置Visual studio的qt环境 在线安装-重启Visual studio会自动安装 离线安装-关闭Visual studio点击安装 关闭…...

BUUCTF crypto做题记录(4)新手向
目录 一、大帝的密码武器 二、Windows系统密码 三、信息化时代的步伐 四、凯撒?替换?呵呵! 一、大帝的密码武器 下载的文件叫zip,应该是提示文件的后缀名是zip,把名字改成1.zip或者其他也行,主要保证后缀名是zip就…...

【ArcGIS微课1000例】0080:ArcGIS将shp转json(geojson)案例教程
本文以案例的形式,讲述在ArcGIS软件中,将矢量数据转为GeoJSON的方法。 扩展阅读:【GIS风暴】GeoJSON数据格式案例全解 文章目录 一、GeoJson简介二、ArcGIS将矢量数据转为GeoJSON一、GeoJson简介 GeoJSON是一种基于JSON的地理空间数据交换格式,它定义了几种类型JSON对象以…...

阿里云Centos8安装Dockers详细过程
一、卸载旧版本 较旧的 Docker 版本称为 docker 或 docker-engine 。如果已安装这些程序,请卸载它们以及相关的依赖项。 yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \do…...

leetcode 二数之和 三数之和 四数之和
leetcode 二数之和 三数之和 四数之和 又到了不想写博客的环节,不想归不想,有些事情还是要做的,今天总结的是多数之和的问题。 二数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target …...

制衣厂生产ERP系统怎么样?制衣厂生产ERP软件哪个好
有很多的制衣厂在订单处理、物料、仓储、销售、仓储、物料编码、车间成本核算、计件工资核算等方面还存在不少改进空间。 而经过多年的发展,现如今制衣行业的竞争比较激烈,如何提升各业务部门协同效率,减少车间物料损耗,简化生产…...

安装 DevEco Studio 后不能用本地 Node.js 打开
安装 DevEco Studio 后第一次打开时,不能用本地 Node.js 打开 答:因为本地 Node.js 文件夹名字中有空格 Node.js路径只能包含字母、数字、“。”、“_”、“-”、“:”和“V” 解决方法: 1.修改文件夹名称 2.重新下载 注意:找一…...

AppLink+WMS,实现仓储管理一体化
WMS像全能的库管员,可以在线还原真实仓库,让企业进行科学化、条理化、俯视化的仓库管理。 随着移动互联网和物流行业的快速发展,如何提高仓储管理的效率和准确性成为了企业关注的焦点。在这个背景下,结合AppLink和WMS系统&#x…...

如果是你,你选SOHO还是跟单?
昨天看到有人在讨论外贸跟单和外贸业务,谁的压力更大的问题?她们讨论的这个问题,源于一个年近四十准备二胎的宝妈,她做跟单十来年了,最近失业迷茫中,在纠结是否要SOHO?作为一个在工贸一体工厂做…...

大语言模型--能力
能力 大语言模型 能力从语言模型到任务模型的转化语言建模总结 从语言模型到任务模型的转化 在自然语言处理的世界中,语言模型 p p p是一种对代币序列 x 1 : L x_{1:L} x1:L这样的模型能够用于评估序列,例如 p ( t h e , m o u s e , a t e , t h e ,…...

安装LLaMA-Factory微调chatglm3,修改自我认知
安装git clone https://github.com/hiyouga/LLaMA-Factory.git conda create -n llama_factory python3.10 conda activate llama_factory cd LLaMA-Factory pip install -r requirements.txt 之后运行 单卡训练, CUDA_VISIBLE_DEVICES0 python src/train_web.py…...

以太网协议与DNS
以太网协议 以太网协议DNS 以太网协议 以太网用于在计算机和其他网络设备之间传输数据,以太网既包含了数据链路层的内容,也包含了物理层的内容. 以太网数据报: 其中目的IP和源IP不是网络层的目的IP和源IP,而是mac地址.网络层的主要负责是整体的转发过程,数据链路层负责的是局…...

Spring Boot的日志
打印日志 打印日志的步骤: • 在程序中得到日志对象. • 使用日志对象输出要打印的内容 在程序中得到日志对象 在程序中获取日志对象需要使用日志工厂LoggerFactory,代码如下: package com.example.demo;import org.slf4j.Logger; import org.slf4j.LoggerFactory;public c…...

Cisco Packet Tracer配置命令——交换机篇
交换机VLAN配置 在简单的网络环境中,当交换机配置完端口后,即可直接应用,但若在复杂或规模较大的网络环境中,一般还要进行VLAN的规划,因此在交换机上还需进行 VLAN 的配置。交换机的VLAN配置工作主要有VLAN的建立与删…...

python单例模式
设计模式:单例模式(Singleton Pattern)。单例模式确保一个类只有一个实例,并提供一个全局访问点来获取这个实例。 class Singleton:_instance Nonedef __new__(cls):if cls._instance is None:cls._instance super().__new__(cl…...

环境保护:人类生存的最后机会
随着科技的进步和人类文明的不断发展,地球上的自然资源也在以惊人的速度消耗殆尽。人类对于环境的无止境的掠夺,使得我们的地球正面临着前所未有的环境危机。环境污染、全球变暖、大规模灭绝等问题不断困扰着我们,似乎指向了人类生存的最后机…...

头歌-Python 基础
第1关:建模与仿真 1、 建模过程,通常也称为数学优化建模(Mathematical Optimization Modeling),不同之处在于它可以确定特定场景的特定的、最优化或最佳的结果。这被称为诊断一个结果,因此命名为▁▁▁。 填空1答案:决…...

C++数据结构:B树
目录 一. 常见的搜索结构 二. B树的概念 三. B树节点的插入和遍历 3.1 插入B树节点 3.2 B树遍历 四. B树和B*树 4.1 B树 4.2 B*树 五. B树索引原理 5.1 索引概述 5.2 MyISAM 5.3 InnoDB 六. 总结 一. 常见的搜索结构 表示1为在实际软件开发项目中,常用…...

【07】ES6:对象的扩展
一、对象字面量语法扩展 1、属性简写 当属性名称和属性值的变量名称相同时,可以省略冒号的变量名称。 const foo barconst baz { foo } // 等同于 const baz { foo: foo }baz // { foo: bar }function f(x, y) {return { x, y } } // 等同于 function f(x, y)…...

flink找不到隐式项
增加 import org.apache.flink.streaming.api.scala._ 即可...

【网络编程】-- 04 UDP
网络编程 6 UDP 6.1 初识Tomcat 服务端 自定义 STomcat S 客户端 自定义 C浏览器 B 6.2 UDP 6.2.1 udp实现发送消息 接收端: package com.duo.lesson03;import java.net.DatagramPacket; import java.net.DatagramSocket; import java.net.SocketExceptio…...

【脚本】图片-音视频-压缩文件处理
音视频处理 一,图片操作1,转换图片格式2,多张图片合成视频 二,音频操作1,转换音频格式2,分割音频为多段3,合成多段音频 三,视频操作1,转换视频格式2,提取视频…...

跨品牌的手机要怎样相互投屏?iPhone和iPad怎么相互投屏?
选择买不同品牌的手机是基于品牌声誉、产品特点、价格和性价比等多个因素的综合考虑。每个人的需求和偏好不同,选择适合自己的手机品牌是一个个人化的决策。 一些品牌可能更加注重摄影功能,而其他品牌可能更加注重性能和速度。选择不同品牌的手机可以根据…...

图像特征提取-角点
角点特征 大多数人都玩过拼图游戏。首先拿到完整图像的碎片,然后把这些碎片以正确的方式排列起来从而重建这幅图像。如果把拼图游戏的原理写成计算机程序,那计算机就也会玩拼图游戏了。 在拼图时,我们要寻找一些唯一的特征,这些…...

N26:构建无缝体验的平台工程之路-Part 2
在第一部分,我们介绍了 N26 团队为达成 “在 Day 1 实现轻松部署” 的目标而设定的战略规划和开发人员体验图,在这一部分,我们将带您了解该团队如何构建最简可行平台以及该平台如何运作。 01 计划构建最简可行平台 我们通…...

【Hadoop-Distcp】通过Distcp的方式进行两个HDFS集群间的数据迁移
【Hadoop-Distcp】通过Distcp的方式进行两个HDFS集群间的数据迁移 1)Distcp 工具简介及参数说明2)Shell 脚本 1)Distcp 工具简介及参数说明 【Hadoop-Distcp】工具简介及参数说明 2)Shell 脚本 应用场景: 两个实时集…...

【Linux】使用Bash和GNU Parallel并行解压缩文件
介绍 在本教程中,我们将学习如何使用Bash脚本和GNU Parallel实现高效并行解压缩多个文件。这种方法在处理大量文件时可以显著加快提取过程。 先决条件 确保系统上已安装以下内容: BashGNU Parallel 你可以使用以下命令在不同Linux系统上安装它们&am…...