Python实现基于败者树的K路归并排序

import random
import os,sys

'''
随机生成不大于max的长度位n的列表
'''
def genList(n,max):
    result = []
    for i in range(n):
        result.append(random.randint(0,max))
    print(result)
    return result

'''
从给定的列表中获取k个有序列表分组
'''
def splitSortedList(sourceList,k):
    splits = []
    rim = len(sourceList)%K
    step = len(sourceList)//K
    for i in range(K):
        li = sourceList[i*step:i*step+step]
        li.append(MAXINT)
        if rim >0 and i==K-1:
          li = li + sourceList[step * K: step*K + rim]
        li.sort(reverse=True)
        if li != []:
            splits.append(li)
    print(splits)
    return splits

'''
定义调整函数
s是buf数组的下标
'''
def adjust(s):
    t = (s+K)//2 #取s位的父节点
    
    #如果当前节点不是根节点则进入下次循环，否则跳出
    while t>0:
        #比较当前节点值与父节点对应的值，如果父节点胜出则记录失败者并将当前节点换成胜利者
        if buf[s] > buf[ls[t]]:
            l = ls[t]
            ls[t] = s
            s = l
        t = t//2
    #记录最终胜利者到ls[0]
    ls[0] = s
    
    
'''
定义败者树构建函数
'''
def build():
    #添加最小值-1到buf尾部
    buf.append(-1)
    
    #将败者树中间节点全部初始化为最小值所在位置即len(buf)-1
    for i in range(len(buf)):
        ls.append(len(buf)-1)
        
    #依次调整buf列表中所有位置
    for i in range(K):
        adjust(i)


MAXINT = sys.maxsize
MININT = -1
K      = 5 #5路归并

#生成测试用例列表长度位33，每个元素是不大于100的随机正整数
source = genList(33,100)
#将待排序数列分成K组
source_split = splitSortedList(source,K)

ls  = []
buf = []

#用每组的第一个元素初始化buf列表
for i in range(len(source_split)):
    buf.append(source_split[i].pop())

#构建初始化buf的败者树
build()

sorted_list =[]
#循环取出最后胜利者，读取新元素进入buf并调整败者树
while buf[ls[0]] < MAXINT:
    winner = ls[0]
    sorted_list.append(buf[winner])
    buf[winner] = source_split[winner].pop()
    adjust(winner)

source.sort()
print(source)
assert(source == sorted_list)  
print(sorted_list)

 

本文地址：https://blog.csdn.net/wqs1106/article/details/107160606