樹(shù)形選擇排序-預(yù)覽頁(yè)
【正文】 O(log2n)。 ? 如果有 n 個(gè)對(duì)象，必須使用至少 2n1 個(gè)結(jié)點(diǎn)來(lái)存放勝方樹(shù)。 。每個(gè)結(jié)點(diǎn)包括排序碼 、 結(jié)點(diǎn)序號(hào) 和 比較標(biāo)志 三種信息。 ? 對(duì)象的移動(dòng)次數(shù)不超過(guò)排序碼的比較次數(shù) ，所以樹(shù)形選擇排序總時(shí)間復(fù)雜度為O(nlog2n)。 ? 勝方樹(shù)最頂層是樹(shù)的 根 ，表示 最后選擇出來(lái)的具有最小排序碼的對(duì)象 。 葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)排序碼兩兩比較的結(jié)果 ， 最頂層是樹(shù)的根 。樹(shù)型選擇排序 (Tree Selection Sort) 錦標(biāo)賽排序 (Tournament Sort) ? 它的思想與體育比賽時(shí)的淘汰賽類(lèi)似。 如果 n 不是 2 的 k 次冪 ， 則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿(mǎn)足 2k1 n ? 2k 的 2k 個(gè) 。 每個(gè)結(jié)點(diǎn)除了存放對(duì)象的排序碼 key 外 ， 還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿(mǎn)二叉樹(shù)中的序號(hào) index。 總排序碼比較次數(shù) 為 O(nlog2n)。最多需要找到滿(mǎn)足 2k1 n ? 2k 的 k，使用 2*2k1 個(gè)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1