算法與數(shù)據(jù)結構程設計報告.doc
約13頁DOC格式手機打開展開
算法與數(shù)據(jù)結構程設計報告,畢業(yè)論文標準word格式排版 13頁一． 設計題目： 堆排序的算法二．運行環(huán)境：1、 硬件：計算機2、 軟件：microsoft visual c++6.0三．目的和意義：目的：創(chuàng)建一個大堆，按從大到小順序輸出堆元素，實現(xiàn)堆排序。意義：利用堆排序，即使在最壞情況下的時間復雜度也是o(nlog2n)，相對于快速排序來說，...
內容介紹
此文檔由會員 莎士比亞 發(fā)布
畢業(yè)論文標準WORD格式排版 13頁
一． 設計題目：
堆排序的算法
二．運行環(huán)境：
1、 硬件：計算機
2、 軟件：Microsoft Visual C++6.0
三．目的和意義：
目的：創(chuàng)建一個大堆，按從大到小順序輸出堆元素，實現(xiàn)堆排序。
意義：利用堆排序，即使在最壞情況下的時間復雜度也是O(nlog2n)，相對于快速排序來說，時間復雜度小，這是堆排序的最大優(yōu)點，可用于對若干元素進行排序，加快排序速度。
四．算法設計的基本思想：
堆排序算法設計基本思想：
堆排序利用了大根堆堆頂記錄的關鍵字最大這一特征，使得在當前無序區(qū)中選取最大關鍵字的記錄變得簡單。先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)。再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄r[n]交換，由此得到新的無序區(qū)r[1..n-1]和有序區(qū)r[n]，且滿足r[1..n-1].keys≤r[n].key。由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)r[1..n-1]調整為堆。然后再次將r[1..n-1]中關鍵字最大的記錄r[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)r[1..n-2]和有序區(qū)r[n-1..n]，且仍滿足關系r[1..n-2].keys≤r[n-1..n].keys，同樣要將r[1..n-2]調整為堆。直到無序區(qū)只有一個元素為止.
........
一． 設計題目：
堆排序的算法
二．運行環(huán)境：
1、 硬件：計算機
2、 軟件：Microsoft Visual C++6.0
三．目的和意義：
目的：創(chuàng)建一個大堆，按從大到小順序輸出堆元素，實現(xiàn)堆排序。
意義：利用堆排序，即使在最壞情況下的時間復雜度也是O(nlog2n)，相對于快速排序來說，時間復雜度小，這是堆排序的最大優(yōu)點，可用于對若干元素進行排序，加快排序速度。
四．算法設計的基本思想：
堆排序算法設計基本思想：
堆排序利用了大根堆堆頂記錄的關鍵字最大這一特征，使得在當前無序區(qū)中選取最大關鍵字的記錄變得簡單。先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)。再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄r[n]交換，由此得到新的無序區(qū)r[1..n-1]和有序區(qū)r[n]，且滿足r[1..n-1].keys≤r[n].key。由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)r[1..n-1]調整為堆。然后再次將r[1..n-1]中關鍵字最大的記錄r[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)r[1..n-2]和有序區(qū)r[n-1..n]，且仍滿足關系r[1..n-2].keys≤r[n-1..n].keys，同樣要將r[1..n-2]調整為堆。直到無序區(qū)只有一個元素為止.
........
