第3節(jié)選擇類排序(專業(yè)版)
【正文】 167。 } return。第九章 排序技術(shù) 基本思想： 在待排記錄中依次選擇關(guān)鍵字最小的記錄作為有序序列的最后一條記錄，逐漸縮小范圍直至全部記錄選擇完畢。} //SelectSort 167。 選擇類排序 ： 從無序序列的第 n/2 個元素（即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進(jìn)行反復(fù)篩選。 選擇類排序 ： 如何由一個無序序列建成一個堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？ —— 篩選 方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。} //p[i]←→p[j]。 167。 選擇類排序 對 n 個記錄進(jìn)行簡單選擇排序，所需進(jìn)行的 關(guān)鍵字間的比較次數(shù) 總計為： ?時間復(fù)雜度為 O(n2) ?序列存儲：順序、鏈?zhǔn)? ?是一種穩(wěn)定的排序方法 2)1()(11??????nninni167。 80 75 40 62 73 28 35 50 38 25 47 15 建堆是一個從下往上進(jìn)行“篩選”的過程。 選擇類排序 76 65 97 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 65 76 27
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1