廣東省汕頭市金山中學(xué)高中信息技術(shù)信息學(xué)競(jìng)賽班數(shù)據(jù)結(jié)構(gòu)專項(xiàng)培

1、內(nèi)部排序在數(shù)據(jù)結(jié)構(gòu)里，排序一般分為：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序五種。寫在前面的話：在看下面的各種算法之前，請(qǐng)先想想，如果給你一個(gè)無序的數(shù)列，你如何去排序？設(shè)計(jì)出你自己的算法。還有沒有其它方法？ 相信自己的能力，排序算法是連小學(xué)生都可以設(shè)計(jì)出的！不希望以后聽到這樣的話：“排序的算法我忘了”，排序算法不是背出來的！§9.1 插入排序 (Insertion Sort)基本思想：   每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。排序過程： 【示例】： 初始關(guān)鍵字 49 38 6

2、5 97 76 13 27 49     J=2(38) 38 49 65 97 76 13 27 49     J=3(65) 38 49 65 97 76 13 27 49     J=4(97) 38 49 65 97 76 13 27 49     J=5(76) 38 49 65 76 97 13 27 49     J=6(13) 13 38 49 65 76 97 27 49

3、0;    J=7(27) 13 27 38 49 65 76 97 49     J=8(49) 13 27 38 49 49 65 76 97 §9.2 選擇排序基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。排序過程：【示例】：    初始關(guān)鍵字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第

4、三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序結(jié)果 13 27 38 49 49 76 76 97§9.3 冒泡排序 (BubbleSort)基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。排序過程：設(shè)想被排序的數(shù)組R1.N垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)

5、輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。【示例】： 49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 【練習(xí)1】 請(qǐng)分別用以上三種算法完成

6、。同學(xué)們進(jìn)行了身體素質(zhì)測(cè)量，其中立位體前屈的成績是以XX . XX cm來記錄的，這個(gè)成績不可能超過100，當(dāng)有可能為負(fù)數(shù)（當(dāng)指尖碰不到足時(shí)），現(xiàn)有若干同學(xué)的成績，請(qǐng)幫他們排序。輸入： 第一行 正整數(shù) n （有n個(gè)同學(xué)） 第二行 n個(gè)成績 輸出： n個(gè)成績從大到小的排列§9.4 快速排序 (Quick Sort)基本思想：在當(dāng)前無序區(qū)R1.H中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)元素"，用此基準(zhǔn)元素將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序區(qū)：R1.I-1和RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)元素則位

7、于最終排序的位置I上，即R1.I-1RIRI+1.H(1IH)，當(dāng)R1.I-1和RI+1.H均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂Ｅ判蜻^程：將數(shù)列從小到大排序以第一個(gè)元素作為基準(zhǔn)，設(shè)兩指針i和j，初始時(shí)i指向區(qū)間第一個(gè)元素，j指向最末一個(gè)元素；先移動(dòng)j指針，如果j元素比i元素大，j指針前移，否則若j小于i，則交換i和j 。交換i和j后，移動(dòng)i指針，如果i元素比j元素小，i指針后移，否則若i大于j，則交換i和j 。再移動(dòng)j指針，輪流移動(dòng)i指針和j指針，直到j(luò) = i 。ij將數(shù)列分成兩部分，分別進(jìn)行上述過程。【示例】： 初始關(guān)鍵字 ，j指針左移 49

8、38 65 97 76 13 27 49ij第一次交換后 ，j指針不動(dòng)，i指針右移 27 38 65 97 76 13 49 49ij第二次交換后 ，i指針不動(dòng)，j指針左移 27 38 49 97 76 13 65 49 ji第三次交換后 ，j指針不動(dòng)，i指針右移 27 38 13 97 76 49 65 49jiij第四次交換后，i指針不動(dòng)，j指針左移 27 38 13 49 76 97 65 49j指針左移，遇i指針 27 38 13 49 76 97 65 49（遞歸過程） 初始關(guān)鍵字 49 38 65 97 76 13 27 49一趟排序之后 27 38 13 49 76 97 65

9、49 二趟排序之后 13 27 38 49 49 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序結(jié)果 13 27 38 49 49 65 76 97 參考程序：Procedure Parttion(L, H : Integer; var I : integer);對(duì)無序區(qū)RL,H做劃分，I返回出本次劃分后已被定位的基準(zhǔn)元素的位置beginI:=L; J:=H; X:=RI; 初始化Repeat While (RJ>=X) And (I<J) Do J:=J1; J指針左移，查找第1個(gè)小于基準(zhǔn)的元素 If I<J Then RI:=RJ; 相

