樹形選擇排序(已修改)
2025-08-17 08:24 本頁面
【正文】 樹型選擇排序 (Tree Selection Sort) 錦標(biāo)賽排序 (Tournament Sort) ? 它的思想與體育比賽時的淘汰賽類似。首先將 n 個對象的排序碼 進行 兩兩比較 , 得到 ?n/2? 個 比較的優(yōu)勝者 (排序碼小者 ), 作為第一步比較的結(jié)果保留下來；然后對這 ?n/2? 個對象再進行排序碼的兩兩比較 , …, 如此重復(fù) , 直到選出一個排序碼最小的對象為止。 ? 在圖例中 , 最下面是對象排列的初始狀態(tài) ,相當(dāng)于一棵滿二叉樹的葉結(jié)點 , 它存放的是 所有參加排序的對象的排序碼 。 如果 n 不是 2 的 k 次冪 ， 則讓葉結(jié)點數(shù)補足到滿足 2k1 n ? 2k 的 2k 個 。 葉結(jié)點上面一層的非葉結(jié)點是葉結(jié)點排序碼兩兩比較的結(jié)果 ， 最頂層是樹的根 。 08 Winner 21 08 08 63 25* 21 21 25 49 25* 16 08 63 勝方樹的概念 ? 每次兩兩比較的結(jié)果是把 排序碼小者作為優(yōu)勝者上升到雙親結(jié)點 ， 稱這種比賽樹為勝方樹 。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1