樹形選擇排序-全文預(yù)覽
【正文】 樹形選擇排序構(gòu)成的勝方樹是滿二叉樹 , 其深度為 ?log2n? , 其中 n 為待排序元素個數(shù)。 08 Winner 21 08 08 63 25* 21 21 25 49 25* 16 08 63 勝方樹的概念 ? 每次兩兩比較的結(jié)果是把 排序碼小者作為優(yōu)勝者上升到雙親結(jié)點 ， 稱這種比賽樹為勝方樹 。首先將 n 個對象的排序碼 進(jìn)行 兩兩比較 , 得到 ?n/2? 個 比較的優(yōu)勝者 (排序碼小者 ), 作為第一步比較的結(jié)果保留下來；然后對這 ?n/2? 個對象再進(jìn)行排序碼的兩兩比較 , …, 如此重復(fù) , 直到選出一個排序碼最小的對象為止。 ? 在圖例中 , 最下面是對象排列的初始狀態(tài) ,相當(dāng)于一棵滿二叉樹的葉結(jié)點 , 它存放的是 所有參加排序的對象的排序碼 。 ? 位于 最底層的葉結(jié)點 叫做勝方樹的 外結(jié)點 ，非葉結(jié)點 稱為勝方樹的 內(nèi)結(jié)點 。 ? 除 第一次選擇具有最小排序碼的對象 需要進(jìn)行 n1 次 排序碼比較 外 , 重構(gòu)勝方樹選擇具有次小、再次小排序碼對象所需的 排序碼比較次數(shù) 為
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1