欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【漫画】什么是外部排序?【转】

程序员文章站 2022-11-06 20:39:31
"漫画,什么是外部排序" 还记得面试现场第一篇文章【面试现场】如何判断一个数是否在40亿个整数中?发出之后,最后蛋哥说把40亿个数先进行外部排序。有读者问到,内存无法一次性加载40亿个数,如何排序? 背景 西天取经的路上,一样上演着编程的乐趣..... (互联网侦察注:160亿字节大概是16G吧,2 ......

还记得面试现场第一篇文章【面试现场】如何判断一个数是否在40亿个整数中?发出之后,最后蛋哥说把40亿个数先进行外部排序。有读者问到,内存无法一次性加载40亿个数,如何排序?

背景

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

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

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

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

置换选择

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

例如我们可以从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如下:

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

【漫画】什么是外部排序?【转】

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