第3節(jié)選擇類(lèi)排序(文件)
【正文】 167。 選擇類(lèi)排序 ： 如何由一個(gè)無(wú)序序列建成一個(gè)堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？ —— 篩選 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選”。 167。 選擇類(lèi)排序 。 49 65 38 27 13 76 97 50 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 50 50 97 13 65 38 13 27 49 49 13 38 27 65 76 50 97 時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn) 空間復(fù)雜度： S(n)=O(1) 堆排序的性能： 堆排序是不穩(wěn)定的； 堆排序適用于 n 較大的情況。 選擇類(lèi)排序 ： 從無(wú)序序列的第 n/2 個(gè)元素（即此無(wú)序序列對(duì)應(yīng)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選。 選擇類(lèi)排序 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 輸出： 13 27 49 38 97 65 76 50 13 輸出： 13 97 49
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1