数据结构与算法 代码整理：外排序法

外排序原理：

外排序就是能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次性装入内存，只能放在读写较慢的外存储器（eg.硬盘）上，通常采用“排序-归并”策略。

算法性能分析：

参考：http://blog.chinaunix.net/uid-25324849-id-2182916.html

多路归并的实现：

败者树是树形选择排序的一种变形。若在双亲结点中记下刚进行完比赛中的败者，而让胜者去参加高一级的比赛，便可得到一颗“败者树”。

如下图a中，在败者树中，根节点ls[2]的双亲结点ls[1]为冠军，指示各归并段中的最小关键字元素在第4段，

结点ls[5]指示败者为b5，胜者为b4，b4将在下一次比赛ls[1]中和b1比较；结点ls[1]指示败者为b1，胜者为b4，与另一场比赛的胜者b2进行比较。

 在选得最小关键字元素后，只需修改对应叶子结点的值(b4)，使其同一个归并段的下一个元素作为该胜出叶子结点的新的关键字，然后从该节点向上与双亲结点所指的关键字比较，败者留在该双亲，胜者继续向上直至树根的双亲，如图b所示。

算法思想用python实现如下：

# 外排序——多路归并排序法
# 败者树算法

# 模拟磁盘中已排序区域，并在文件最后添加一个极大数作为判断结束的哨兵值
# 注意，由于从列表后面删除元素要快于从前面删除，所以示例中的区域采用倒序排列，把第一个关键字放在最后
B = {1:[999,    16,15,10],
     2:[999,    20,18,9 ],
     3:[999,    40,22,20],
     4:[999,    25,15,6 ],
     5:[999,    48,37,12]}
k = len(B)   # k路归并
merge_result = []     # 目标归并段


# k 路归并处理程序
# 利用败者树ls将编号从1到k的k个输入归并段元素归并到输出端
# b[1]到b[k]为败者树上的k个叶子结点，分别存放k个输入归并段中当前元素的关键字
b = [0]*(k+1)       # 起点从1开始，第0位空着
ls = [0]*(k+1)      # 由于败者树是完全二叉树（不含叶子），则该树的结点数即叶子个数(归并路数)，可采用顺序储存结构


def K_Merge():
    for i in range(1,k+1):      # 分别从k个输入归并中读入该段中的第一个关键字
        input(i)                # 保存到叶子节点中
    CreaterLoserTree()          # 根据当前关键字b建立败者树ls
    while b[ls[1]]!=999:        # 当冠军值非最大的哨兵值（存在未被归并的元素）时，归并继续
        q = ls[1]               # q指示当前最小关键字所在的归并段
        output(q)               # 将编号为 q 的段中最前面关键字写入输出归并段
        input(q)                # 从编号为 q 的段中读入下一个关键字
        AdjustLoserTree(q)      # 根据当前冠军，调整败者树，选择新的最小关键字
#     output(1)                   # 将喊最大关键字的元素写入输出段（假设选择最大关键字作为哨兵的话,不过这里不需要）
    
# 建立败者树ls
# 已知从b[1]到b[k]为完全二叉树ls的叶子结点存有k个关键字，沿从叶子到根的k条路径将ls调整为败者树
def CreaterLoserTree():
    # 假设败者树上存放的都是最小键值（所在的序号），则可以对每个叶子节点进行测试
    # 使当前结点的键值上升为新的败者，以替换掉原来树节点的位置

    minval = b[1]
    for i in range(2,k):        # 先从第一批叶子结点中找到拥有最小的键值所在的段
        if b[i]<minval:
            minval = b[i]; minidx = i
    
    for i in range(1,k+1):      
        ls[i] = minidx          # 设置败者初值，为最小键值所在的段序号
    
    for i in range(k,0,-1):
        AdjustLoserTree(i)      # 依次从b[1],b[2],...,b[k]出发调整败者树

# 选择最小关键字后，从叶到根调整败者树，选出下一个最小关键字
# 沿从叶子节点b[s],到根节点ls[0]的路径调整败者树
def AdjustLoserTree(s):
    t = (s+k+1)/2               # ls[t]是b[s]的父结点 (+1是为了四舍五入)
    while t > 1:
        if b[s] > b[ls[t]]:     # 败者树的结点中存放的是比较后较大的关键字所在的段序号
            s,ls[t] = ls[t],s   # 当b[s]被击败后，将s指示向新的胜利者，并将败者留着当前的内结点中
        t = (t+1)/2             # 上移到上一个父结点
    ls[1] = s



# 模拟外存读入函数，从i所指向的区域读取第一个关键字
def input(i):
    b[i] = B[i][-1]
# 模拟输出归并函数,从i所指向的区域中读取第一个关键字，并输出到归并段
def output(i):
    merge_result.append(B[i].pop())


if __name__=="__main__":
    pass
    K_Merge()
    print merge_result
    #>>> [6, 9, 10, 12, 15, 15, 16, 18, 20, 20, 22, 25, 37, 40, 48]