排序算法實(shí)驗(yàn)報(bào)告-文庫吧
2025-07-17 21:18 本頁面
【正文】 長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。希爾排序的示例：算法的實(shí)現(xiàn)： 我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1}n為要排序數(shù)的個數(shù)即：先將要排序的一組記錄按某個增量d（n/2,n為要排序數(shù)的個數(shù)）分成若干組子序列，然后再用一個較小的增量（d/2）對它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序。時效分析：希爾排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。3. 選擇排序—簡單選擇排序（Simple Selection Sort） 基本思想： 在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數(shù)交換，依次類推，直到第n1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。簡單選擇排序的示例：操作方法：第一趟，從n 個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；以此類推.....第i 趟，則從第i 個記錄開始的ni+1 個記錄中選出關(guān)鍵碼最小的記錄與第i 個記錄交換，直到整個序列按關(guān)鍵碼有序。4. 選擇排序—堆排序（Heap Sort）堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)?；舅枷耄憾训亩x如下：具有n個元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項(xiàng)（小頂堆）。若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的。如：（a）大頂堆序列：（96, 83,27,38,11,09) (b) 小頂堆序列：（12，36，24，85，47，30，53，91）初始時把要排序的n個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹），調(diào)整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素，這時堆的根節(jié)點(diǎn)的數(shù)最小（或者最大）。然后對前面(n1)個元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節(jié)點(diǎn)的堆，并對它們作交換，最后得到有n個節(jié)點(diǎn)的有序序列。稱這個過程為堆排序。因此，實(shí)現(xiàn)堆排序需解決兩個問題：1. 如何將n 個待排序的數(shù)建成堆；2. 輸出堆頂元素后，怎樣調(diào)整剩余n1 個元素，使其成為一個新堆。首先討論第二個問題：輸出堆頂元素后，對剩余n1元素重新建成堆的調(diào)整過程。調(diào)整小頂堆的方法：1）設(shè)有m 個元素的堆，輸出堆頂元素后，剩下m1 個元素。將堆底元素送入堆頂（（最后一個元素與堆頂進(jìn)行交換），堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。2）將根結(jié)點(diǎn)與左、右子樹中較小元素的進(jìn)行交換。3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)，則重復(fù)方法 （2）.4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。則重復(fù)方法 （2）.5）繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。稱這個自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過程為篩
法律信息相關(guān)推薦
鄂ICP備17016276號-1