10、當(dāng)于交換RI和RJWhile (RI<=RJ) And (I<J) Do I:=I+1; I指針右移，查找第1個(gè)大于基準(zhǔn)的元素 If I<J Then RJ:=RI; Until I=J;RI:=X; 基準(zhǔn)X已被最終定位end; ParttionProcedure QuickSort(S,T:Integer); 對(duì)RS.T快速排序beginIf S<T Then begin 當(dāng)RS.T為空或只有一個(gè)元素是無需排序 Partion (S,T,I); 對(duì)RS.T做劃分,返回I QuickSort (S,I-1); 遞歸處理左區(qū)間RS,I-1 QuickSort (I+1,T

11、); 遞歸處理右區(qū)間RI+1,Tend;end; QuickSort【練習(xí)2】請(qǐng)將給出的單詞按字典排序。 （利用字符串比較） 輸入：從文件word.in讀入 第一行 正整數(shù)n 以下n行 每行一個(gè)單詞 輸出：寫入文件word.out中按字典排序，每行一個(gè)單詞§9.5 堆排序 (Heap Sort)基本思想：堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。堆的定義: N個(gè)元素的序列K1, K2, K3, , Kn. 稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：    K

12、iK2i KiK2i+1 (1 i N/2)堆實(shí)質(zhì)上是滿足如下性質(zhì)的二叉樹：是一棵完全二叉樹；2 樹中任一結(jié)點(diǎn)的值均大于等于（小于等于）其孩子結(jié)點(diǎn)的值；3 樹根的值是最大的（最小的）例如序列10, 15, 56, 25, 30, 70就是一個(gè)堆，它對(duì)應(yīng)的完全二叉樹如下圖所示。這種堆中根結(jié)點(diǎn)（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。這棵二叉樹的存儲(chǔ)，既可以用鏈表的方式存儲(chǔ)，也可以用順序表（一維數(shù)組S）的方式存儲(chǔ)。采用順序表的存儲(chǔ)結(jié)構(gòu)如上圖所示，若某結(jié)點(diǎn)為S i ，則其左右子樹分別為S 2i 和S 2i+1 。

13、 堆的調(diào)整： 在介紹從一個(gè)無序序列建堆的方法前，我們先看如何在一個(gè)已建成的堆中，若在輸出堆頂?shù)淖钚≈抵?，調(diào)整剩余的n-1個(gè)元素的序列，重又建成一個(gè)一個(gè)堆。設(shè)圖91為一個(gè)幾建成的小根堆。圖91輸出堆頂元素后，以堆中最后元素代替之，如圖92 (a)。此時(shí)根結(jié)點(diǎn)的左右子樹均為堆，則僅需自上而下進(jìn)行調(diào)整即可。首先以新堆頂元素與其左右子樹根結(jié)點(diǎn)的值比較，由于右子樹根結(jié)點(diǎn)的值小于左子樹根結(jié)點(diǎn)的值，且小于根結(jié)點(diǎn)的值，則將根結(jié)點(diǎn)的值69與右子樹根結(jié)點(diǎn)的值11交換， 如圖92 (b)。由于69替代了11之后破壞了右子樹的“堆”，需進(jìn)行和上述相同的調(diào)整，直至葉子結(jié)點(diǎn)。調(diào)整后的狀態(tài)如圖92 (c)。這個(gè)過程可稱為

14、“篩”。( a )( b )( c )圖92 調(diào)制建新堆的過程 輸出堆頂元素后的調(diào)整過程如下：procedure sift ( var S : array 1.n of integer ; k , m : integer ); 假設(shè)Sk+1. . m為小根堆，調(diào)整Sk使整個(gè)序列Sk . . m滿足堆的性質(zhì) begin i:=k; j:=2*i; x:=Sk; finish:=false; while (j<=m) and (finish=false) do begin if (j<m) and (S j >S j+1 ) then j:=j+1; 若存在右子樹，且右子樹根結(jié)點(diǎn)

15、的值更小，則沿右分支調(diào)整 if x<=S j then finish:=true else begin S i  := S j ; i :=j  j :=2*i  end; end; whie S i :=x;end;排序過程：從一個(gè)無序序列建堆的過程就是一個(gè)反復(fù)調(diào)整的過程。將無序數(shù)列看成一棵完全二叉樹，從最后一個(gè)非葉子結(jié)點(diǎn)i開始進(jìn)行調(diào)整以該結(jié)點(diǎn)為根的子樹，然后在調(diào)整以i-1為根的子樹， 這樣，在原序列的尾部形成有序區(qū)并逐步向前擴(kuò)大到整個(gè)序列?！纠浚簩?duì)無序序列42，13，91，23，24，16，05，88建立大跟堆 【練習(xí)】對(duì)輸入的無序序列進(jìn)行堆排序。輸入： 第一行： n 第二行： n個(gè)整數(shù)輸出： 將n個(gè)整數(shù)按從小到大排序輸出§9.6 排序算法的比較和選擇 1. 選取排序方法需要考慮的因素：(1) 待排序的元素?cái)?shù)目n；(2) 元素本身信息量的大?。?3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況；(4) 語言工具的條件，輔助空間的大小等。2. 小結(jié)：(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動(dòng)操作較直接選擇排序多，因而當(dāng)記錄本身信息量較大時(shí)，用直接選擇排序較好。(2) 若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