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

归并排序详解:递归实现+非递归实现(图文详解+代码)

文章目录

  • 归并排序
        • 1.递归实现
        • 2.非递归实现
        • 3.海量数据的排序问题


归并排序


  • 时间复杂度:O ( N * logzN ) 每一层都是N,有log2N层
  • 空间复杂度:O(N),每个区间都会申请内存,最后申请的数组大小和array大小相同
  • 稳定性:稳定

目前为止,稳定的排序有:插入、冒泡、归并

  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,采用了分治法

在这里插入图片描述

  • 将待排序列分解,先使每个子序列有序,再使子序列段间有序
  • 将已有序的子序列合并,得到完全有序的序列
  • 若将两个有序表合并成一个有序表,称为二路归并
1.递归实现

在这里插入图片描述

  • 1.确定递归的结束条件,求出中间数mid,
  • 2.进行分解,根据mid来确定递归的区间大小
  • 3.递归分解完左边,然后递归分解右边
  • 4.左右分解完成后,进行合并
  • 5.申请新数组进行合并,比较两个数组段,记得查漏补缺
  • 6.和并的时候要对齐下标,每个tmp的下标要找到array中对应的下标
/*** 归并排序* @param array*/public static void mergeSort(int[] array) {mergeSortFunc(array,0,array.length-1);}private static void mergeSortFunc(int[] array, int left, int right) {//结束条件if (left >= right) {return;}//进行分解int mid = (left + right) / 2;mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);//左右分解完成后,进行合并merge(array, left, right, mid);}//进行合并private static void merge(int[] array, int start, int end, int mid) {int s1 = start;int s2 = mid + 1;int[] tmp = new int[end - start + 1];int k = 0;//k为tmp数组的下标while (s1 <= mid && s2 <= end) {//两个数组中都有数据//进行比较,放到新申请的数组if (array[s1] <= array[s2]) {tmp[k++] = array[s1++];} else {tmp[k++] = array[s2++];}}//因为有&&条件,数组不一定走完while (s1 <= mid) {tmp[k++] = array[s1++];}while (s2 <= end) {tmp[k++] = array[s2++];}//此时,将排好的tmp数组的数组,拷贝到arrayfor (int i = 0; i < tmp.length; i++) {array[i+start] = tmp[i];//对齐下标}}
2.非递归实现

在这里插入图片描述

  • 1.从1开始分组,先保证每个数都是独立有序的
  • 2.进行循环,i下标从0开始,每次跳转组数的两倍
  • 3.根据left = i,求出mid和right
  • 4.要避免mid和right越界
  • 5.分组进行合并
  • 6.二倍数扩大组数
/**** 归并排序,非递归实现* @param array*/public static void mergeSort2(int[] array) {int gap = 1;while (gap < array.length) {//i += gap * 2 i每次跳到下一组for (int i = 0; i < array.length; i += gap * 2) {int left = i;//要避免mid和right越界int mid = left + gap - 1;if(mid>=array.length){mid = array.length-1;//修正越界的情况}int right = mid + gap;if (right>=array.length){//修正越界的情况right = array.length-1;}merge(array,left,right,mid);//进行合并}gap *=2;//2倍数扩大组数}}//进行合并private static void merge(int[] array, int start, int end, int mid) {int s1 = start;int s2 = mid + 1;int[] tmp = new int[end - start + 1];int k = 0;//k为tmp数组的下标while (s1 <= mid && s2 <= end) {//两个数组中都有数据//进行比较,放到新申请的数组if (array[s1] <= array[s2]) {tmp[k++] = array[s1++];} else {tmp[k++] = array[s2++];}}//因为有&&条件,数组不一定走完while (s1 <= mid) {tmp[k++] = array[s1++];}while (s2 <= end) {tmp[k++] = array[s2++];}//此时,将排好的tmp数组的数组,拷贝到arrayfor (int i = 0; i < tmp.length; i++) {array[i + start] = tmp[i];//对齐下标}}
3.海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序

前提:内存只有 1G,需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序

  1. 先把文件切分成 200 份,每个 512 M
  2. 分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以
  3. 进行 2路归并,同时对 200 份有序文件做归并过程,最终结果就有序了

点击移步博客主页,欢迎光临~

偷cyk的图

相关文章:

归并排序详解:递归实现+非递归实现(图文详解+代码)

文章目录 归并排序1.递归实现2.非递归实现3.海量数据的排序问题 归并排序 时间复杂度&#xff1a;O ( N * logzN ) 每一层都是N,有log2N层空间复杂度&#xff1a;O&#xff08;N&#xff09;&#xff0c;每个区间都会申请内存&#xff0c;最后申请的数组大小和array大小相同稳定…...

DataBinding原理

1、MainActivity首先使用DataBindingUtil.setContentView设置布局文件activity_main.xml。 2、随后&#xff0c;经过一系列函数调用&#xff0c;ActivityMainBindingImpl对象最终会实例化&#xff0c;并与activity_main.xml进行绑定。 3、实例化后的ActivityMainBindingImpl对象…...

docker更换国内源

docker更换国内源 1、编辑Docker配置文件 在终端中执行以下命令&#xff0c;编辑Docker配置文件&#xff1a; vi /etc/docker/daemon.json2、添加更新源 在打开的配置文件中&#xff0c;添加以下内容&#xff1a; {"registry-mirrors": ["https://hub-mirror…...

【咖啡品牌分析】Google Maps数据采集咖啡市场数据分析区域分析热度分布分析数据抓取瑞幸星巴克

引言 咖啡作为一种受欢迎的饮品&#xff0c;已经成为我们生活中不可或缺的一部分。随着国内外咖啡品牌的涌入&#xff0c;新加坡咖啡市场愈加多元化和竞争激烈。 本文对新加坡咖啡市场进行了全面的品牌门店数占比分析&#xff0c;聚焦于热门品牌的地理分布、投资价值等。通过…...

【Java】异常处理(一)

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;Java ⭐每日一句&#xff1a;什么都不做&#xff0c;才会来不及 &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️ 文章目录 &#x1f4cb;前…...

【高级程序设计】Week2-4Week3-1 JavaScript

一、Javascript 1. What is JS 定义A scripting language used for client-side web development.作用 an implementation of the ECMAScript standard defines the syntax/characteristics of the language and a basic set of commonly used objects such as Number, Date …...

PHP笔记-->读取JSON数据以及获取读取到的JSON里边的数据

由于我以前是写C#的&#xff0c;现在学一下PHP&#xff0c; 在读取json数据的时候被以前的思维卡住了。 以前用C#读取的时候&#xff0c;是先定义一个数组&#xff0c;将反序列化的json存到数组里面&#xff0c;在从数组里面获取jaon中的“data”数据。 其实PHP的思路也是一样…...

【Spring Boot】如何集成Redis

在pom.xml文件中导入spring data redis的maven坐标。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 在application.yml文件中加入redis相关配置。 spr…...

Elasticsearch备份与还原:使用elasticdump

在数据管理的世界里&#xff0c;备份和还原数据是重中之重的日常工作&#xff0c;特别是对于Elasticsearch这样的强大而复杂的搜索引擎。备份不仅可以用于灾难恢复&#xff0c;还可以在数据迁移、测试或者升级等场景中发挥重要作用。 在本博客中&#xff0c;我们将会重点介绍如…...

给大伙讲个笑话:阿里云服务器开了安全组防火墙还是无法访问到服务

铺垫&#xff1a; 某天我在阿里云上买了一个服务器&#xff0c;买完我就通过MobaXterm进行了ssh&#xff08;这个软件是会保存登录信息的&#xff09; 故事开始&#xff1a; 过了n天之后我想用这个服务器来部署流媒体服务&#xff0c;咔咔两下就部署好了流媒体服务器&#x…...

js:react使用zustand实现状态管理

文档 https://www.npmjs.com/package/zustandhttps://github.com/pmndrs/zustandhttps://docs.pmnd.rs/zustand/getting-started/introduction 安装 npm install zustand示例 定义store store/index.js import { create } from "zustand";export const useCount…...

vue3+vite+SQL.js 读取db3文件数据

前言&#xff1a;好久没写博客了&#xff0c;最近一直在忙&#xff0c;没时间梳理。最近遇到一个需求是读取本地SQLite文件&#xff0c;还是花费了点时间才实现&#xff0c;没怎么看到vite方面写这个的文章&#xff0c;现在分享出来完整流程。 1.pnpm下载SQL.js(什么都可以下)…...

微信小程序 限制字数文本域框组件封装

微信小程序 限制字数文本域框 介绍&#xff1a;展示类组件 导入 在app.json或index.json中引入组件 "usingComponents": {"text-field":"/pages/components/text-field/index"}代码使用 <text-field maxlength"500" bindtabsIt…...

阿里国际站(直通车)

1.国际站流量 2.直通车即P4P&#xff08;pay for performance点击付费&#xff09; 2.1直通的含义&#xff1a;按点击付费&#xff0c;通过自助设置多维度展示产品信息&#xff0c;获得大量曝光吸引潜在买家。 注意&#xff1a;中国大陆和尼日利尼地区点击不扣费。 2.2扣费规…...

C# GC机制

在C#中&#xff0c;垃圾回收&#xff08;Garbage Collection&#xff0c;简称GC&#xff09;是CLR&#xff08;公共语言运行时&#xff09;的一个重要部分&#xff0c;用于自动管理内存。它会自动释放不再使用的对象所占用的内存&#xff0c;避免内存泄漏&#xff0c;减少程序员…...

wpf devexpress在未束缚模式中生成Tree

TreeListControl 可以在未束缚模式中没有数据源时操作&#xff0c;这个教程示范如何在没有数据源时创建tree 在XAML生成tree 创建ProjectObject类实现数据对象显示在TreeListControl: public class ProjectObject {public string Name { get; set; }public string Executor {…...

Python利器:os与chardet读取多编码文件

在数据处理中会遇到读取位于不同位置的文件,每个文件所在的层级不同,而且每个文件的编码类型各不相同,那么如何高效地读取文件呢? 在读取文件时首先需要获取文件的位置信息,然后根据文件的编码类型来读取文件。本文将使用os获取文件路径,使用chardet得到文件编码类型。 …...

微服务和注册中心

微服务和注册中心是紧密相关的概念&#xff0c;可以说注册中心是微服务架构中必不可少的一部分。 在微服务架构中&#xff0c;系统被拆分成了若干个独立的服务&#xff0c;因此服务之间需要进行通信和协作。为了实现服务的发现和调用&#xff0c;需要一个中心化的注册中心来进…...

吴恩达《机器学习》9-1-9-3:反向传播算法、反向传播算法的直观理解

一、正向传播的基础 在正向传播中&#xff0c;从神经网络的输入层开始&#xff0c;通过一层一层的计算&#xff0c;最终得到输出层的预测结果。这是一种前向的计算过程&#xff0c;即从输入到输出的传播。 二、反向传播算法概述 反向传播算法是为了计算代价函数相对于模型参数…...

Java 算法篇-链表的经典算法:判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 链表的创建 2.0 判断回文链表说明 2.1 快慢指针方法 2.2 使用递归方式实现反转链表方法 2.3 实现判断回文链表 - 使用快慢指针与反转链表方法 3.0 判断环链表说明…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...