归并排序:从二路到多路

前言

我们所熟知的快速排序归并排序都是非常优秀的排序算法。

但是快速排序和归并排序的一个区别就是:快速排序是一种内部排序,而归并排序是一种外部排序

简单理解归并排序:递归地拆分,回溯过程中,将排序结果进行合并。

大致流程示意图:

 

假设递归的终止条件就是剩下三个以下的元素就可以排序了。

注意:这步合并的过程用到了额外的存储空间。完成了排序之后再复制回去。

二路归并演示代码

#include <iostream>
using namespace std;void merge_sort(int *arr, int l, int r) {// 递归终止条件:只有一个元素或者没有元素的时候,不需要排序。if (l >= r) return ;// 打印输出排序之前的情况cout << endl;cout << "sort " << l << "<-->" << r << " : ";for (int i = l; i <= r; i++) cout << arr[i] << " ";cout << endl;int mid = (l + r) >> 1;merge_sort(arr, l, mid); // left sortmerge_sort(arr, mid + 1, r); // right sort// 写递归代码,一定不要展开地看,上面两行代码就当做左右子区间已经排序好了。// 下面将对两个区间进行合并,需要开辟新的空间将元素存到temp数组中。int *temp = (int *)malloc(sizeof(int) * (r - l + 1));int k = 0, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if ((p2 > r) || (p1 <= mid && arr[p1] <= arr[p2])) {// 只有当右边为空,或者左边不为空并且左边比右边小,才将左边的元素放入temp[k++] = arr[p1++];} else {temp[k++] = arr[p2++];}}// 最后再拷贝回去即可for (int i = l; i <= r; i++) arr[i] = temp[i - l];// 打印输出排序之后的情况for (int i = l; i <= r; i++) cout << arr[i] << " ";cout << endl;free(temp);return ;
}int main() {int n;int arr[100];cin >> n;for (int i = 0; i < n; i++) cin >> arr[i];merge_sort(arr, 0, n - 1);for (int i = 0; i < n; i++) cout << arr[i] << " ";return 0;
}

输入数据:

10 
7 9 0 8 6 4 5 3 1 2

输出:

sort 0<-->9 : 7 9 0 8 6 4 5 3 1 2 sort 0<-->4 : 7 9 0 8 6 sort 0<-->2 : 7 9 0 sort 0<-->1 : 7 9 
7 9 
0 7 9 sort 3<-->4 : 8 6
6 8
0 6 7 8 9sort 5<-->9 : 4 5 3 1 2sort 5<-->7 : 4 5 3sort 5<-->6 : 4 5
4 5
3 4 5sort 8<-->9 : 1 2
1 2
1 2 3 4 5
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

多路归并

上述演示代码的归并排序只是二路归并。将两个有序数组合并为一个有序数组。

那么多路归并就很好理解了,就是将多个有序数组合并为一个有序数组。

比如三路归并:

 关于多路归并排序的应用,有一道很经典的面试题:

意思就是:我的内存太小了,无法通过诸如快速排序这样的内部排序算法,进行数据的直接整体排序。那么为什么这个问题可以由归并算法来解决呢?

归并的时候,外存可以作为归并排序中的那片关键的额外空间,数据是可以直接写回外存的,所以不需要内存有40GB的额外空间来先存放排序完的数据,再写回外存。

其实这40GB的文件可以被拆分成20份2GB的小文件,我们只要分别对20份小文件进行排序之后,进行20路归并操作就可以了

注意:程序执行一定是在内存当中,所有的数据也都需要从辅存或者外存当中调入内存当中,才可以进行CPU的运算。一个2GB大小的内存当然无法调入40GB的数据。

还需注意的是:我们在程序中只存储了相应的文件指针,并没有将文件中的内容一次性全部读满内存,而是需要一个数据就从文件中读一个数据。

读取文件演示代码:

*************************************************************************> File Name: merge_file.cpp> Author: jby> Mail: > Created Time: Sat 12 Aug 2023 11:39:20 PM CST************************************************************************/#include<iostream>
using namespace std;int main(int argc, char *argv[]) {int n = argc - 1; // 读取文件数量FILE **farr = (FILE **)malloc(sizeof(FILE *) * n);for (int i = 1; i <= n; i++) {farr[i - 1] = fopen(argv[i], "r");}for (int i = 0; i < n; i++) {int a;while (~fscanf(farr[i], "%d", &a)) {printf("%d\n", a);}printf("======\n");}return 0;
}

