數(shù)據(jù)結(jié)構(gòu)(c語言版)課件-第八章-排序-(嚴(yán)蔚敏、吳偉民編-清華大學(xué)出版社)(編輯修改稿)
2024-09-11 23:38 本頁面
【文章內(nèi)容簡介】 (76 97 65 50) 分別進(jìn)行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 97 49 27i i j i j 49 65j 13 49i 49 97i j ?算法描述 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ?最好情況（每次總是選到中間值作樞軸） T(n)=O(nlog2n) ?最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n178。) ? 空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸 ?最壞情況： S(n)=O(n) ?一般情況： S(n)=O(log2n) T(n)=O(n178。) ? 選擇排序 ? 簡單選擇排序 ?排序過程 ? 首先通過 n1次關(guān)鍵字比較，從 n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換 ? 再通過 n2次比較，從剩余的 n1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換 ? 重復(fù)上述操作，共進(jìn)行 n1趟排序后，排序結(jié)束 例 初始： [ 49 38 65 97 76 13 27 ] k j j j j j j k k i=1 13 49 一趟： 13 [38 65 97 76 49 27 ] i=2 k k j j j j j 27 38 二趟： 13 27 [65 97 76 49 38 ] 三趟： 13 27 38 [97 76 49 65 ] 四趟： 13 27 38 49 [76 97 65 ] 五趟： 13 27 38 49 65 [97 76 ] 六趟： 13 27 38 49 65 76 [97 ] 排序結(jié)束： 13 27 38 49 65 76 97 ?算法描述 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ?記錄移動(dòng)次數(shù) ?最好情況： 0 ?最壞情況： 3(n1) ?比較次數(shù)： )(21)( 211nninni??????? 空間復(fù)雜度： S(n)=O(1) T(n)=O(n178。) ? 堆排序 ?堆的定義： n個(gè)元素的序列 (k1,k2,……kn) ， 當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆 或 (i=1,2,…... ?n/2?) ki?k2i ki?k2i+1 ki?k2i ki?k2i+1 例 （ 96， 83， 27， 38， 11， 9） 例 （ 13， 38， 27， 50， 76， 65， 49， 97） 96 27 9 11 38 83 13 27 38 49 65 76 50 97 可將堆序列看成完全二叉樹，則堆頂 元素（完全二叉樹的根）必為序列中 n個(gè)元素的最小值或最大值 ?堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余?n1個(gè)元素重又建成一個(gè)堆，則可得到 n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過程叫 ~ ?堆排序需解決的兩個(gè)問題： ? 如何由一個(gè)無序序列建成一個(gè)堆？ ? 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？ ?第二個(gè)問題解決方法 —— 篩選 ? 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選” 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 輸出： 13 27 49 38 97 65 76 50 13 輸出： 13 97 49 38 27 65 76 50 13 輸出： 13 27 38 49 50 27 65 76 97 13 輸出： 13 27 65 49 50 27 38 76 97 13 輸出： 13 27 38 49 65 50 27 38 76 97 13 輸出： 13 27 38 76 65 50 27 38 49 97 13 輸出： 13 27 38 49
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1