外部排序ruby实现
# value 数组类型，存储待比较大小的元素。数组长度比败者树数组长度大1# loser_tree 数组类型，败者树。数组元素是value数组的索引# node 待调整的叶子结点在value数组中的索引def adjust_loser_tree(value, loser_tree, node) # 求叶子结点的父结点在败者树中的索引 t = (node + loser_tree.size) / 2 while t > 0if value[node].email > value[loser_tree[t]].email tmp = node node = loser_tree[t] loser_tree[t] = tmpendt /= 2 end loser_tree[t] = nodeend# 创建败者树def create_loser_tree(value, loser_tree) # 初始化败者树数组 0.upto(loser_tree.size - 1) do |i|loser_tree[i] = value.size - 1 end (value.size - 2).downto(0) do |i|adjust_loser_tree(value, loser_tree, i) endend
