[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第9章排序中國(guó)石油大學(xué)華東-在線瀏覽
2024-12-06 04:12本頁(yè)面
【正文】 ① 任取 待排序元素序列中的某個(gè)元素作為 基準(zhǔn)（支點(diǎn)，一般去第一個(gè)） ，按照該元素的排序碼大小，將整個(gè)元素序列劃分為 左右兩個(gè)子序列 ： ? 左側(cè)子序列中所有元素的都小于基準(zhǔn)元素 ? 右側(cè)子序列中所有元素的都大于基準(zhǔn)元素 ② 基準(zhǔn)元素則排在這兩個(gè)子序列中間 (這也是該元素 最終應(yīng)安放的位置 )。 快速排序 (Quick Sort) 做法： 附設(shè)兩個(gè)指針 low和 high ，初值分別指向 第一個(gè)記錄和 最后一個(gè)記錄 ，設(shè) 支點(diǎn)記錄 為 r[1] ， (r[1]通常取第一個(gè)記錄的值為基準(zhǔn)值。 例 初始關(guān)鍵字： 49 38 65 97 76 13 27 50 L H r[1] .KEY=49 H 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序 : ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 97 4927L L H L 49 65H 13 49 49 97L H 20 選擇排序 基本思想是 : ? 首先從 1~n個(gè)元素中選出關(guān)鍵字 最小 的記錄交換到 第一個(gè) 位置上。 ? 時(shí)間復(fù)雜度為 O(n2)， ? 適用于 待排序元素較少 的情況。 for (i=0,in。jn。 if(k!=i) { t=L[i]。 L[k]=t ； } } } 堆排序 (Heap Sort) 堆 :是具有特定條件的順序存儲(chǔ)的 完全二叉樹(shù) ，其特定條件是： 任何一個(gè)非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。首先將這 n個(gè)元素按關(guān)鍵字建成堆，將堆頂元素輸出，得到 n個(gè)元素中關(guān)鍵字最小 (或最大 )的元素。如此反復(fù)，便得到一個(gè)按關(guān)鍵字有序的序列。 堆排序分為兩個(gè)步驟 : 1）如何由一個(gè)無(wú)序序列建成一個(gè)堆？ 2）輸出堆頂元素后，如何將剩余元素調(diào)整成一個(gè)新的堆？ 24 (1)第二個(gè)問(wèn)題解決方法 —— 篩選 65 25 36 56 49 78 41 11 (b) 65 36 56 49 78 41 11 (c) 25 11 25 36 56 49 78 41 65 (a) 25 49 36 56 65 78 41 (d) 11 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并 與其中小者進(jìn)行交換 ；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“ 篩選 ” 25 （ 2） 第一個(gè)問(wèn)題解決方法 從無(wú)序序列的第 ?n/2?個(gè)元素（即此無(wú)序序列對(duì)應(yīng)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選 25 56 49 78 11 65 41 36 (a)無(wú)序序列 n=8, int(n/2)=4開(kāi)始 25 56 49 36 11 65 41 78 (b): 78被篩選后的狀態(tài) 25 56 41 36 11 65 49 78 (c): 49被篩選后的狀態(tài) 25 11 41 36 56 65 49 78 (d): 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1