歸并排序方法：
1溪猿、將記錄分為若干個文件刃跛，每個文件先進行內(nèi)部排序抠艾，這些排序好的叫做歸并段或者順串。
2桨昙、用歸并將歸并段由小變大检号，由多變少。優(yōu)化
為了減少外部IO時間绊率，要增加歸并路數(shù)（多個文件同時進行歸并）谨敛，減少初始歸并段。但增加歸并路數(shù)的同時每次比較按照常規(guī)的時間也會更長滤否，比如二路歸并我們需要比較一次即可選出最小值脸狸，n路歸并需要n-1次，但是我們可以利用上次比較的信息來減少多路歸并的比較次數(shù)，這就是敗者樹炊甲。敗者樹：
勝者樹和堆的區(qū)別：
相同的都是完全樹泥彤，每次調(diào)整的時間復雜度也都是O(logn)，最大的區(qū)別就是堆的非葉子節(jié)點有包含元素卿啡，而勝者樹只有葉子節(jié)點有元素吟吝，非葉子節(jié)點用來存放兩個節(jié)點的勝者。由于這種結(jié)構(gòu)上的差異颈娜，因此每次在調(diào)整的時候堆要分別跟兩個孩子進行兩次比較剑逃，而勝者樹只需要跟其兄弟進行一次比較即可，效率上會高一點官辽，有些人可能跟我一開始一樣有這樣的疑問蛹磺，雖然你在比較次數(shù)上少了一半，但堆由于非葉子節(jié)點也含有原始數(shù)據(jù)同仆，所以堆的樹的高度會比勝者樹低一些萤捆，那么需要調(diào)整的次數(shù)少了，綜合起來不是差不多嗎俗批？要注意這里的樹是完全二叉樹俗或，每增加一層，節(jié)點數(shù)目就增加了一倍多岁忘，因此堆的高度一般也只比勝者樹矮一層辛慰，而一般樹的高度都是比較高的，這樣定性分析來說臭觉，堆在高度上也只有很小的優(yōu)勢昆雀。
勝者樹和敗者樹的區(qū)別：
一開始我是想寫代碼實現(xiàn)敗者樹的，沒想到理解成勝者樹蝠筑，實現(xiàn)成了勝者樹狞膘。實際操作發(fā)現(xiàn)，勝者樹每次都將勝者放在父節(jié)點上面什乙，如果這是最終的勝者挽封，一路上升到到根節(jié)點都是勝者的記錄，這就沒有必要了臣镣！于是就有了敗者樹辅愿，敗者樹的父節(jié)點存儲的是敗者，下次我們直接跟父節(jié)點進行比較就可以了忆某，實際代碼上減少了計算兄弟的計算量点待。勝者樹相交于敗者樹代碼的區(qū)別：
下面是勝者樹的代碼，可以看到每次更新新的數(shù)據(jù)的時候癞埠，我們要讓勝者一路沿著樹上浮到根節(jié)點（根節(jié)點下標為1）状原。很清楚地看到，我們先計算父節(jié)點的位置苗踪，然后再計算左右節(jié)點的位置颠区，將左右節(jié)點來進行比較放到父節(jié)點，然后父節(jié)點又跟其兄弟進行比較通铲，以此類推毕莱。
father_index = (offset+path)//2
while father_index != 0:
lc_index = father_index*2
rc_index = lc_index + 1
if loser_tree[lc_index][1] < loser_tree[rc_index][1]:
loser_tree[father_index] = loser_tree[lc_index]
else:
loser_tree[father_index] = loser_tree[rc_index]
father_index //= 2
敗者樹調(diào)整新加入的節(jié)點部分的代碼，可以看到每次都是暫時優(yōu)勝者跟上一個進行比較：
new_comer = pre_winnner
loser_tree[0] = loser_tree[new_comer]
# 對比勝者樹颅夺，這里每次都只需跟上一級進行比較即可
while new_comer != 0:
if loser_tree[new_comer][1] < loser_tree[0][1]:
loser_tree[new_comer],loser_tree[0] = loser_tree[0],loser_tree[new_comer]
else:
pass
new_comer //= 2
- 置換選擇排序（生成初試歸并段）
為了在內(nèi)存大小有限的情況下盡量增加歸并段的長度朋截。
可以用最小堆或者敗者樹來實現(xiàn)
生成的初試歸并段長度、是傳統(tǒng)方法的2倍
-最佳歸并樹
長度不等的歸并段在歸并路數(shù)相等的情況下碗啄，歸并的順序不同效率也不同质和，歸家歸并樹可以減少比較次數(shù)稳摄。
勝者樹全部代碼：
注：本來是想實現(xiàn)敗者樹的稚字，但是理解錯誤成勝者樹，所以變量名稱含loser不要太在意厦酬。另外我寫完后才發(fā)現(xiàn)教科書上的圖所代表的那棵樹胆描，也就是下面的loser_tree這個列表是沒有包含我們分析中的葉子節(jié)點的，但我在實現(xiàn)上是有包含的仗阅，復制了過來昌讲，這樣子代碼寫起來更加簡潔，后來想要改减噪，可以改短绸，但是改的并不是很好看，所以維持現(xiàn)狀筹裕。
# 敗者樹來減少多路歸并所需的比較次數(shù)
BIG_NUM = 100000000
def loser_tree_merge(data):
# data是個二維數(shù)組醋闭，其橫向向量個數(shù)為敗者樹的路數(shù)
# 每個向量所包含元素為各自路數(shù)的元素個數(shù)
paths_of_merge = len(data)
paths_length = [0]*paths_of_merge
for i in range(paths_of_merge):
paths_length[i] = len(data[i])
# 敗者樹是一棵完全二叉樹，歸并段輸入的數(shù)據(jù)為樹的葉子
# 完全二叉樹節(jié)點個數(shù)N = N0+N1+N2朝卒，其中N0=N2+1证逻，N0 = paths_of_merge，N1根據(jù)根據(jù)觀察永遠為0
loser_tree_num = paths_of_merge + (paths_of_merge - 1) + 1
loser_tree = [0]*loser_tree_num
paths_index = [0]*paths_of_merge
offset = loser_tree_num - paths_of_merge
# 填充數(shù)據(jù)到葉子節(jié)點
for i in range(paths_of_merge):
loser_tree[offset+i] = [i,data[i][paths_index[i]]]
paths_index[i] += 1
# 調(diào)整非葉子節(jié)點抗斤，注意是由最后向前調(diào)整
for i in range(offset-1,0,-1):
lc = i*2
rc = lc+1
if loser_tree[lc][1] < loser_tree[rc][1]:
loser_tree[i] = loser_tree[lc]
else:
loser_tree[i] = loser_tree[rc]
while loser_tree[1][1]!=BIG_NUM:
path,num = loser_tree[1]
print(num,end = ' ')
if paths_index[path] < paths_length[path]:
new_elem = data[path][paths_index[path]]
paths_index[path] += 1
loser_tree[offset+path] = [path, new_elem]
else:
new_elem = BIG_NUM
loser_tree[offset+path] = [path,new_elem]
father = (offset+path)//2
while father != 0:
lc = father*2
rc = lc + 1
if loser_tree[lc][1] < loser_tree[rc][1]:
loser_tree[father] = loser_tree[lc]
else:
loser_tree[father] = loser_tree[rc]
father //= 2
def main():
data = [[1,2],[3,5,8],[6,7,9]]
loser_tree_merge(data)
if __name__ == '__main__':
main()
真正的敗者樹來了：
# 敗者樹來減少多路歸并所需的比較次數(shù)
BIG_NUM = 987654321
def loser_tree_merge(data):
# data是個二維數(shù)組囚企，其橫向向量個數(shù)為敗者樹的路數(shù)
# 每個向量所包含元素為各自路數(shù)的元素個數(shù)
paths_of_merge = len(data)
paths_length = [0]*paths_of_merge
for i in range(paths_of_merge):
paths_length[i] = len(data[i])
# 敗者樹是一棵完全二叉樹，歸并段輸入的數(shù)據(jù)為樹的葉子
# 完全二叉樹節(jié)點個數(shù)N = N0+N1+N2瑞眼，其中N0=N2+1龙宏，N0 = paths_of_merge，N1根據(jù)根據(jù)觀察永遠為0
loser_tree_num = paths_of_merge + (paths_of_merge - 1) + 1
loser_tree = [0]*loser_tree_num
paths_index = [0]*paths_of_merge
offset = loser_tree_num - paths_of_merge
# 敗者樹第一輪還需要另外記錄勝者伤疙，之后就不用了
winner = [0]*loser_tree_num
# 填充數(shù)據(jù)到葉子節(jié)點
for i in range(paths_of_merge):
loser_tree[offset+i] = [i,data[i][paths_index[i]]]
winner[offset+i] = [i,data[i][paths_index[i]]]
paths_index[i] += 1
# 調(diào)整非葉子節(jié)點银酗，注意是由最后向前調(diào)整
for i in range(offset-1,0,-1):
lc = i*2
rc = lc+1
if winner[lc][1] < winner[rc][1]:
loser_tree[i] = winner[rc]
winner[i] = winner[lc]
else:
loser_tree[i] = winner[lc]
winner[i] = winner[rc]
loser_tree[0] = winner[1]
while loser_tree[0][1]!=BIG_NUM:
path,num = loser_tree[0]
print(num,end = ' ')
pre_winnner = offset + path
if paths_index[path] < paths_length[path]:
new_elem = data[path][paths_index[path]]
paths_index[path] += 1
loser_tree[pre_winnner] = [path, new_elem]
else:
new_elem = BIG_NUM
loser_tree[pre_winnner] = [path,new_elem]
new_comer = pre_winnner
loser_tree[0] = loser_tree[new_comer]
# 對比勝者樹，這里每次都只需跟上一級進行比較即可
while new_comer != 0:
if loser_tree[new_comer][1] < loser_tree[0][1]:
loser_tree[new_comer],loser_tree[0] = loser_tree[0],loser_tree[new_comer]
else:
pass
new_comer //= 2
def main():
data = [[3,5,8],[1,2,4],[6,7,9]]
loser_tree_merge(data)
if __name__ == '__main__':
main()
