游客您好
第三方账号登陆
  • 点击联系客服

    在线时间:8:00-16:00

    客服电话

    020-85534346

    电子邮件

    81058337@qq.com
  • 码云社APP

    随时掌握码云社动态

  • 扫描二维码

    关注砺锋微信公众号

推荐阅读
aa12345789 初出江湖
未知星球 | 未知职业
  • 圣诞老人

    圣诞节自动颁发
  • 金猪

    猪年自动颁发
  • 五一勋章

    五一劳动节在线用户
  • 优质作者

    在社区持续发表优质文章
  • 关注0
  • 粉丝0
  • 帖子2

算法:什么是外部排序

[复制链接]
aa12345789 发表于 1970-1-1 08:14:48 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
点击上方关注,每天学习一个java知识点
原创:苦逼的码农
背景
西天取经的路上,一样上演着编程的乐趣.....


a8fBOa9ckKAvt9v8.jpg









G8joOOM356XxzmJA.jpg





(互联网侦察注:160亿字节大概是16G吧,20亿int32大概8G)
DXPddPPC6ZIiGQdK.jpg





A3oZa3sago03Oso3.jpg





nK8N88SiZP18p81P.jpg





pMN8NnNnrN6lkKwp.jpg





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


o02MEG06qgSrT6Fr.jpg





注意:读取的时候是每次读取一个int数,通过比较之后在输出。
按照这个方法来回合并,总共经过三次合并之后就可以得到8G的有序子串。


uikKKGomte781QEE.jpg





U99A9FfY05u8PU56.jpg





jc2ocMKPc2o6Xsek.jpg







接下来把12个数据分成4份,然后排序成有序子串


wtPXGB44nZ973SBm.jpg







然后把子串进行两两合并


eEPdiz5KQ5ok7n78.jpg







输出哪个元素,就在那个元素所在的有序子串再次读入一个元素


RETCA2MT2e2XTBFE.jpg







继续


W97e4rD34r7qy6ym.jpg







重复直到合并成一个包含6个int的有序子串


ghYtxsxiSiNdUUIO.jpg







再把两个包含6个int的有序子串合并成一个包含12个int数据的最终有序子串


MdmxYjbprDXmZpmM.jpg





Qb22xGk542OXQryL.jpg







优化策略


Y4KV9VVWgXS42ZSg.jpg





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


y78x32xsa5J02xS7.jpg







SFIZQdNFcf97a7CQ.jpg







S872En7f12Sl81T9.jpg





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




Yqq47o4bYBf5Iy0z.jpg







WGg0idFawZFbC50S.jpg





snn6U1n6T9a2925W.jpg







eifLCK7Zbzit5BXI.jpg







bE0LR07gbIyXWC97.jpg





vzXxqyyQCu177SDl.jpg







z727O24003pK71Zz.jpg





置换选择


lO0V14Yy5z53b0MA.jpg









Y8B9Fc8zBaKl9zBB.jpg





msi0ZIstkTimE0IS.jpg







sAfz343YYYt34GPg.jpg





rZnqdlJkhkJyYijL.jpg





udeX35T22sDh6z2T.jpg





qNolAB6nn6ynS8b3.jpg





例如我们可以从12个数据读取3个存到内存中,然后从内存中选出最小的那个数放进子串p1里;
之后再从在从剩余的9个数据读取一个放到内存中,然后再从内存中选出一个数放进子串p1里,这个数必须满足比p1中的其他数大,且在内存中尽量小
这样一直重复,直到内存中的数都比p1中的数小,这时p1子串存放结束,继续来p2子串的存放。例如(这时假设内存只能存放3个int型数据):
12个无序的int数据


Vwt65jeqP6wrqJri.jpg





读入3个到内存中,且选出一个最小的到子串p1


s0YzY90980Ly4YbC.jpg





从内存中再次读取一个元素86


UbQSS8x7X8d5aqQy.jpg





从内存中再次读取一个元素3


x6ulRWVvzqvHU882.jpg





从内存中再次读取一个元素24


I4VWvV4zVZFHHvu4.jpg





从内存中再次读取一个元素8


ySx40SPXjZPNBPS7.jpg





这个时候,已经没有符合要求的数了,且内存已满,进而用p2子串来存放,以此类推。
通过这种方法,p1子串存放了4个数据,而原来的那种方法p1子串只能存放3个数据。


