排序算法實驗報告(編輯修改稿)
2024-08-28 21:18 本頁面
【文章內容簡介】 選。如圖：再討論對n 個元素初始建堆的過程。建堆方法：對初始序列建堆的過程，就是一個反復進行篩選的過程。1）n 個結點的完全二叉樹，則最后一個結點是第個結點的子樹。2）篩選從第個結點為根的子樹開始，該子樹成為堆。3）之后向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。如圖建堆初始過程：無序序列：（49，38，65，97，76，13，27，49）算法的實現(xiàn)：從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆的滲透函數(shù)，二是反復調用滲透函數(shù)實現(xiàn)排序的函數(shù)。時效分析：設樹深度為k。從根到葉的篩選，元素比較次數(shù)至多2(k1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：而建堆時的比較次數(shù)不超過4n 次，因此堆排序最壞情況下，時間復雜度也為：O(nlogn )。5. 交換排序—冒泡排序（Bubble Sort） 基本思想：在要排序的一組數(shù)中，對當前還未排好序的范圍內的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進行比較和調整，讓較大的數(shù)往下沉，較小的往上冒。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。冒泡排序的示例：6. 交換排序—快速排序（Quick Sort）基本思想：1）選擇一個基準元素,通常選擇第一個元素或者最后一個元素,2）通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值比基準值大。3）此時基準元素在其排好序后的正確位置4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進行排序，直到整個序列有序?？焖倥判虻氖纠海╝） 一趟排序的過程：（b） 排序的全過程：時效分析： 快速排序是通常被認為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準記錄，即將排序區(qū)間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄?？焖倥判蚴且粋€不穩(wěn)定的排序方法。7. 歸并排序（Merge Sort）基本思想： 歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。歸并排序示例：算法的實現(xiàn)： 1 個元素的表總是有序的。所以對n 個元素的待排序列，每個元素可看成1 個有序子表。對子表兩兩合并生成n/2個子表，所得子表除最后一個子表長度可能為1 外，其余子表長度均為2。再進行兩兩合并，直到生成n 個元素按關鍵碼有序的表。8. 桶排序/基數(shù)排序(Radix Sort)基本思想： 是按照低位先排序，然后收集；再按照高位排序
法律信息相關推薦
鄂ICP備17016276號-1