Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 1、带、盘的平衡多路归并的性质： ·eg:K>2时，趟数将会减少。m个归并串。总共n个记录。 合并段1 合并段k 合并段m-1 合并段m 层数： 中间合并段 中间合并段 「logxm1+1 归并趟数： 「logxm7 有序文件 ·设从k个元素中挑选一个最小的元素需(k-)次比较。每次比较耗费的时间代价为： tmg,那么在进行k路平衡归并时，总的时间耗费不会超过： [iogkm×(k-1)×(n-1)×tmg=log2m1log2k×(k-1)×(n-1)×tmg 大 Tlogzm logzk]x (k-1) 大 16 EXST
16 物料管理 EXST 16 Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 1、带、盘的平衡多路归并的性质： • e.g: K > 2 时, 趟数将会减少。m 个归并串。总共 n 个记录。 合并段1 合并段k 合并段m-1 合并段m 中间合并段 中间合并段 有序文件 层数： logkm +1 归并趟数： logkm • 设从 k 个元素中挑选一个最小的元素需 ( k-1) 次比较。 每次比较耗费的时间代价为: tmg，那么在进行 k 路平衡归并时，总的时间耗费不会超过： logkm × ( k - 1 ) × ( n - 1 ) × tmg = log2m / log2k × ( k - 1 ) × ( n - 1 ) × tmg k log2m / log2k × ( k - 1 ) 大 大
Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 1、带、盘的平衡多路归并的性质： ·设从k个元素中挑选一个最小的元素需(k-)次比较。每次比较耗费的时间代价为： tmg,那么在进行k平衡归并时，总的时间耗费不会超过： [logkm]×(k-1)×(n-1)×tmg=log2m1log2k×(k-1)×(n-1)×tmg 大 Tlog2m logzk]x (k-1) 大 ·改进：采用胜者树或者败者树，从K个元素中挑选一个最小的元素仅需「og2k]次比 较，这时总的时间耗费将下降： 「logkm1×「log2k×(n-1)×tmg 2、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结 果，使得更快地挑出亚军、第三名.。 17 EXST
17 物料管理 EXST 17 Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 1、带、盘的平衡多路归并的性质： • 设从 k 个元素中挑选一个最小的元素需 ( k-1) 次比较。 每次比较耗费的时间代价为: tmg，那么在进行 k 平衡归并时，总的时间耗费不会超过： logkm × ( k - 1 ) × ( n - 1 ) × tmg = log2m / log2k × ( k - 1 ) × ( n - 1 ) × tmg k log2m / log2k × ( k - 1 ) 大 大 • 改进：采用胜者树或者败者树，从 K 个元素中挑选一个最小的元素仅需 log2k 次比 较，这时总的时间耗费将下降： logkm × log2k × ( n - 1 ) × tmg 2、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结 果，使得更快地挑出亚军、第三名 .
Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 2、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结 果，使得更快地挑出亚军、第三名. 1 2 3 5 6 5 9 5 29 3 9 29 注意：挑出冠军 输 5 7 29 9 输 5 需要进行k-1次 入 16 12 38 22 出 49 2584 57 47 比较，此处需要 缓 冲 52 48 比较3次。 d 91 71 9 冲 18 区 区 EXST
18 物料管理 EXST 18 Algorithms and DataStructures:EXSORT 5 9 3、多路平衡归并的实现 2、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结 果，使得更快地挑出亚军、第三名 . 。 5 7 29 9 5 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 4 5 6 7 2 3 1 输 入 缓 冲 区 输 出 缓 冲 区 5 5 9 5 7 29 9 1 2 3 4 5 6 7 5 注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次
Algorithms and DataStructures:EXSORT 3、多路平衡归并的实现 2、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结 果，使得更快地挑出亚军、第三名. 2 3 6 9 16 29 9 3 9 29 注意：挑出亚军 输 5 7 29 9 输 5 入 16 22 7 需要进log2k] 5 AT 出缓 次比较，此处需 冲 52 2504 48 要比较2次。 1 . o 冲 19 区 区 EXST
19 物料管理 EXST 19 Algorithms and DataStructures:EXSORT 7 9 3、多路平衡归并的实现 2、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结 果，使得更快地挑出亚军、第三名 . 。 16 7 29 9 7 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 4 5 6 7 2 3 1 输 入 缓 冲 区 输 出 缓 冲 区 7 7 9 16 7 29 9 1 2 3 4 5 6 7 5 7 注意：挑出亚军 需要进行 log2k 次比较，此处需 要比较 2 次