本篇內容主要講解“什么是Polyphase Merge Sort”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“什么是Polyphase Merge Sort”吧!

專注于為中小企業(yè)提供成都網(wǎng)站制作、成都網(wǎng)站設計服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)麥積免費做網(wǎng)站提供優(yōu)質的服務。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了1000+企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設實現(xiàn)規(guī)模擴充和轉變。

Polyphase Merge Sort是一種External Sort算法,給定N個Tapes,只需要1個Tapes作為Output設備,而且讀寫均為順序讀寫,對于Disk/Tapes等外存設備比較友好.

Merge Sort
歸并排序,其算法思想是對于2個run(已排序的數(shù)據(jù)簡稱)進行歸并得到最終結果.
在初始狀態(tài)下,可以把一個待排序的元素視為一個run,然后以2的n次方為基數(shù)逐步歸并為最終結果,顯然,其算法復雜度(時間)是O(nlogn).

Tape1 : 2 3 5 6 9 11
Tape2 : 4 7 8 10
Output : 2 3 4 5 6 7 8 9 10 11

Balanced N-way Merge Sort
平衡多路歸并排序,其算法思想是使用N個輸入和輸出設備,讀取N個輸入歸并產(chǎn)生N個輸出.
注:下面是一個實現(xiàn)樣例,其中以字符”|”分隔的部分稱為run

Tape1 : 2 3 5 6 30 | 1 11 200 
Tape2 : 4 7 8 10 | 15 20 35 201
Tape3 : Empty
Tape4 : Empty

Pass1

Tape1 : Empty
Tape2 : Empty
Tape3 : 2 3 4 5 6 7 8 10 30 
Tape4 : 1 11 15 20 35 200 201

Pass2

Tape1 : 1 2 3 4 5 6 7 8 10 11 15 20 30 35 200 201 
Tape2 : Empty
Tape3 : Empty
Tape4 : Empty

之所以稱為平衡,是因為輸入和輸出的”設備”是一樣多的.N-way指的是可以同時對N個設備進行處理(并行).
在空間利用上,這種算法需要N個空閑設備.

Polyphase Merge Sort
Polyphase Merge Sort與N-way類似,但只需要1個空閑設備,大大節(jié)省了空間.
注:下面是一個實現(xiàn)樣例,其中以字符”|”分隔的部分稱為run

初始狀態(tài)
Tape1 : 2 3 5 6 30 | 1 11 200 | 25 40 56 70
Tape2 : 4 7 8 10 | 15 20 35 201 | 27 33 46 78 | 13 17 27 87 90
Tape3 : Empty

Pass1
Tape1 : Empty
Tape2 : 13 17 27 87 90
Tape3 : 2 3 4 5 6 7 8 10 30 | 1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78

Pass 2
Tape1 : 2 3 4 5 6 7 8 10 13 17 27 30 87 90
Tape2 : Empty
Tape3 :1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78

Pass3
Tape1 : Empty
Tape2 : 1 2 3 4 5 6 7 8 10 11 13 15 17 20 27 30 35 87 90 200 201
Tape3 :25 27 33 40 46 56 70 78

Pass4
Tape1 : 1 2 3 4 5 6 7 8 10 11 13 15 17 20  25 27 30 33 35 40 46 56 70 78 87 90 200 201
Tape2 : Empty
Tape3 : Empty

到此，相信大家對“什么是Polyphase Merge Sort”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！