1、引言
選擇排序里面主要講了三個(gè)排序，分別是簡(jiǎn)單選擇排序、樹(shù)形選擇排序、堆排序。今天這篇文章主要講樹(shù)形選擇排序，樹(shù)形選擇排序也被稱(chēng)為錦標(biāo)賽排序，樹(shù)形選擇排序運(yùn)用了錦標(biāo)賽的思想進(jìn)行排序，樹(shù)形選擇排序是指首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小的記錄為止。
2、問(wèn)題描述
給定一個(gè)序列，我們將如何用樹(shù)形選擇排序來(lái)將它排序呢，下面將結(jié)合圖形和文字一起講述。
示例1：對(duì)數(shù)據(jù)表A=（73，45，79，90，81，75，94，97）進(jìn)行排序
輸出：45 73 75 79 81 90 94 97
3、解決方案
數(shù)據(jù)表A是亂序的，現(xiàn)在需要將它按照從小到大的順序排序好，根據(jù)樹(shù)形選擇排序的思想首先需要將比較的記錄全部作為葉子，然后按照從左到右的順序，兩兩進(jìn)行比較，選出最小的那個(gè)，然后將比較后的n/2個(gè)元素又按照從左到右的順序兩兩進(jìn)行比較，選出最小的，一直重復(fù)這樣操作后，會(huì)從底向上形成一個(gè)完全二叉樹(shù)。可能讀完這段文字還是不好理解，下面我將用圖示來(lái)具體描述。
1.構(gòu)建二叉樹(shù)：圖1是數(shù)據(jù)表A構(gòu)成的二叉樹(shù)，首先直接將數(shù)據(jù)表A的數(shù)據(jù)直接放在最下面，也就是二叉樹(shù)的葉子；然后從左到右兩兩進(jìn)行比較，例如73和45比較后選出最小的45，79和90比較后選出最小的79，將選出的45和79比較選出最小的45，一直這樣重復(fù)操作，直到構(gòu)成一個(gè)完整的二叉樹(shù)。
2. 如何輸出正確順序：根據(jù)圖1可以知道根節(jié)點(diǎn)是45，也就是最小的。圖2就是把第一遍找出來(lái)的45用無(wú)窮符號(hào)代替，然后又兩兩比較，直到根節(jié)點(diǎn)變?yōu)樽钚〉模ㄟ^(guò)圖1和圖2對(duì)比可以看出第一遍找到的最小的是45，第二遍是73，，現(xiàn)在又將找出來(lái)的73用無(wú)窮符號(hào)代替，又重復(fù)上面的操作，直到對(duì)所有數(shù)據(jù)排完序。如下圖所示
4、結(jié)語(yǔ)
樹(shù)形選擇排序還是比較好理解，圖和文字結(jié)合就比較容易結(jié)合。
到此這篇關(guān)于Python 選擇排序中的樹(shù)形選擇排序的文章就介紹到這了,更多相關(guān)Python 樹(shù)形選擇排序內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
