什么是Polyphase Merge Sort

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

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

Merge Sort
歸并排序,其算法思想是對于2個run(已排序的數(shù)據(jù)簡稱)進行歸并得到最終結(jié)果.
在初始狀態(tài)下,可以把一個待排序的元素視為一個run,然后以2的n次方為基數(shù)逐步歸并為最終結(jié)果,顯然,其算法復(fù)雜度(時間)是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個輸入和輸出設(shè)備,讀取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

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

Polyphase Merge Sort
Polyphase Merge Sort與N-way類似,但只需要1個空閑設(shè)備,大大節(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”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！