【面试】问当需要排序的数据量很大,但是电脑内存很小,如何实现排序?

b站学习资源:【天勤考研】外部排序1, 【天勤考研】外部排序2, 【天勤考研】外部排序3

此时我们就需要利用 外存 进行排序,简称 外部排序

多路归并排序

首先,我们知道 二路归并排序,就是把两个有序序列 归并成一个有序序列。

  • 1 4 5 9		\
    			 -> 1 2 3 4 5 7 8 9
    2 3 7 8     /
    

多路归并排序,就是将 多个有序序列归并成一个序列,每次从 每个序列头部取出一个元素,然后取出最值,进行排序。

通过上面案例,可以发现,每次比较 都只选则出每个序列的第一个元素,从中得到最大值。假设有 n 个序列,则 我们每次 只需要处理 n 个值。剩余的值,等下到下一次比较处理。所以,我们可以通过每次从外存中 读入每个序列的 头元素,进行排序。

  • 这里设我们 内存只能存 3 个整数,我们需要对长度 为 9 的序列进行排序。

  • 2 5 7 9 1 4 2 0 3
    // 每次从代排序序列中读取,前三数,然后取出最值。就会生成三个如下的有序序列
    2 5 7
    1 4 9
    0 2 3
    // 得到三个有序序列,后我们就可以利用多路归并排序,一次从序列中读取头部元素,进行比较取出最值归并
    [2, 1, 0] -> [2, 1, empty]
    [0] -> merge queue
    5 7
    4 9
    2 3
    // 然后在从 第三个序列中读取一个元素
    [2, 1, 2] -> [2, empty, 2]
    [0, 1] -> merge queue
    5 7
    4 9
    3
    // 然后从第二个序列中读取取出头元素
    [2, 3, 2] -> [empty, 3, 2]
    [0, 1, 2] -> merge queue
    5 7
    9
    3
    // 然后从第一个序列中取出头元素
    [5, 3, 2] -> [5, 3, empty]
    [0, 1, 2, 2] -> merge queue
    7
    9
    3
    // 然后从 第三个序列中取出头元素
    [5, 3, 3] -> [5, empty, 3]
    [0, 1, 2, 2, 3] -> merge queue
    7
    9
    empty
    // 然后从第二个序列取出头元素
    [5, 9, 3] -> [5, 9, empty]
    [0, 1, 2, 2, 3, 3] -> merge queue
    7
    empty
    empty
    // 然后遇到为空的序列则不操作
    [5, 9, 7] -> [empty, 9, empty]
    [0, 1, 2, 2, 3, 3, 5] -> merge queue
    empty
    empty
    empty
    // 最后处理剩余数字
    [0, 1, 2, 2, 3, 3, 5, 7, 9] -> merge queue
    
  • 这个过程中,通过频繁的读写外存实现排序。不过对于每个关键字都会执行 四次 IO 操作,2次读取,2次写入。通过分析,我们知道将归并段的长度设置更长,IO 操作就更少。

如何设置归并段呢

通过 置换选则排序 计算归并段

  • 设我们的内存能够读入 4 个数。

    • // 我们要进行归并分段的序列如下
      [7, 10, 2, 4, 19, 5, 9, 11, 22, 9, 10, 11, 12, 13]
      // 当 读入的个数 小于 4 的时候,就从该序列头部取出元素,放入内存中。过程大致如下
      [7, 10, 2, 4] -> [7, 10, empty, 4]
      [2]
      // ----
      [7, 10, 19, 4] -> [7, 10, 19, empty]
      [2, 4]
      // ---
      [7, 10, 19, 5] -> [7, 10, 19, empty]
      [2, 4, 5]
      // ---
      [7, 10, 19, 9] -> [empty, 10, 19, 9]
      [2, 4, 5, 7]
      // ---
      [11, 10, 19, 9] -> [11, 10, 19, empty]
      [2, 4, 5, 7, 9]
      // ---
      [11. 10, 19, 22] -> [11, empty, 19, 22]
      [2, 4, 5, 7, 9, 10]
      // --- 注意 此时 9 虽然是 4个中最小的数,但是它小于当前排序序列尾部的数,所以我们将他标记不进行比较
      [11, 9, 19, 22] -> [empty, 9x, 19, 22]
      [2, 4, 5, 7, 9, 10, 11]
      // --- 10 标记
      [10, 9x, 19, 22] -> [10x, 9x, empty, 22]
      [2, 4, 5, 7, 9, 10, 11, 19]
      // --- 11 标记
      [10x, 9x, 11, 22] -> [10x, 9x, 11x, empty]
      [2, 4, 5, 7, 9, 10, 11, 19, 22]
      // --- 12 标记, 此时内存中的所有的数都被标记了,所以我们新开一个文件,并取消标记继续排序
      [10x, 9x, 11x, 12] -> [10x, 9x, 11x, 12x] 
      [2, 4, 5, 7, 9, 10, 11, 19, 22]
      []
      // ---
      [10, 9, 11, 12] -> [10, empty, 11, 12] 
      [2, 4, 5, 7, 9, 10, 11, 19, 22]
      [9]
      // ---
      [10, 13, 11, 12] -> [empty, 13, 11, 12] 
      [2, 4, 5, 7, 9, 10, 11, 19, 22]
      [9, 10]
      // --
      [empty, empty, empty, empty] 
      [2, 4, 5, 7, 9, 10, 11, 19, 22]
      [9, 10, 11, 12, 13]
      
  • 上面就完成归并段的排序,并且尽可能让归并段变得更长,以减少IO操作的可能。不过这个情况下,得到的归并段的长度是不相等的。为了减少 关键字的IO操作次数,我们需要让长度最段的归并段的先归并。

通过 HuffmanTree 生成最佳归并树

  • 长度最大的归并段,距离根节点最进。每次将当前几个长度最少的归并段归并。最后会生成一颗树,该树的特点是长度越大的归并段,距离根越近。如下图
  • image-20230110131608471

通过败者树选则最值

局部修复过程,远小于构建一颗树。

  • 建树:
    • 首先,我们有 [17, 5, 10, 29, 15] 这组关键字等待我们找出最值。我们首先为每个值生成一个节点,作为其父节点。
      • image-20230110131951832
    • 然后,把这些独立的树合并成一颗树
      • 以 前两颗树为例,我们从中比较 arr[0] 和 arr[1], 然后,用较大的值的根节点作为,另一个值的根节点,然后,将较小值的根节点,设置为当前较大值的根节点。
        • image-20230110132330400
      • 然后重复操作
        • arr[3] 和 arr[4] 比较
          • image-20230110132419860
        • arr[1] 和 arr[2] 比较
          • image-20230110132514134
        • arr[1] 和 arr[4] 比较
          • image-20230110132540124

构建完败者树,后我们挑选出一个最值,也就是根节点所指向的值,进行归并。然后,从这个归并段的后一个值补上,最后,调整败者树。

  • image-20230110132753595

    • 上图,拿出了最值 5, 然后用 44 补上该位置。
  • 调整,我们先把 1, 拿出来,然后把 arr[1] 所在的子树,给拿出来

    • image-20230110132939012

    • 调整,局部重新建立败者树,将局部重新还原成合并前的状态。

    • image-20230110133047940

    • 重新合并

    • image-20230110133108008

    • 然后,拿出其他残缺的节点进行合并。

      • image-20230110133224995

然后重复执行这个操作就行了。最后就排序就完成了。