生成俩数据文件:file1、file2

# file1
1
34
56
78

# file2:
3
45
89
100
执行命令行:$./a.out file1 file2

输出结果:

1
34
56
78
======
3
45
89
100
======

这样我们就依次读取了存放在两个文件中的数据。

文件排序演示代码(简单实现,不用归并)

/*************************************************************************> File Name: merge_file.cpp> Author: jby> Mail: > Created Time: Sat 12 Aug 2023 11:39:20 PM CST************************************************************************/#include<iostream>
using namespace std;struct Data {FILE *fin;     // fin: 当前文件指针int val, flag; // val: 当前读取的值;flag: 当前文件是否为空
};int main(int argc, char *argv[]) {int n = argc - 1; // 读取文件数量Data *data = (Data *)malloc(sizeof(Data) * n);for (int i = 1; i <= n; i++) {data[i - 1].fin = fopen(argv[i], "r");if (fscanf(data[i - 1].fin, "%d", &data[i - 1].val) == EOF) {data[i - 1].flag = 1;} else {data[i - 1].flag = 0;}}FILE *fout = fopen("output", "w");while (1) {int flag = 0;int ind = -1;int minVal = 0x3f3f3f3f;for (int i = 0; i < n; i++) {if (data[i].flag) continue; // 当前文件为空if (ind == -1 || data[i].val < data[ind].val) {ind = i;}}if (ind != -1) {fprintf(fout, "%d\n", data[ind].val); // 向结果文件中输出内容if (fscanf(data[ind].fin, "%d", &data[ind].val) == EOF) {data[ind].flag = 1;} else {data[ind].flag = 0;}flag = 1;}if (flag == 0) break;}return 0;
}
执行命令行:$./a.out file1 file2

输出结果,保存在output文件中:

1
3
34
45
56
78
89
100

归并排序的算法思想

我们不妨把思维从排序问题当中延展出来,归并排序的算法思想可以看成是以下三个步骤:

  1. 左边处理一下,得到左边的信息
  2. 右边处理一下,得到右边的信息
  3. 最后再处理,横跨左右两边的信息

这就是分而治之的思想。

LeetCode刷题实战

剑指 Offer 51. 数组中的逆序对

在归并排序的过程中,当右边区间的元素放进额外空间的时候,左边剩下的元素个数就是该元素所对应的逆序对个数。所以可以在归并的过程中不断累加。

