【数据结构入门】排序算法(4)归并排序

        

目录

1.排序的原理

1.1 保证子数组有序

1.2 时间复杂度

2. 递归实现

2.1 思路

2.2 代码

3. 非递归实现

3.1 思路

3.2 代码

4.面试题

4.1 题目

4.2 思路

       

1.排序的原理

归并排序是外排序，所谓外排序就是说能够对文件中的数据进行排序。

①首先，将待排序数组分成两部分，这两部分数组一定是有序的，使用两个指针分别初始化于这两部分的首元素；

②需要一个临时空间，两个指针指向的较小的元素先放入空数组中。

③如果选择其中一个指针的元素，那么该指针需要后移一位，如果没选到该元素，指针不动。

④如果其中一个数组元素被取完了，那么另外一个数组的内容直接填入空数组。

        上面的操作是建立在两部分数组是分别有序的情况下，但是我们如何保证两部分的数组是有序的呢？

1.1 保证子数组有序

                保证当前区间是有序的，如果该区间不是有序的，那么需要将该区间分成子区间，从而保证子区间有序，如果该区间只剩一个数，那么说明这个区间是有序的。

        将区间细分到只有一个数的时候，这就是递归的“归”，此时返回上一层的函数栈帧，使父区间变得有序。

1.2 时间复杂度

        这里可以将递归的过程当做二叉树的生成，每一层的节点是N，二叉树的高度是LogN，那么时间复杂度就可以计算出来是N*logN。

2. 递归实现

2.1 思路

①首先写一个归并排序的主函数，主函数需要创建一个临时变量tmp，用于存放排序的数据；

②调用归并排序的子函数，子函数需要传入原数组、区间、临时数组，子函数的目的是为了让区间内的数组有序。

③子函数：首先这是一个递归，需要写递归退出条件，即left >= right下标不合法或者就剩一个元素，说明是有序的，就退出递归。

④使用递归分别让左右区间分别有序。

⑤开始合并有序数组，begin指针指向的元素更小的存入tmp中。

⑥把tmp数组的元素拷贝回原数组。

2.2 代码

        

#include<stdio.h>// 使区间变得有序的方法
void _merge_sort(int* arr, int left, int right, int* tmp)
{// 递归退出条件if (left >= right){return;}// 求mid,将[left,right]分为[left,mid][mid+1,right]两部分int mid = (left + right) / 2;// 保证两区域是有序的才能进行合并有序数组_merge_sort(arr, left, mid, tmp);_merge_sort(arr, mid + 1, right, tmp);// 开始合并有序数组int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;// 记录tmp的下标int tmp_index = begin1;while (begin1 <= end1 && begin2 <= end2){// 两个有序数组，哪个小放哪个if (arr[begin1] < arr[begin2]){tmp[tmp_index++] = arr[begin1++];}else{tmp[tmp_index++] = arr[begin2++];}}// 退出的时候是某一数组已经取值完毕了while (begin1 <= end1){tmp[tmp_index++] = arr[begin1++];}while (begin2 <= end2){tmp[tmp_index++] = arr[begin2++];}// 将tmp数组的值全部放回arr去，进行覆盖for (int i = left; i <= right; ++i){arr[ i] = tmp[i];}
}void merge_sort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_merge_sort(arr, 0, n - 1, tmp);free(tmp);	
}

3. 非递归实现

3.1 思路

        使用循环，首先每一个元素作为一个单位进行排序，接下来两个一组为单位进行排序如下图所示：

最后按照四个元素一组进行排序，我们只需要控制间距即可。

3.2 代码

        首先写gap为1的时候，该如何操作，当gap为1的的时候，我们只需要将相邻两个元素进行合并操作，例如将10和6合并成6和10，下一次合并需要将7和1合并成1和7；以此类推。

        我们可以将合并有序数组这个方法单独抽象出来，然后后面直接调用此方法即可，下面的代码就是当gap=1的时候，书写的代码。