OcA58Mf5MuFu4z5h.jpg







IZjj2qY052RGYdXX.jpg





(不知道堆排序的可以看下我之前写的文章:【算法与数据结构】堆排序是什么鬼?)
从12个数据中读取3个数据,构建成一个最小堆,然后从堆顶选择一个数写入到p1中。
之后再从剩余的9个数中读取一个数,如果这个数比刚才那个写入到p1中的数大,则把这个数插入到最小堆中,重新调整最小堆结构,然后在堆顶选一个数写入到p1中。
否则,把这个数暂放在一边,暂时不处理。之后一样需要调整堆结构,从堆顶选择一个数写入到p1中。
这里说明一下,那个被放在一边的数是不能再放入p1中的了,因为它一定比p1中的数都要小,所以它会放在下一个子串中
看这些文字会让人头大,我画图解释下吧。
从12数据读取3个数据


MzwWHk5WXQHoQEOG.jpg





构建最小堆,且选出目标数


Nl8xfR0R0kVWRWgV.jpg





读入下一个数86


G0va0o05AL0krG0h.jpg





读入下一个数3,比70小,暂放一边,不加入堆结构中


WLtVCd6G56lDZS6l.jpg





读入下一个数据24,比81小,不加入堆结构


Ci8uSOd3YwWAW1WD.jpg





读入下一个数据8,比86小,不加入堆结构。此时p1已经完成了,把那些刚才暂放一边的数重新构成一个堆,继续p2的存放。


x2d1ytnvcNumnOvY.jpg





以此类推...
最后生成的p2如下:


HTs45ZIaz28XSByj.jpg







N5TfodTHBp5LPlfo.jpg







Ks1AITgtk1hAT2Au.jpg







Fk99XzEUxqx9XE69.jpg





(注:这里作者笔误,应该是2n)


iR8xx8878Ok75K8t.jpg





这种方法适合要排序的数据太多,以至于内存一次性装载不下。只能通过把数据分几次的方式来排序,我们也把这种方法称之为外部排序


VE1wwwkQ9KZV669K.jpg
码云社-用代码改变世界!
回复 关闭延时

使用道具 举报

精彩评论20

1341313635 发表于 2019-4-3 16:26:32 | 显示全部楼层
之前那两只仓鼠哪里去了
码云社-用代码改变世界!
回复

使用道具 举报

xz真相 发表于 2019-4-3 16:29:17 | 显示全部楼层
转发了
码云社-用代码改变世界!
回复

使用道具 举报

大河的大河 发表于 2019-4-3 16:32:31 | 显示全部楼层
搞笑啊
码云社-用代码改变世界!
回复

使用道具 举报

hy4334011 发表于 2019-4-3 16:35:47 | 显示全部楼层
都来看图片了,谁看你的算法?你以为你这样我就学得会啦![机智][机智]
码云社-用代码改变世界!
回复

使用道具 举报

1341313635 发表于 2019-4-3 16:38:52 | 显示全部楼层
转发了
码云社-用代码改变世界!
回复

使用道具 举报

Zz_文诗 发表于 2019-4-3 16:42:00 | 显示全部楼层
转发了
码云社-用代码改变世界!
回复

使用道具 举报

macauslot 发表于 2019-4-3 16:44:49 | 显示全部楼层
转发了
码云社-用代码改变世界!
回复

使用道具 举报

趁早起飞 发表于 2019-4-3 16:47:41 | 显示全部楼层
转发了
码云社-用代码改变世界!
回复

使用道具 举报

执行力 发表于 2019-4-3 16:51:13 | 显示全部楼层
转发了
码云社-用代码改变世界!
回复

使用道具 举报

高级模式
B Color Image Link Quote Code Smilies 上传

本版积分规则

CODESEEDING(码云社)一家致力于程序员成长、以内容为核心、以提问为引导的多元化成长社区。我们在线上为技术爱好者提供了一个优质的交流氛围环境,在线下同样和众多高校联合开办了技术沙龙品牌。
020-85534346
关注我们
  • 访问移动H5版
  • 官方微信公众号

码云社 - CODESEEDING 2.0© 2018-2019 码云社. TOOBUG ( 粤ICP备16114193号-3 )