【漫画】什么是外部排序？

我不是女神ヾ 2021-09-30 22:38 337阅读 0赞

> 公众号来源：苦逼的码农  作者：帅地
> 
> 通过漫画的方式通俗易懂讲解什么是外部排序，建议阅读！

背景

西天取经的路上，一样上演着编程的乐趣.....

![640][]

![640][640 1]

![640][640 2]

> 地哥笔误：40亿字节不是占8G，而是大概占16G

![640][640 3]

![640][640 4]

![640][640 5]

![640][640 6]

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

![640][640 7]

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

按照这个方法来回合并，总共经过三次合并之后就可以得到8G的有序子串。

![640][640 8]

![640][640 9]

![640][640 10]

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

![640][640 11]

然后把子串进行两两合并

![640][640 12]

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

![640][640 13]

继续

![640][640 14]

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

![640][640 15]

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

![640][640 16]

![640][640 17]

**优化策略**

![640][640 18]

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

![640][640 19]

![640][640 20]

![640][640 21]

**多路归并**

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

![640][640 22]

![640][640 23]

![640][640 24]

![640][640 25]

![640][640 26]

![640][640 27]

![640][640 28]

**置换选择**

![640][640 29]

![640][640 30]

![640][640 31]

![640][640 32]

![640][640 33]

![640][640 34]

![640][640 35]

例如我们可以从12个数据读取3个存到内存中，然后从内存中选出最小的那个数放进子串p1里；

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

这样一直重复，直到内存中的数都比p1中的数小，这时p1子串存放结束，继续来p2子串的存放。

> ps：我看的时候没看懂为啥有上面几条规则，于是跑去问了一下地哥。地哥的回答：在构造一个子串的时候，因为我们必须保存字串是“有序”的，所以我们从内存中选出的数，必须要比“上一次”选的数小。

例如(***这时假设内存只能存放3个int型数据***)：

12个无序的int数据

![640][640 36]

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

![640][640 37]

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

![640][640 38]

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

![640][640 39]

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

![640][640 40]

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

![640][640 41]

这个时候，已经没有符合要求的数了，且内存已满，进而用p2子串来存放，以此类推。

通过这种方法，p1子串存放了4个数据，而原来的那种方法p1子串只能存放3个数据。

![640][640 42]

![640][640 43]

(不知道堆排序的可以看下我之前写的文章：[【算法与数据结构】堆排序是什么鬼？][Link 1])

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

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

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

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

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

从12数据读取3个数据

![640][640 44]

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

![640][640 45]

读入下一个数86

![640][640 46]

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

![640][640 47]

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

![640][640 48]

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

![640][640 49]

以此类推...

最后生成的p2如下：

![640][640 50]

![640][640 51]

![640][640 52]

![640][640 53]

![640][640 54]

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

![640][640 55]

![640][640 56]

**- End -**

推荐阅读：

[TensorFlow读写数据][TensorFlow]  
[为什么有些网站域名不以www开头？什么是二级域名？][www]

> 乐于输出**干货**的Java技术公众号：Java3y。公众号内有200多篇**原创**技术文章、海量视频资源、精美脑图，不妨来**关注**一下！

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

有帮助？好看！转发！![640][640 57]