// 抽象合并有序数组的函数
void merge_array(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{int left = begin1, right = end2;// 记录tmp的下标int tmp_index = begin1;while (begin1 <= end1 && begin2 <= end2){// 两个有序数组，哪个小放哪个if (arr[begin1] < arr[begin2]){tmp[tmp_index++] = arr[begin1++];}else{tmp[tmp_index++] = arr[begin2++];}}// 退出的时候是某一数组已经取值完毕了while (begin1 <= end1){tmp[tmp_index++] = arr[begin1++];}while (begin2 <= end2){tmp[tmp_index++] = arr[begin2++];}// 将tmp数组的值全部放回arr去，进行覆盖for (int i = left; i <= right; ++i){arr[ i] = tmp[i];}
}void merge_sort_non(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;// 【i,i + gap - 1】和【i + gap,i + 2 * gap - 1】闭区间for (int i = 0; i < n; i+= 2*gap)// 1,2合并之后，i下一次要合并3,4,{merge_array(arr, i, i + gap - 1, i + gap, i + 2 * gap - 1, tmp);// gap=1的时候就是两个数合并}free(tmp);
}

我们可以验证一下，当gap=1的时候是否正确：

最后调整gap，外面增加一层循环，gap最多是n/2，每次循环gap需要变为原来的2倍，1,2,4.....

        这里需要注意的是，当gap不断变化，第二组有可能会出现越界的情况，下面需要标注第二组两种越界情况。

void merge_sort_non(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap <n){// 【i,i + gap - 1】和【i + gap,i + 2 * gap - 1】闭区间for (int i = 0; i < n; i += 2 * gap)// 1,2合并之后，i下一次要合并3,4,{// 确保不越界int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;// 确保不越界if (begin2 >= n) break;  // 第二个数组不存在if (end2 >= n) end2 = n - 1;  // 调整第二个数组的结束位置merge_array(arr, begin1, end1, begin2, end2, tmp);}gap *= 2;}free(tmp);
}

gap其实就是决定有多少个数进行合并，gap为1的时候，其实就是1个数和1个数进行合并。

4.面试题

4.1 题目

        ①文件有10亿个数据，需要排序，怎么办？假设内存中最多只能放1000w个数据。

首先将数据分成100份，一份就是1000w个数据，将每一份数据两两归并排序成一个文件（磁盘）

假设文件中的数据是按照换行来分割的：

首先需要将数据分成n等份，每一份的大小刚好可以存入内存里，然后对每一份进行排序，生成n份文件。

// 外排序,返回一个文件名
void file_sort(char* file)
{FILE* fout = fopen(file, "r");if (fout == NULL){printf("文件打开失败\n");exit(-1);}int num = 0;int n = 10;// 将文件内容分成10份int arr[10];// 临时存10个数int i = 0;char subfile[20];// 子文件名称int id = 0; // 子文件下标while (fscanf(fout, "%d\n", &num) != EOF){if (i < n){arr[i++] = num;}else{// 满10个了就排序merge_sort(arr, n);sprintf(subfile, "sub\\subfile_%d.txt", id++);printf("%s", subfile);// 对每一个文件进行写FILE* fin = fopen(subfile, "w");for (int i = 0; i < n; i++){fprintf(fin, "%d\n", arr[i]);}fclose(fin);i = 0;}}fclose(fout);}int main()
{file_sort("sort.txt");}

然后对这n份文件进行合并，实现整体有序，两两合并，可以如下图也可以两两等分合并。

思路就是，有两个小文件file1、file2作为临时变量，首先合并形成m_file，然后将fiel2后移一位到下一个文件，file1变成m_file，继续合并形成新的m_file。

4.2 思路

①每n个数据为一组（这里n=10），读到n个的时候进行排序创建一个文件，那么100个数据就会有10个文件1-10；每一个文件需要先排序再写入。

②使用三个变量，file1、file2、m_file用于存储文件名，file1和file2合并之后写死文件名为12；后面将合并后的数据给file1，修改m_file的文件名为：之前的文件名+i（当前下标+1，i从2开始），使其命名能够逐步增加。

③依次迭代1+2的数据称为新的file1再和迭代后新的file2继续合并，最后的结果就是10个文件的最终排序结果。

void _merge_file(const char* file1, const char* file2, const char* m_file)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){printf("文件打开失败\n");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){printf("文件打开失败\n");exit(-1);}FILE* fin = fopen(m_file, "w");if (fin == NULL){printf("文件打开失败\n");exit(-1);}int num1, num2;// 如果两个文件都没有读完就继续int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);while (ret1 != EOF&& ret2 != EOF){if (num1 < num2){// nums1写到m_filefprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);// fiel1的指针后移}else{fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);// fiel1的指针后移}}// 其中一个结束，另外一个按序写入while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);// fiel1的指针后移}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);// fiel1的指针后移}fclose(fin);fclose(fout1);fclose(fout2);
}// 外排序,返回一个文件名
void file_sort(char* file)
{FILE* fout = fopen(file, "r");if (fout == NULL){printf("文件打开失败\n");exit(-1);}int num = 0;int n = 10;// 将文件内容分成10份int arr[10];// 临时存10个数int i = 0;char subfile[20];// 子文件名称int id = 1; // 子文件下标while (fscanf(fout, "%d\n", &num) != EOF){if (i < n - 1) // 前n-1个数据{arr[i++] = num;}else{// 第十个arr[i] = num;// 满10个了就排序merge_sort(arr, n);sprintf(subfile, "%d", id++);printf("%s", subfile);// 对每一个文件进行写FILE* fin = fopen(subfile, "w");for (int i = 0; i < n; i++){fprintf(fin, "%d\n", arr[i]);}fclose(fin);i = 0;}}fclose(fout);// 读取两个文件char file1[100] = "1";char file2[100];char m_file[100] = "12"; // 合并的文件for (int i = 2; i <= n; i++){sprintf(file2, "%d.txt", i);// 读取file1和file2，将合并内容放到m_file_merge_file(file1, file2, m_file);// file1变成mfilestrcpy(file1,m_file);sprintf(m_file, "%s%d", m_file,i+1); // 拼接}}int main()
{file_sort("sort.txt");}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/96672.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/96672.shtml

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

相关文章

FLEXSPI_Init 硬件故障问题

FLEXSPI_Init 硬件故障问题

使用官方例程发现FLEXSPI_Init会引起硬件故障&#xff0c;查阅相关帖子发现主要有两个可能&#xff1a;1、外部闪存配置差异修改 LUT&#xff08;查找表&#xff09;命令&#xff1a;示例中擦除扇区命令为 0xD7&#xff0c;写状态寄存器命令为 0x01&#xff0c;需分别改为 闪存…
阅读更多...
如何用 Rust 重写 SQLite 数据库（一）:项目探索

如何用 Rust 重写 SQLite 数据库（一）:项目探索

要使用 Rust 重写 SQLite 数据库&#xff0c;我们需要实现一个简化的关系型数据库核心功能&#xff08;如 SQL 解析、存储引擎、事务管理&#xff09;。以下是一个分步实践指南&#xff0c;包含关键代码示例。一、项目规划 我们将实现一个超简化数据库 MiniSQL&#xff0c;支持…
阅读更多...
JVM之堆（Heap）

JVM之堆（Heap）

一、堆的核心特性 唯一性与共享性 每个JVM实例仅有一个堆&#xff0c;所有线程共享&#xff0c;但可通过线程私有缓冲区&#xff08;TLAB&#xff09;减少多线程分配冲突。内存结构演变 JDK 7及之前&#xff1a;堆分为新生代&#xff08;Young&#xff09;、老年代&#xff08;…
阅读更多...
单片机的RAM与ROM概念

单片机的RAM与ROM概念

RAM与ROM1、RAM与ROM2、 bss、data、heap、stack、text详细讲解3、详细探讨 TCM、OCRAM 和 HBNRAM 之间的区别及其具体作用。3.1、TCM&#xff08;Tightly Coupled Memory&#xff09;3.2、 OCRAM&#xff08;On Chip RAM&#xff09;3.3、HBNRAM (Hibernate RAM)3.4、总结1、R…
阅读更多...
实验3：事件处理（2学时）

实验3：事件处理（2学时）

实验目的&#xff08;1&#xff09;熟练掌握 v-on 指令的用法&#xff0c;学会使用 v-on 指令监听 DOM 元素的事件&#xff0c;并通过该事件触发调用事件处理程序。&#xff08;2&#xff09;掌握v-on 指令修饰符的基本用法。实验内容实现购物车功能的拓展&#xff08;商品数量…
阅读更多...
商品库存扣减方案

商品库存扣减方案

文章目录1. Lua脚本 Redis&#xff08;业界首选&#xff0c;综合最优&#xff09;2. Redis原子命令&#xff08;DECRBY 结果校验&#xff09;3. Redis事务&#xff08;MULTI/EXEC&#xff09;4. 分布式锁&#xff08;基于Redis实现&#xff09;5. Redisson客户端封装&#xf…
阅读更多...
关于在阿里云DMS误操作后如何恢复数据的记录

关于在阿里云DMS误操作后如何恢复数据的记录

前言 昨天因客户员工操作错误&#xff0c;导致快递单号和订单互换。客户员工那边让笔记修改数据。 于是笔者写下如下SQL来操作&#xff0c;导致了灾难性事故。 update t_order_fed_ex_record set tracking_number 884102170661, master_tracking_number 884102170661, push…
阅读更多...
【操作系统核心知识梳理】线程（Thread）重点与易错点全面总结

【操作系统核心知识梳理】线程（Thread）重点与易错点全面总结

在多任务操作系统中&#xff0c;线程是比进程更轻量的执行单元&#xff0c;理解线程的特性和实现方式是掌握并发编程的基础。本文系统梳理了线程相关的核心知识点和常见误区&#xff0c;助你夯实操作系统基础。一、线程的基本概念与引入目的 1.1 什么是线程&#xff1f; 线程是…
阅读更多...
深入理解 Python 中的 `__call__` 方法

深入理解 Python 中的 `__call__` 方法

化身为可调用的对象&#xff1a;深入理解 Python 中的 __call__ 方法 引言&#xff1a;函数与对象的边界模糊化 在 Python 中&#xff0c;我们最熟悉的概念莫过于函数&#xff08;Function&#xff09; 和对象&#xff08;Object&#xff09;。函数是可调用的&#xff08;calla…
阅读更多...
云服务器使用代理稳定与github通信方法

云服务器使用代理稳定与github通信方法

使用SSH反向隧道 (SSH Reverse Tunneling) 利用SSH连接在您的本地电脑和云服务器之间建立一个反向的加密通道。 原理&#xff1a; 从本地电脑发起一个SSH命令到您的云服务器&#xff0c;这个命令会告诉云服务器&#xff1a;“请监听您自己的某个端口&#xff08;例如&#xff1…
阅读更多...
7.k8s四层代理service

7.k8s四层代理service

Service的基本介绍 Cluster IP&#xff1a;每个 Service 都分配了一个Cluster IP&#xff0c;它是一个虚拟的内部IP地址&#xff0c;用于在集群内部进行访问。这个虚拟IP是由Kubernetes自动分配的&#xff0c;并且与Service对象一一对应。 端口映射&#xff1a;Service可以映射…
阅读更多...
Qt 工程中 UI 文件在 Makefile 中的处理

Qt 工程中 UI 文件在 Makefile 中的处理

Qt 工程中 UI 文件在 Makefile 中的处理 在 Qt 工程中&#xff0c;.ui 文件&#xff08;Qt Designer 界面文件&#xff09;需要通过 uic&#xff08;用户界面编译器&#xff09;工具转换为对应的头文件。以下是几种情况下如何处理 UI 文件&#xff1a;1. 使用 qmake 自动生成 M…
阅读更多...
ZLMediaKit性能测试

ZLMediaKit性能测试

一、环境 系统&#xff1a;虚拟机 Ubuntu22.04 64bit配置: 4核8G设置&#xff1a;ulimit -n 102400 二、安装 依赖安装sudo apt update sudo apt install ffmpeg sudo apt install nloadzlm服务安装参考&#xff1a;https://blog.csdn.net/hanbo622/article/details/149064939?…
阅读更多...
智能文档处理业务，应该选择大模型还是OCR专用小模型？

智能文档处理业务，应该选择大模型还是OCR专用小模型？

智能文档处理业务中&#xff0c;最佳策略不是二选一&#xff0c;而是“大小模型协同”。用专用小模型处理高频、标准化的核心文档流&#xff0c;实现极致效率与成本控制&#xff1b;用大模型赋能非标、长尾文档的灵活处理&#xff0c;加速业务创新。 OCR小模型会被大模型取代吗…
阅读更多...
android 如何判定底部导航栏显示时 不是键盘显示

android 如何判定底部导航栏显示时 不是键盘显示

在 Android 中判定底部导航栏是否显示时&#xff0c;核心痛点是 区分 “导航栏的底部 Insets” 和 “软键盘弹出的底部 Insets”—— 两者都会导致 getSystemWindowInsetBottom() 返回非零值&#xff0c;直接判断会误将键盘弹出当成导航栏显示。以下是基于 WindowInsets 类型区…
阅读更多...
你知道服务器和电脑主机的区别吗？

你知道服务器和电脑主机的区别吗？

我们都知道服务器和台式主机有着不同之处&#xff0c;但具体说出个一二三来很多人还是一头雾水&#xff0c;也就是知其然不知其所以然&#xff0c;都是CPU主板 内存 硬盘 电源&#xff0c;撑死就差一个显卡不同&#xff0c;但其实服务器和我们正常使用的台式主机差距很大&#…
阅读更多...
什么是包装类

什么是包装类

什么是包装类 在Java中&#xff0c;包装类&#xff08;Wrapper Class&#xff09;是为基本数据类型提供的对应的引用类型。Java中的基本数据类型&#xff08;如int、char、boolean等&#xff09;不是对象&#xff0c;为了在需要对象的场景中使用基本数据类型&#xff08;如集合…
阅读更多...
用Python打造专业级老照片修复工具：让时光倒流的数字魔法

用Python打造专业级老照片修复工具：让时光倒流的数字魔法

在这个数字化时代&#xff0c;我们手中珍藏着许多泛黄、模糊、甚至有划痕的老照片。这些照片承载着珍贵的回忆&#xff0c;但时间的侵蚀让它们失去了往日的光彩。今天&#xff0c;我将带您一起用Python开发一个专业级的老照片修复工具&#xff0c;让这些珍贵的记忆重现光彩。为…
阅读更多...
linux中查找包含xxx内容的文件

linux中查找包含xxx内容的文件

linux中怎么查找哪个文件包含xxx内容 在Linux中查找包含特定内容的文件 在Linux系统中&#xff0c;有几种常用方法来查找包含特定内容的文件。以下是几种最有效的方法&#xff1a;1. 使用 grep 命令&#xff08;最常用&#xff09; 基本语法&#xff1a;bash grep -r "搜索…
阅读更多...
sklearn 加州房价数据集 fetch_california_housing 出错 403: Forbidden 修复方案

sklearn 加州房价数据集 fetch_california_housing 出错 403: Forbidden 修复方案

问题 加载加州房价数据时出现 403 错误 HTTP Error 403: Forbidden from sklearn.datasets import fetch_california_housingcalifornia fetch_california_housing() print(california.target.shape) 解决方案 运行下述代码&#xff0c;然后再运行上述的 fetch_california_hou…
阅读更多...
最新文章

Copyright @ 2022~2023