算法與數(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ū)只有一個元素為止.
........