排序-归并排序与计数排序

文章目录

    • 一、归并排序
      • 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[] = { 3710962385 };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、稳定性

在统计和重新排序过程中相同元素可能位置发生交换,所以为不稳定

以上就是我的分享了,如果有什么错误,欢迎在评论区留言。
最后,谢谢大家的观看!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/219232.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

黑色翻页时钟HTML源码-倒计时单页翻页时钟

黑色翻页时钟HTML源码-倒计时单页翻页时钟这是一个类似fliqlo的黑色翻页时钟HTML源码&#xff0c;它仅包含一个HTML文件&#xff0c;上传到网站后即可使用。该时钟具有查看当前时间、秒表和倒计时功能&#xff0c;并且可以在页面的右下角进行设置。 红色动态炫酷数字时钟html网…

智能优化算法应用:基于和声算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于和声算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于和声算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.和声算法4.实验参数设定5.算法结果6.参考文献7.MA…

大一python题库刷题训练,大一python填空题题库

大家好&#xff0c;给大家分享一下大一python题库及答案和分析&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; 这篇文章主要介绍了大一python上机题库及答案&#xff0c;具有一定借鉴价值&#xff0c;需要的朋友可以参考下。希望大家阅读完…

化妆刷适合用超声波清洗机洗吗?超声波清洗机可以洗什么物品?

随着科技发展&#xff0c;现在有很多物品都可以交给机器去清洗了&#xff0c;是越来越智能化&#xff01;其中&#xff0c;超声波清洗机就是一项非常实用的技术。它利用高频振动和清洗液的共同作用&#xff0c;能够有效地清除各种物品上的污渍和细菌。而在我们的日常生活中&…

27系列DGUS智能屏发布:可实时播放高清模拟信号摄像头视频

针对高清晰度的模拟信号摄像头视频画面的显示需求&#xff0c;迪文特推出27系列DGUS智能屏。该系列智能屏可适配常见的AHD摄像头、CVBS摄像头&#xff0c;支持单路1080P高清显示、两路720P同屏显示&#xff08;同一类型摄像头&#xff09;。用户通过DGUS简单开发即可实现摄像头…

Android 升级签名算法从SHA1withRSA 升级到SHA256withRSA

一 背景 想到要修改这个问题 是因为收到下面整改通知 要求我们更新签名文件的签名算法&#xff0c;看到这个问题都懵了呀 虽然打包天天用签名文件 但是从来没关注过他呀 开发者自查&#xff1a; 不要使用已经过时或不安全的弱算法&#xff0c;确保签名证书使用了更强的签名算法…

leetcode(力扣) 89. 格雷编码 (规律题)

文章目录 题目描述思路分析完整代码 题目描述 n 位格雷码序列 是一个由 2n 个整数组成的序列&#xff0c;其中&#xff1a; 每个整数都在范围 [0, 2n - 1] 内&#xff08;含 0 和 2n - 1&#xff09; 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表…

【JVM入门到实战】(三) 查看字节码文件的工具

一、 javap -v命令 javap是JDK自带的反编译工具&#xff0c;可以通过控制台查看字节码文件的内容。适合在服务器上查看字节码文件内容。直接输入javap查看所有参数。输入javap -v 字节码文件名称 查看具体的字节码信息。&#xff08;如果jar包需要先使用 jar –xvf 命令解压&a…

Android Error inflating class android.webkit.WebView

对于app是系统级别的APP&#xff0c;如下设置的 android:sharedUserId“android.uid.system” 遇到使用WebView出现下面的错误时 Process: com.alps.gamecenter, PID: 25495 android.view.InflateException: Binary XML file line #34: Binary XML file line #34: Error infl…

用标记接口定义类型

标记接口是不含有任何方法的接口&#xff0c;它的目的是通过将特定接口应用于类来为该类添加类型信息。以下是一个示例&#xff1a; public interface Drawable {// 标记接口&#xff0c;不包含任何方法 }public class Circle implements Drawable {private int radius;public…

