PostgreSQL中REPLACEMENT SELECTION SORT使用與哪種情況

本篇內(nèi)容主要講解“PostgreSQL中REPLACEMENT SELECTION SORT使用與哪種情況”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“PostgreSQL中REPLACEMENT SELECTION SORT使用與哪種情況”吧!

REPLACEMENT SELECTION SORT,適用于內(nèi)存較小的情況(在高德納提出該算法的年代,內(nèi)存比起現(xiàn)在少了N個數(shù)量級).
該算法在PG 9.x或以下版本在使用,在高版本已被廢棄.其算法實現(xiàn)如下:

Let m be the number of records to be sorted which can be kept in the main memory. Imagine that these memory locations are registers and assume we can mark them as “on” or “off”. Replacement selection can overlap reading, sorting and writing.

Step1: The m registers are filled with records from the input to be sorted.
Step2: All registers are put into the “on” state.
Step3: Select the register which has the smallest of all “on” registers.
Step4: Transfer the contents of the selected register to the output (call it as key Y).
Step5: Replace the contents of the selected register by the next input record.
            If new record key > Y
                        Go to step 3
            If new record key = =Y
                        Go to step 4
            If new record key < Y
                        Go to step 6
Step6: Turn the selected key register  “off”.
            If all registers are now  “off”
                        We have completed a sorted substring(run).
                        We start a new substring group and go to step 2.
            Else
                        Go to step 3

下面是該算法的一個例子:

Example: Suppose number of registers is 3 and input keys are 5, 2, 9, 7, 0, 8, 1, 6, 3, 4 ...
            Registers                               Output
            5 2 9                                       2
            5 7 9                                       5
*0 7 9                                     7
*0 8 9                                     8
*0*1 9                                    9
*0*1*6
0 1 6                                       0
3 1 6                                       1
3 4 6                                       3
- 4 6                                        4
- - 6                                        6
- - -

相關(guān)的數(shù)據(jù)結(jié)構(gòu):兩個數(shù)組,一個存儲讀取的實際數(shù)據(jù),一個標記數(shù)組;一個外存,用于存儲已完成排序的一個run.
如標記數(shù)組全為F(非活動狀態(tài)),則產(chǎn)生一個run,周而復(fù)始,直至所有輸入被耗盡為止.
通過這個方法,可以生成N個runs(每個run對應(yīng)的是已完成排序的部分數(shù)據(jù)).

CS 351 -Data Organization and Management ( Section: 02)
External_sorting
replacement-selection-sort vs selection-sort

到此，相信大家對“PostgreSQL中REPLACEMENT SELECTION SORT使用與哪種情況”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！