[640]: /images/20210827/52a19e95c59b48999847bfdfcf9931df.png
[640 1]: /images/20210827/2c77b97f902c410d9b4e8b76ef715ae2.png
[640 2]: /images/20210827/6ef2c66509424c22a8129bbdcb6aece2.png
[640 3]: /images/20210827/1333e6e84d664b6e9db45aacbb68c736.png
[640 4]: /images/20210827/d8b61a9e38ad4b23ab06aca5aee30206.png
[640 5]: /images/20210827/f4f640fbfcb84c37a8307816516d810b.png
[640 6]: /images/20210827/b5c40acbd83f4d96b9e3a71cd977a5c3.png
[640 7]: /images/20210827/6ad0db91d8aa43e38b00906680eaca00.png
[640 8]: /images/20210827/b1afc07be0264dda9389dcb6252f3350.png
[640 9]: /images/20210827/350d5ae7699d46b69fb37eb7a6347649.png
[640 10]: /images/20210827/24639b9271794246b0b42d5c2cd51596.png
[640 11]: /images/20210827/b82a095b84a34b128acfd5bf862b7eca.png
[640 12]: /images/20210827/8ffcd5a7ecff41f9a8565c4bc8f45a8f.png
[640 13]: /images/20210827/dd201ba1720d49a581793a8b4962bf34.png
[640 14]: /images/20210827/a07420f9b601418ab571ba0f6a3fae80.png
[640 15]: /images/20210827/e1ed3811a5f4404a84a5a72298c41e3f.png
[640 16]: /images/20210827/068a18c0f9a14c03a5981628e4012676.png
[640 17]: /images/20210827/df26229f46904b3d89b624a3e7ae51d9.png
[640 18]: /images/20210827/72c012b73c93441b8a749c71776d2ba2.png
[640 19]: /images/20210827/c2d7ae349dba49fe998cd72b456061fc.png
[640 20]: /images/20210827/82c668cbadb64e09a72909ab66413959.png
[640 21]: /images/20210827/cddb4732312a42879287e7ede9083d53.png
[640 22]: /images/20210827/7d82a31c2cdd416790266fffbdbd0b5f.png
[640 23]: /images/20210827/a25d7d5ab5f3441397eef19dceac147f.png
[640 24]: /images/20210827/9978d0f5f8074b56bc499cbf40cdd66a.png
[640 25]: /images/20210827/2ed31068dd93491c84ca38c4cb1587f4.png
[640 26]: /images/20210827/8f2fb8e45cdc4af18d8284582383ac1c.png
[640 27]: /images/20210827/0b962cfac3464c789998a165dd3c33d8.png
[640 28]: /images/20210827/f6e2dda7ac344c6fb7d0de5af191b0da.png
[640 29]: /images/20210827/d98fa1e7192045e4857fe7c33fd88cc5.png
[640 30]: /images/20210827/7f7541aa4784447b91ab6aeafd5ceaf7.png
[640 31]: /images/20210827/b9de1566460147e3a5a89a05e7ab9c9e.png
[640 32]: /images/20210827/0f9177580b5a4082b8b8e882c9cfb1b9.png
[640 33]: /images/20210827/9afe7a9081974b5bb7b033173b59d740.png
[640 34]: /images/20210827/6994388c42fb4e3cbf8b3adf3192d10a.png
[640 35]: /images/20210827/f66315a9179b47a7aeb2ff37ebc9941f.png
[640 36]: /images/20210827/29c97d7101ef41d4b3d27a9b11fcaad2.png
[640 37]: /images/20210827/d336de11e8554ff4bfcb2f32b2c92967.png
[640 38]: /images/20210827/c09111077edd4cdfbb69d6a1be2b9456.png
[640 39]: /images/20210827/076be2eb77d443ce9e0bce322f511345.png
[640 40]: /images/20210827/855a9d7a4a3a4905bb2df6c0ca2779c8.png
[640 41]: /images/20210827/3e008aa1cdca40cb9a0b4dec411fb6d6.png
[640 42]: /images/20210827/3c7fed6e80994e75969ce4cc48547ec7.png
[640 43]: /images/20210827/9fa738fa502e4aac86a8e734ffb2fa86.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUxNzg0MDc1Mg==&mid=2247484222&idx=1&sn=2a3d3f0e95df9d1fdcc2e21123721e66&chksm=f9934921cee4c037fe37eb9a27454f095376117985187867b09bd95b564e4941956ead73ed93&scene=21#wechat_redirect
[640 44]: /images/20210827/857c383b41b741c1a005f1f6275fc118.png
[640 45]: /images/20210827/71b8e20098a94796a0a1605e33892f7c.png
[640 46]: /images/20210827/44b353388fc7479ca06b28b9e00586f9.png
[640 47]: /images/20210827/ab7a81220b724fc48ca036e544e6829b.png
[640 48]: /images/20210827/c14c5adbaafa4e1cbefabc0d1ca9a226.png
[640 49]: /images/20210827/615815afa16a4455b3865f3a1f34bf0c.png
[640 50]: /images/20210827/3e16cf41914945c6917d0e91de0263e7.png
[640 51]: /images/20210827/7e52f05ecb7f46b38ffca214a8e857a1.png
[640 52]: /images/20210827/e48f1fd301e94bf8af3f07dcc9bb3065.png
[640 53]: /images/20210827/037293da442448f18a7db7516d6224a4.png
[640 54]: /images/20210827/9cad81804d2542ea9e4dbbbf550cafb7.png
[640 55]: /images/20210827/8933eb1829fb41368a54a41a44ba56c6.png
[640 56]: /images/20210827/088610f3a69e431fba6c69ffb68f2069.png
[TensorFlow]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484984&idx=1&sn=b11d353aa5aa9e7964c715f5ab7d4ddd&chksm=ebd74739dca0ce2f82f21586531a03effe69d78ab21671d116ffb56aa6f1220e5a3028d1bc5e&token=522477157&lang=zh_CN&scene=21#wechat_redirect
[www]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484968&idx=1&sn=af9d31c0ed6e4b972af08be7b57bb451&chksm=ebd74729dca0ce3fd02abfe47534b3c77ede43ce3032e737426cd7f07e26f3780f542b098851&token=522477157&lang=zh_CN&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20210827/a04bbf857cb64554a01c7f1d2236c2b1.png?wx_fmt=jpeg
[640 57]: /images/20210827/50522b3a8ec047e8b6d1a9df2d5ab98c.png