class Solution {
public:vector<int> temp;int countResult(vector<int>& nums, int l, int r) {if (l >= r) return 0; // 如果只有一个元素,逆序数为0int ans = 0, mid = (l + r) >> 1;ans += countResult(nums, l, mid);ans += countResult(nums, mid + 1, r);int k = l, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if ((p2 > r) || (p1 <= mid && nums[p1] <= nums[p2])) {temp[k++] = nums[p1++];} else {temp[k++] = nums[p2++];ans += (mid - p1 + 1);}}for (int i = l; i <= r; i++) nums[i] = temp[i];return ans;}int reversePairs(vector<int>& nums) {while (temp.size() < nums.size()) temp.push_back(0);return countResult(nums, 0, nums.size() - 1);       }
};

23. 合并 K 个升序链表 - 力扣(LeetCode)

这道题其实跟之前的文件排序演示代码的逻辑没有本质区别,只不过这道题可以用到堆来加速。

class Solution {
public:struct CMP {bool operator()(ListNode *p, ListNode *q) {return p->val > q->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode *, vector<ListNode *>, CMP> q;for (auto x : lists) {if (x == nullptr) continue;q.push(x);}ListNode ret, *p = &ret;while (!q.empty()) {ListNode *cur = q.top();q.pop();p->next = cur;p = cur;if (cur->next) q.push(cur->next);}return ret.next;}
};

148. 排序链表 - 力扣(LeetCode)


 

如何用归并排序实现链表的排序呢?下面这段代码还是很具有典型意义的用链表来实现过程。

lass Solution {
public:ListNode *mergeSort(ListNode *head, int n) {if (head == nullptr || head->next == nullptr) return head;int l = n / 2, r = n - l;ListNode *lp = head, *rp = lp, *p;for (int i = 1; i < l; i++, rp = rp->next);p = rp, rp = rp->next;p->next = nullptr;lp = mergeSort(lp, l); // left Sortrp = mergeSort(rp, r); // right SortListNode ret;p = &ret;while (lp || rp) {if (rp == nullptr || (lp && lp->val < rp->val)) {p->next = lp;lp = lp->next;p = p->next;} else {p->next = rp;rp = rp->next;p = p->next;}}return ret.next;}ListNode* sortList(ListNode* head) {int n = 0;ListNode *p = head;while (p) p = p->next, n += 1;return mergeSort(head, n);}
};

1305. 两棵二叉搜索树中的所有元素 - 力扣(LeetCode)

用中序遍历,归并两颗子树,也是具有一定综合性的题。(怎么说的跟考研数学似的。。。)

class Solution {
public:void getResult(TreeNode *root, vector<int> &arr) {if (root == nullptr) return ;getResult(root->left, arr);arr.push_back(root->val);getResult(root->right, arr);return ;}vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {vector<int> lnums, rnums;getResult(root1, lnums);getResult(root2, rnums);vector<int> ret;int p1 = 0, p2 = 0;while (p1 < lnums.size() || p2 < rnums.size()) {if (p2 >= rnums.size() || (p1 < lnums.size() && lnums[p1] < rnums[p2])) {ret.push_back(lnums[p1++]);} else {ret.push_back(rnums[p2++]);}}return ret;}
};

327. 区间和的个数 - 力扣(LeetCode)

一说到区间和值,就能想到前缀和。区间和等于前缀和数组中两项相减的值。问题就变成了,前缀和数组中,有多少对 lower <= sun[i]-sum[j] <= upper (i>j)

利用左右区间的有序性,加速查找的过程。

算法解题过程的封装思维:当我们将问题转化成另一个问题的时候,我们就忘掉前面的问题到底是什么,只需专注解决当前这个独立的问题。而不是脑子里一团乱麻。

class Solution {
public:int countTwoPart(vector<long long> &sum, int l1, int r1, int l2, int r2, int lower, int upper) {int ans = 0, k1 = l1, k2 = l1;for (int j = l2; j <= r2; j++) {long long a = sum[j] - upper;long long b = sum[j] - lower;while (k1 <= r1 && sum[k1] < a) k1++;while (k2 <= r1 && sum[k2] <= b)k2++;ans += k2 - k1;}return ans;}int mergeSort(vector<long long> &sum, int l, int r, int lower, int upper) {if (l >= r) return 0; // 只有一个元素的话,根本找不到数值对。int mid = (l + r) >> 1, ans = 0;ans += mergeSort(sum, l, mid, lower, upper);ans += mergeSort(sum, mid + 1, r, lower, upper);ans += countTwoPart(sum, l, mid, mid + 1, r, lower, upper);int k = l, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if (p2 > r || (p1 <= mid && sum[p1] < sum[p2])) {temp[k++] = sum[p1++];} else {temp[k++] = sum[p2++];}}for (int i = l; i <= r; i++) sum[i] = temp[i];return ans; }vector<long long> temp;int countRangeSum(vector<int>& nums, int lower, int upper) {vector<long long> sum(nums.size() + 1);while (temp.size() < sum.size()) temp.push_back(0);sum[0] = 0;for (int i = 0; i < nums.size(); i++) sum[i + 1] = sum[i] + nums[i];return mergeSort(sum, 0, sum.size() - 1, lower, upper);}
};

本质上还是利用了分治的思想。核心的过程就是如何计算跨左右两半部分的过程

315. 计算右侧小于当前元素的个数 - 力扣(LeetCode)

已经求得左右半边各自比它小的元素。两个区间合并。

class Solution {
public:// 归并排序的思想:分两个区间,统计两个区间的性质。// 在归并的过程中,左右两个有序区间,合并的时候,从大到小的顺序排,左边区间内,如果元素大于右边,则左边的元素比他小的个数应当加上右边r-p2+1struct Data {Data(int val, int ind) : val(val), ind(ind), cnt(0) {}bool operator > (const Data &a) {return val > a.val;}int val, ind, cnt;};void mergeSort(vector<Data> &arr, int l, int r) {if (l >= r) return ; // 如果只剩下一个元素,那就计算不了左右两边的统计性质int mid = (l + r) >> 1;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);int k = l, p1 = l, p2 = mid + 1;while (p1 <= mid || p2 <= r) {if (p2 > r || (p1 <= mid && arr[p1] > arr[p2])) {arr[p1].cnt += r - p2 + 1;temp[k++] = arr[p1++];} else {temp[k++] = arr[p2++];}}for (int i = l; i <= r; i++) arr[i] = temp[i];return ;}vector<Data> temp;vector<int> countSmaller(vector<int>& nums) {vector<Data> arr;for (int i = 0; i < nums.size(); i++) arr.push_back(Data{nums[i], i});while (temp.size() < nums.size()) temp.push_back(Data{0, 0});mergeSort(arr, 0, arr.size() - 1);vector<int> ret(nums.size());for (auto x : arr) ret[x.ind] = x.cnt;return ret;}
};

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

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

相关文章

深度学习在MRI运动校正中的应用综述

运动是MRI中的主要挑战之一。由于MR信号是在频率空间中获取的&#xff0c;因此除了其他MR成像伪影之外&#xff0c;成像对象的任何运动都会导致重建图像中产生伪影。深度学习被提出用于重建过程的几个阶段的运动校正。广泛的MR采集序列、感兴趣的解剖结构和病理学以及运动模式&…

vue3使用vuex

VUEX官方文档,可以学习详细,这篇笔记是写vue2升级vue3后使用vuex,或者忘记如何使用vuex做状态管理的情况 vueX状态管理 Vue 3 与 Vue 2 有很多不同之处&#xff0c;但 Vuex 的核心概念——State、Getters、Mutations、Actions 和 Modules——保持基本一致。Vuex 4 是为 Vue 3 …

部署工业物联网可以选择哪些通信方案?

部署工业物联网有诸多意义&#xff0c;诸如提升生产效率&#xff0c;降低管理成本&#xff0c;保障生产品质稳定&#xff0c;应对长期从业劳动力变化趋势等。针对不同行业、场景&#xff0c;工业物联网需要选择不同的通信方案&#xff0c;以达到成本和效益的最佳平衡。本篇就简…

drawio----输出pdf为图片大小无空白(图片插入论文)

自己在写论文插入图片时为了让论文图片放大不模糊&#xff0c;啥方法都试了&#xff0c;最后摸索出来这个。 自己手动画图的时候导出pdf总会出现自己的图片很小&#xff0c;pdf的白边很大如下如所示&#xff0c;插入论文的时候后虽然放大不会模糊&#xff0c;但是白边很大会显…

开源了一套基于springboot+vue+uniapp的商城,包含分类、sku、商户管理、分销、会员、适合企业或个人二次开发

RuoYi-Mall-JAVA商城-电商系统简介 开源了一套基于若依框架&#xff0c;SringBoot2MybatisPlusSpringSecurityjwtredisVueUniapp的前后端分离的商城系统&#xff0c; 包含分类、sku、商户管理、分销、会员、适合企业或个人二次开发。 前端采用Vue、Element UI&#xff08;ant…

【C#】条码管理操作手册

前言&#xff1a;本文档为条码管理系统操作指南&#xff0c;介绍功能使用、参数配置、资源链接&#xff0c;以及异常的解决等。思维导图如下&#xff1a; 一、思维导图 二、功能操作–条码打印&#xff08;客户端&#xff09; 2.1 参数设置 功能介绍&#xff1a;二维码图片样…

正则表达式:贪婪与非贪婪模式

正则中的三种模式&#xff0c;贪婪匹配、非贪婪匹配和独占模式。 在这 6 种元字符中&#xff0c;我们可以用 {m,n} 来表示 &#xff08;*&#xff09;&#xff08;&#xff09;&#xff08;?&#xff09; 这 3 种元字符&#xff1a; 贪婪模式&#xff0c;简单说就是尽可能进行…

材料行业可以转IC设计后端吗?

近来有许多材料行业的小伙伴通过后台来问我对于职业规划的看法&#xff0c;甚至有些小伙伴直接点明了某个行业适不适合自己&#xff0c;那么我这边仅以近年来比较热门的数字芯片设计来展开讲讲&#xff0c;材料适不适合转行做IC呢。 对于理工科的同学而言&#xff0c;选择哪个…

Day14 01-Shell脚本编程详解

文章目录 第一章 Shell编程【重点】1.1. Shell的概念介绍1.1.1. 命令解释器4.1.1.2. Shell脚本 1.2. Shell编程规范1.2.1. 脚本文件的结构1.2.2. 脚本文件的执行 1.3. Shell的变量1.3.1. 变量的用法1.3.2. 变量的分类1.3.3. 局部变量1.3.4. 环境变量1.3.5. 位置参数变量1.3.6. …

前端-初始化Vue3+TypeScript

如果使用如下命令初始化项目&#xff0c;项目很干净&#xff0c;很适合了解项目的各个结构。 npm init vitelatest如果使用如下命令初始化项目&#xff0c;是可以选择你需要的组件 npm init vuelatest

SpringBoot系列之集成Resteasy实现RESTFul接口

JAX-RS&#xff1a;JavaAPI for RESTful Web Services&#xff0c;JAX-RS是可以用可以用于实现RESTFul应用程序的JAVA API&#xff0c;给开发者提供了一系列的RESTFul注解 EasyRest&#xff1a;这是Jboss开源的&#xff0c;一款用来定义实现RESTFul应用程序的框架&#xff0c;…

ASP.NET WEB API通过SugarSql连接MySQL数据库

注意&#xff1a;VS2022企业版可以&#xff0c;社区版可能存在问题。实体名称和字段和数据库中的要一致。 1、创建项目&#xff0c;安装SqlSugarCore、Pomelo.EntityFrameworkCore.MySql插件 2、文件结构 2、appsettings.json { “Logging”: { “LogLevel”: { “Default”: …

.netcore grpc身份验证和授权

一、鉴权和授权&#xff08;grpc专栏结束后会开启鉴权授权专栏欢迎大家关注&#xff09; 权限认证这里使用IdentityServer4配合JWT进行认证通过AddAuthentication和AddAuthorization方法进行鉴权授权注入&#xff1b;通过UseAuthentication和UseAuthorization启用鉴权授权增加…

YOLO系列解读DAY2—YOLOV1预测代码转换

一、说在前面 小伙伴们好&#xff0c;博主很久没有写博客了&#xff0c;略感生疏&#xff0c;不到之处敬请谅解&#xff0c;欢迎指出文中错误&#xff0c;大家一起探讨。欲看视频讲解&#xff0c;可转至博主DouYin、B站&#xff0c;欢迎关注&#xff0c;链接如下&#xff1a; …

Dockerfile自定义镜像

文章目录 Dockerfile自定义镜像镜像结构Dockerfile语法构建java项目 小结 Dockerfile自定义镜像 常见的镜像在DockerHub就能找到&#xff0c;但是我们自己写的项目就必须自己构建镜像了。 而要自定义镜像&#xff0c;就必须先了解镜像的结构才行。 镜像结构 镜像是将应用程序及…

java知识-JVM线程四大引用

一、JVM (1) 基本概念&#xff1a; JVM 是可运行 Java 代码的假想计算机 &#xff0c;包括一套字节码指令集、一组寄存器、一个栈、 一个垃圾回收&#xff0c;堆 和 一个存储方法域。JVM 是运行在操作系统之上的&#xff0c;它与硬件没有直接 的交互。 (2) 运行过程&#x…

File 类的用法, InputStream和Reader, OutputStream和Writer 的用法

前言 普通的文件长这样&#xff1a; 其实目录也是一种特殊文件&#xff1a; 一、文件前缀知识 &#xff08;一&#xff09;绝对路径和相对路径 以盘符开头的的路径&#xff0c;叫做绝对路径&#xff0c;如&#xff1a;D:\360Downloads\cat.jpg 以.或..开头的路径&#xff0c…

华为认证为什么现在这么受欢迎?

华为认证目前受欢迎的原因有很多&#xff0c;以下是其中一些主要原因&#xff1a; 高质量的认证培训&#xff1a;华为认证提供了一系列高质量的培训课程&#xff0c;涵盖了IT技术、网络安全、云计算等领域。这些培训课程由华为的技术专家和工程师团队设计和提供&#xff0c;内容…

编程练习(3)

一.选择题 第一题&#xff1a; 函数传参的两个变量都是传的地址&#xff0c;而数组名c本身就是地址&#xff0c;int型变量b需要使用&符号&#xff0c;因此答案为A 第二题&#xff1a; 本题考察const修饰指针变量&#xff0c;答案为A,B,C,D 第三题&#xff1a; 注意int 型变…

回到未来:使用马尔可夫转移矩阵分析时间序列数据

一、说明 在本文中&#xff0c;我们将研究使用马尔可夫转移矩阵重构时间序列数据如何产生有趣的描述性见解以及用于预测、回溯和收敛分析的优雅方法。在时间上来回走动——就像科幻经典《回到未来》中 Doc 改装的 DeLorean 时间机器一样。 注意&#xff1a;以下各节中的所有方程…