[其它]數(shù)據(jù)結(jié)構(gòu)第10章-資料下載頁(yè)
2025-01-19 10:02本頁(yè)面
【正文】 狀況如圖 （ c）所示。 第四步：把 T1上的順串 1和 T3上的順串 3合并，并把結(jié)果放到 T2上，即為所要求的有序文件。 ? 第 10章 外部排序 上述例子采用的是 2路歸并法，與磁盤排序的情況一樣，排序的時(shí)間主要取決于對(duì)數(shù)據(jù)的掃描遍數(shù)。采用多路歸并能減少掃描的遍數(shù)，但對(duì)磁帶排序來(lái)說(shuō)，多路歸并需要多臺(tái)磁帶機(jī)，為了避免過(guò)多的磁帶尋找時(shí)間，要?dú)w并的順串需要放在不同的磁帶上。因此， k路歸并至少需要 k+1臺(tái)磁帶機(jī)，其中 k臺(tái)作為輸入帶，另外一臺(tái)用于歸并后存放輸出結(jié)果。但這樣需要對(duì)輸出帶再作一遍掃描，把輸出帶上的各順串重新分配到 k臺(tái)磁帶上，以便作為下一級(jí)歸并使用。若使用 2k臺(tái)磁帶機(jī)，則可避免這種再分配掃描，把 k臺(tái)作為輸入帶，其余 k臺(tái)作為輸出帶，在下一級(jí)歸并時(shí)，輸入帶與輸出帶的作用互相對(duì)換。上述例子就是用 4臺(tái)磁帶機(jī)實(shí)現(xiàn) 2路歸并， T T2和 T T4輪流地用作輸入帶和輸出帶。 第 10章 外部排序 2. 非平衡歸并 設(shè)初始順串的長(zhǎng)度為度量單位，即規(guī)定初始順串的長(zhǎng)度為 1，用 Sn來(lái)表示某臺(tái)磁帶機(jī)上有 n個(gè)順串，每個(gè)順串的長(zhǎng)度為 S。 假設(shè)初始順串有八個(gè)，則在 T1上分配五個(gè)順串，在 T2上分配三個(gè)順串，然后把 T2上的三個(gè)順串與 T1中的三個(gè)順串相歸并，得到三個(gè)長(zhǎng)度為 2的順串，將它們寫到 T3上。下一步把 T1中的兩個(gè)順串與 T3中的兩個(gè)順串相歸并，得到兩個(gè)長(zhǎng)度為 3的順串，把它們寫到 T2上。再下一步是把 T3上一個(gè)長(zhǎng)度為 2的順串與 T2中的一個(gè)長(zhǎng)度為 3的順串進(jìn)行歸并，得到一個(gè)長(zhǎng)度為 5的順串，將其寫到 T1上。最后，把 T1上一個(gè)長(zhǎng)度為 5的順串與 T2上一個(gè)長(zhǎng)度為 3的順串進(jìn)行歸并， 得到一個(gè)長(zhǎng)度為 8的順串，把它寫到 T3上。至此，完成了非平衡 2路歸并排序。 第 10章 外部排序 圖 采用非平衡分布法用三臺(tái)磁帶機(jī)實(shí)現(xiàn) 2路歸并 第 10章 外部排序 下面我們來(lái)討論如何確定順串初始分布的問(wèn)題。為了確定初始分布，就得從最后一步往前推。假設(shè)有 n步，我們希望 n步之后在 T1上正好有一個(gè)順串，而在 T2和 T3上沒(méi)有順串。要做到這點(diǎn)，則必須把 T2中的一個(gè)順串與 T3中的一個(gè)順串加以歸并來(lái)得到這種順串，并且 T2和 T3上沒(méi)有別的順串，所以在第 n1步后， T2和 T3上應(yīng)各有一個(gè)順串， T2上的順串是從 T1和 T3中各取一個(gè)順串加以歸并后得到，因此，在第 n2步后，在 T1上應(yīng)有一個(gè)順串，在 T3上應(yīng)有兩個(gè)順串，就這樣一步一步往前推。圖 過(guò)程。由該圖可見(jiàn)，若有初始順串 21個(gè)，則可以分配 13個(gè)順串到 T1上，分配 8個(gè)順串到 T2上。 第 10章 外部排序 圖 三帶 2路歸并的順串分布 第 10章 外部排序 圖 四帶 3路歸并的順串分布
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1