【漫画+图解】面试官让我用 2GB 内存给 20亿个整数(需要8GB内存)排序,我该咋整??

news/2024/10/31 5:31:03/

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
排序的时候我们可以选择快速排序或归并排序等算法。为了方便,我们把排序好的2G有序数据称之为有序子串吧。接着我们可以把两个小的有序子串合并成一个大的有序子串。
在这里插入图片描述

注意:读取的时候是每次读取一个int数,通过比较之后在输出。

按照这个方法来回合并,总共经过三次合并之后就可以得到8G的有序子串。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
接下来把12个数据分成4份,然后排序成有序子串
在这里插入图片描述
然后把子串进行两两合并
在这里插入图片描述
输出哪个元素,就在那个元素所在的有序子串再次读入一个元素
在这里插入图片描述
继续
在这里插入图片描述
重复直到合并成一个包含6个int的有序子串
在这里插入图片描述
再把两个包含6个int的有序子串合并成一个包含12个int数据的最终有序子串
在这里插入图片描述
在这里插入图片描述

优化策略

在这里插入图片描述

解释下:例如对于数据2,我们把无序的12个数据分成有序的4个子串需要读写各一次,把2份3个有序子串合并成6个有序子串读写各一次;把2份6个有序子串合并从12个有序子串读写各一次,一共需要读写各3次。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

多路归并

为了方便讲解,我们假设内存一共可以装4个int型数据。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

置换选择

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
例如我们可以从12个数据读取3个存到内存中,然后从内存中选出最小的那个数放进子串p1里;

之后再从在从剩余的9个数据读取一个放到内存中,然后再从内存中选出一个数放进子串p1里,这个数必须满足比p1中的其他数大,且在内存中尽量小

这样一直重复,直到内存中的数都比p1中的数小,这时p1子串存放结束,继续来p2子串的存放。例如(这时假设内存只能存放3个int型数据):

12个无序的int数据
在这里插入图片描述
读入3个到内存中,且选出一个最小的到子串p1
在这里插入图片描述
从内存中再次读取一个元素86
在这里插入图片描述
从内存中再次读取一个元素3
在这里插入图片描述
从内存中再次读取一个元素24
在这里插入图片描述
从内存中再次读取一个元素8
在这里插入图片描述
这个时候,已经没有符合要求的数了,且内存已满,进而用p2子串来存放,以此类推。

通过这种方法,p1子串存放了4个数据,而原来的那种方法p1子串只能存放3个数据。
在这里插入图片描述
在这里插入图片描述

不知道堆排序的可以看下我之前写的文章 : 堆排序是什么鬼?

从12个数据中读取3个数据,构建成一个最小堆,然后从堆顶选择一个数写入到p1中。

之后再从剩余的9个数中读取一个数,如果这个数比刚才那个写入到p1中的数大,则把这个数插入到最小堆中,重新调整最小堆结构,然后在堆顶选一个数写入到p1中。

否则,把这个数暂放在一边,暂时不处理。之后一样需要调整堆结构,从堆顶选择一个数写入到p1中。

这里说明一下,那个被放在一边的数是不能再放入p1中的了,因为它一定比p1中的数都要小,所以它会放在下一个子串中

看这些文字会让人头大,我画图解释下吧。

从12数据读取3个数据
在这里插入图片描述
构建最小堆,且选出目标数
在这里插入图片描述
读入下一个数86
在这里插入图片描述
读入下一个数3,比70小,暂放一边,不加入堆结构中
在这里插入图片描述
读入下一个数据24,比81小,不加入堆结构
在这里插入图片描述
读入下一个数据8,比86小,不加入堆结构。此时p1已经完成了,把那些刚才暂放一边的数重新构成一个堆,继续p2的存放。
在这里插入图片描述
以此类推…
最后生成的p2如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这种方法适合要排序的数据太多,以至于内存一次性装载不下。只能通过把数据分几次的方式来排序,我们也把这种方法称之为外部排序

在这里插入图片描述

另外,帅地把公众号的精华文章整理成了一本电子书,共 630页!目录如下

在这里插入图片描述

现在免费送给大家,在我的公众号帅地玩编程回复程序员内功修炼即可获取。

兄dei,如果觉得我写的不错,不妨帮个忙

1、关注我的原创微信公众号「帅地玩编程」,每天准时推送干货技术文章,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux),听说关注了的不优秀也会变得优秀哦。

2、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

作者简洁

作者:大家好,我是帅地,从大学、自学一路走来,深知算法计算机基础知识的重要性,所以申请了一个微星公众号『帅地玩编程』,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习。 转载说明:未获得授权,禁止转载


http://www.ppmy.cn/news/332803.html

相关文章

2.2 搭建Spark开发环境

一、Spark开发环境准备工作 由于Spark仅仅是一种计算框架,不负责数据的存储和管理,因此,通常都会将Spark和Hadoop进行统一部署,由Hadoop中的HDFS、HBase等组件负责数据的存储管理,Spark负责数据计算。 安装Spark集群前…

数据可视化学习笔记:Python实现汽车品牌销售量矩形树图

引言 本文将介绍如何使用 Python 和 Pyecharts 库创建一个汽车品牌销售量的矩形树图。我们将使用 Pandas 读取 CSV 文件数据,然后对数据进行处理、封装,最后将数据可视化为矩形树图。 准备工作 首先,我们需要先安装好相关库: PandasPyecharts可以使用 pip 命令进行安装:…

自己制作一寸照片

用ps制作1寸照片 一,文件–打开一张照片。 二,点击裁剪工具 (调整为宽:2.5cm,高:3.5cm,分辨率:300像素,注高版本ps记住选择厘米像素),设置之后直接框选出需要剪切保留的位置(使人物居正中), 然后按上面的“…

PS二寸证件照制作

一、新建画布 文件——>新建 二寸证件照尺寸:3.5✖5.3 厘米 / 413✖626 像素、分辨率为300 像素/英寸 一寸证件照尺寸:2.5✖3.5 厘米 / 295✖413 像素、分辨率为300 像素/英寸 小二寸证件照尺寸:3.3✖4.8 厘米 / 390✖567 像素、分辨率为…

使用django的APP在前端上传excel通过post传给后端读取并打印

文章目录 前言前端后端 前言 备研了&#xff0c;博客许久未更了&#xff0c;但是学期末的大作业&#xff0c;遇到了问题并成功解决了&#xff0c;不得不记录一下。 前端 <form method"post" enctype"multipart/form-data" action"/insurance/up…

将照片改成一寸照

第一步&#xff1a;打开电脑画图 第二步&#xff1a;选择“重新调整大小” 第三步&#xff1a;去掉“保持纵横比“的对勾 第四部&#xff1a;选择“像素”&#xff0c;输入295,413 第五步&#xff1a;选择图片&#xff0c;另存为 完成

如何用手机制作一寸或二寸证件照?

日常生活中&#xff0c;大家出门办业务的时候除了会用到身份证之外还会经常用到一寸或二寸照片。那么&#xff0c;你知道如何用手机制作一寸或二寸照吗&#xff1f;今天就以一寸照为例&#xff0c;给大家分享一招手机制作电子一寸照的方法&#xff0c;操作步骤如下&#xff1a;…

照片怎么设置成1寸大小?修改图片像素大小的方法

我们在网上填写个人简历的时候&#xff0c;需要提交1寸个人照片&#xff0c;如果没有这个尺寸的照片怎么办呢&#xff1f;能不能自己修改图片尺寸呢&#xff1f;今天就教给大家一个可以把图片修改到一寸大小的方法&#xff0c;1寸照片尺寸为295*413&#xff0c;通过图片改大小&…