畢業(yè)論文標(biāo)準(zhǔn)WORD格式排版 13頁

一． 設(shè)計題目：
堆排序的算法

二．運(yùn)行環(huán)境：
1、 硬件：計算機(jī)
2、 軟件：Microsoft Visual C++6.0

三．目的和意義：
目的：創(chuàng)建一個大堆，按從大到小順序輸出堆元素，實現(xiàn)堆排序。
意義：利用堆排序，即使在最壞情況下的時間復(fù)雜度也是O(nlog2n)，相對于快速排序來說，時間復(fù)雜度小，這是堆排序的最大優(yōu)點，可用于對若干元素進(jìn)行排序，加快排序速度。

四．算法設(shè)計的基本思想：
堆排序算法設(shè)計基本思想：
堆排序利用了大根堆堆頂記錄的關(guān)鍵字最大這一特征，使得在當(dāng)前無序區(qū)中選取最大關(guān)鍵字的記錄變得簡單。先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)。再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄r[n]交換，由此得到新的無序區(qū)r[1..n-1]和有序區(qū)r[n]，且滿足r[1..n-1].keys≤r[n].key。由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)r[1..n-1]調(diào)整為堆。然后再次將r[1..n-1]中關(guān)鍵字最大的記錄r[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)r[1..n-2]和有序區(qū)r[n-1..n]，且仍滿足關(guān)系r[1..n-2].keys≤r[n-1..n].keys，同樣要將r[1..n-2]調(diào)整為堆。直到無序區(qū)只有一個元素為止.
........