第3節(jié)選擇類排序-資料下載頁(yè)
2025-07-22 09:55本頁(yè)面
【正文】 選擇類排序 ： 如何由一個(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。 選擇類排序 ： 從無(wú)序序列的第 n/2 個(gè)元素（即此無(wú)序序列對(duì)應(yīng)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選。 80 75 40 62 73 28 35 50 38 25 47 15 建堆是一個(gè)從下往上進(jìn)行“篩選”的過(guò)程。 167。 選擇類排序 示例 3： 將下列元素（ 49， 38， 65， 97， 76， 13， 27， 50）建堆。 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 較大的情況。 167。 選擇類排序
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1