亚信科技AntDB数据库——深入了解AntDB-M元数据锁的实现(一)

锁的获取 5.1 锁的强弱 当线程已经持有的锁比新申请的锁更强时&#xff0c;认为已经持有了锁&#xff0c;无需再对申请锁类型加锁。锁的强弱指持有的锁与其他锁的不兼容集合大小&#xff0c;集合相同锁相同&#xff0c;集合更大锁更强&#xff0c;否则无强弱关系。通过锁的兼…

产品经理之如何编写竞品分析(医疗HIS系统管理详细案例模板)

目录 一.项目周期 二.竞品分析的目的 三.竞品分析包含的维度 四.如何选择竞品 五.竞品画布 六.案例模板 一.项目周期 在整个项目的周期&#xff0c;产品经理所做的事情主要在项目前期做市场分析、需求调研等&#xff0c;下面一张图概况了整个项目周期产品经理、开发工程师…

自定义注解

自定义注解 自定义注解 以实战案例为驱动,快速掌握此怎么自己自定义注解,也好出去自己吹牛逼~哈哈哈 假设我们打车,需要检验验证码,我们需要一个注解字来进行核验,我们怎么操作呢? 大纲总览 ​​ 1.定义注解 可以自己创一个包单门存放自己的注解: 如​constraints​ 包 然后…

Java入门学习笔记一

一、Java语言环境搭建 1、JAVA语言的跨平台原理 1.1、什么是跨平台性&#xff1f; 跨平台就是说&#xff0c;同一个软件可以在不同的操作系统&#xff08;例如&#xff1a;Windows、Linux、mad&#xff09;上执行&#xff0c;而不需要对软件做任务处理。即通过Java语言编写的…

PMP项目管理 - 风险管理

系列文章目录 PMP项目管理 - 质量管理 PMP项目管理 - 采购管理 PMP项目管理 - 资源管理 PMP项目管理 - 风险管理 现在的一切都是为将来的梦想编织翅膀&#xff0c;让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in…

虚拟机启动 I/O error in “xfs_read_agi+0x95“

1.在选择系统界面按e 进入维护模式 2.找到ro把ro改成 rw init/sysroot/bin/sh 然后按Ctrlx 3.找到坏掉的分区&#xff0c;以nvme0n1p3为例进行修复 xfs_repair -d /dev/nvme0n1p3 4.init 6 重新启动 以下情况 先umount 再修复 则修复成功

计算机网络:数据链路层(网桥)

带你速通计算机网络期末 目录 一、冲突域和广播域 二、网桥介绍 三、网桥分类—―透明网桥 四、网桥分类―—源路由网桥 五、多接口网桥―—以太网交换机 总结 一、冲突域和广播域 冲突域:在同一个冲突域中的每一个节点都能收到所有被发送的帧。简单的说就是同一时间内只…

Linux-----6、文件操作管理

# 文件操作管理 重要&#xff1a;Linux下&#xff0c;一切皆文件&#xff01;&#xff01;&#xff01; 说在前面&#xff1a; 接下来所有的命令需要在一个载体上执行&#xff0c;这个载体就叫做终端。 终端上所有命令都需要一个东西翻译解析一下&#xff0c;计算机才能理解…

ProcessOn在线绘制部分项目流程图

目录 一、ProcessOn 1.1 简介 1.2 官方网站 二、Axure自定义元件库 2.1 新建元件库 2.2 自定义元件 2.3 添加元件库 三、HIS系统门诊流程图 四、HIS系统住院流程图 五、HIS系统药品采购入库流程图 六、OA会议流程图 一、ProcessOn 1.1 简介 ProcessOn是一款在线的流…

期货股市联动(期股联动助推资本市场上扬)

期股联动——期货股市助推资本市场上扬 随着我国资本市场的不断发展&#xff0c;期货和股票这两个市场也在逐渐紧密地联系起来。期货和股票的相互作用是一种“期股联动”&#xff0c;它能够促进资本市场的上扬。 期货与股票市场 期货市场是一种标准化的场外交易市场&#xf…