排序算法實(shí)驗(yàn)報(bào)告-文庫吧資料
2024-08-14 21:18本頁面
【正文】 集；再按照高位排序，然后再收集；依次類推，直到最高位。對(duì)子表兩兩合并生成n/2個(gè)子表，所得子表除最后一個(gè)子表長度可能為1 外，其余子表長度均為2。歸并排序示例：算法的實(shí)現(xiàn)： 1 個(gè)元素的表總是有序的。7. 歸并排序（Merge Sort）基本思想： 歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。為改進(jìn)之，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄?？焖倥判虻氖纠海╝） 一趟排序的過程：（b） 排序的全過程：時(shí)效分析： 快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的。元素值比基準(zhǔn)值大。6. 交換排序—快速排序（Quick Sort）基本思想：1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,2）通過一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。而建堆時(shí)的比較次數(shù)不超過4n 次，因此堆排序最壞情況下，時(shí)間復(fù)雜度也為：O(nlogn )。從根到葉的篩選，元素比較次數(shù)至多2(k1)次，交換記錄至多k 次。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。算法的實(shí)現(xiàn)：從算法描述來看，堆排序需要兩個(gè)過程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。如圖建堆初始過程：無序序列：（49，38，65，97，76，13，27，49）2）篩選從第個(gè)結(jié)點(diǎn)為根的子樹開始，該子樹成為堆。建堆方法：對(duì)初始序列建堆的過程，就是一個(gè)反復(fù)進(jìn)行篩選的過程。稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過程為篩選。3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)，則重復(fù)方法 （2）.4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。將堆底元素送入堆頂（（最后一個(gè)元素與堆頂進(jìn)行交換），堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。首先討論第二個(gè)問題：輸出堆頂元素后，對(duì)剩余n1元素重新建成堆的調(diào)整過程。稱這個(gè)過程為堆排序。然后對(duì)前面(n1)個(gè)元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個(gè)元素中次小(或次大)的元素。 (b)若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的?；舅枷耄憾训亩x如下：具有n個(gè)元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足時(shí)稱之為堆。簡單選擇排序的示例：操作方法：第一趟，從n 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換；第二趟，從第二個(gè)記錄開始的n1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；以此類推.....第i 趟，則從第i 個(gè)記錄開始的ni+1 個(gè)記錄中選出關(guān)鍵碼最小的記錄與第i 個(gè)記錄交換，直到整個(gè)序列按關(guān)鍵碼有序。希爾排序方法是一個(gè)不穩(wěn)定的排序方法。目前還沒有人給出選取最好的增量因子序列的方法。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序。希爾排序的示例：算法的實(shí)現(xiàn)： 我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1}操作方法：1. 選擇一個(gè)增量序列t1，t2，…，tk，其中titj，tk=1；2. 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；3. 每趟排
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1