2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法

上傳人:xt****7 文檔編號(hào):105277558 上傳時(shí)間:2022-06-11 格式:DOC 頁數(shù):8 大小:24.52KB
收藏 版權(quán)申訴 舉報(bào) 下載
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法_第1頁
第1頁 / 共8頁
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法_第2頁
第2頁 / 共8頁
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法_第3頁
第3頁 / 共8頁

下載文檔到電腦,查找使用更方便

9.9 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法》由會(huì)員分享,可在線閱讀,更多相關(guān)《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法(8頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 排序算法 ? 一、插入排序(Insertion Sort) 1. 基本思想: ???? 每次將一個(gè)待排序的數(shù)據(jù)元素,插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置,使數(shù)列依然有序;直到待排序數(shù)據(jù)元素全部插入完為止。 2. 排序過程:  【示例】: [初始關(guān)鍵字] [49] 38 65 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

2、27 49 ????J=5(76) [38 49 65 76 97] 13 27 49 ????J=6(13) [13 38 49 65 76 97] 27 49 ????J=7(27) [13 27 38 49 65 76 97] 49 ????J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //對(duì)R[1..N]按遞增序進(jìn)行插入排序, R[0]是監(jiān)視哨// ??Begin ????for I := 2 To N Do ?????//依次插入R[2],...,R[n]// ?

3、???begin ??????R[0] := R[I]; J := I - 1; ??????While R[0] < R[J] Do ??//查找R[I]的插入位置// ???????begin ????????R[J+1] := R[J]; ??????//將大于R[I]的元素后移// ????????J := J - 1 ???????end ??????R[J + 1] := R[0] ; ?????//插入R[I] // ????end ??End; ?????????????????//InsertSort // ? 二、選擇排序 1. 基本思想:   每

4、一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素,順序放在已排好序的數(shù)列的最后,直到全部待排序的數(shù)據(jù)元素排完。 2. 排序過程: 【示例】: ??初始關(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] 第三趟排序后 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

5、49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結(jié)果 13 27 38 49 49 76 76 97 Procedure SelectSort(Var R : FileType); ?????//對(duì)R[1..N]進(jìn)行直接選擇排序 // ??Begin ????for I := 1 To N - 1 Do ?????????????????//做N - 1趟選擇排序// ?????begin ??????K := I; ??????For J := I + 1 To N Do ???????????????//在當(dāng)前無序區(qū)R

6、[I..N]中選最小的元素R[K]// ???????begin ????????If R[J] < R[K] Then K := J ???????end; ??????If K <> I Then ?????????????????????//交換R[I]和R[K] // ????????begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end; ?????end ??End.?????????????????????????????? //SelectSort // ? 三、冒泡排序(BubbleSort) 1. 基本思想

7、:   兩兩比較待排序數(shù)據(jù)元素的大小,發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換,直到?jīng)]有反序的數(shù)據(jù)元素為止。 2. 排序過程:   設(shè)想被排序的數(shù)組R[1..N]垂直豎立,將每個(gè)數(shù)據(jù)元素看作有重量的氣泡,根據(jù)輕氣泡不能在重氣泡之下的原則,從下往上掃描數(shù)組R,凡掃描到違反本原則的輕氣泡,就使其向上"漂浮",如此反復(fù)進(jìn)行,直至最后任何兩個(gè)氣泡都是輕者在上,重者在下為止。 【示例】: 49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 9

8、7 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 Procedure BubbleSort(Var R : FileType) //從下往上掃描的起泡排序// Begin ??For I := 1 To N-1 Do ??//做N-1趟排序// ???begin ?????NoSwap := True; ???//置未排序的標(biāo)志// ?????For J := N - 1 DownTo 1 Do ???//從底部往上掃描// ??????b

9、egin ???????If R[J+1]< R[J] Then ???//交換元素// ????????begin ?????????Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp; ?????????NoSwap := False ????????end; ??????end; ?????If NoSwap Then Return??? //本趟排序中未發(fā)生交換,則終止算法// ????end End.????????????????????? //BubbleSort// 四、快速排序(Quick Sort) 1. 基本思

10、想:   在當(dāng)前無序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X),用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序區(qū):R[1..I-1]和R[I+1..H],且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素,右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素,而基準(zhǔn)X則位于最終排序的位置上,即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí),分別對(duì)它們進(jìn)行上述的劃分過程,直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂? 2. 排序過程: 【示例】: 初始關(guān)鍵字 [49 38 65 97 76 13 27 49] 第一次

11、交換后 [27 38 65 97 76 13 49 49] 第二次交換后 [27 38 49 97 76 13 65 49] J向左掃描,位置不變,第三次交換后 [27 38 13 97 76 49 65 49] I向右掃描,位置不變,第四次交換后 [27 38 13 49 76 97 65 49] J向左掃描 [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 49] 二趟排序之后 [13] 27 [38] 49 [49 6

12、5]76 [97] 三趟排序之后 13 27 38 49 49 [65]76 97 最后的排序結(jié)果 13 27 38 49 49 65 76 97 各趟排序之后的狀態(tài) Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer); //對(duì)無序區(qū)R[1,H]做劃分,I給以出本次劃分后已被定位的基準(zhǔn)元素的位置 // Begin ??I := 1; J := H; X := R[I] ;?? //初始化,X為基準(zhǔn)// ??Repeat ????While (R[J] >= X) And (I < J)

13、Do ??????begin ???????J := J - 1 ???????//從右向左掃描,查找第1個(gè)小于 X的元素// ???????If I < J Then ????//已找到R[J] 〈X// ?????????begin ??????????R[I] := R[J]; ??//相當(dāng)于交換R[I]和R[J]// ??????????I := I + 1 ?????????end; ???????While (R[I] <= X) And (I < J) Do ??????????I := I + 1 ?????//從左向右掃描,查找第1個(gè)大于 X的元素///

14、??????end; ?????If I < J Then ???//已找到R[I] > X // ???????begin ????????R[J] := R[I]; ????//相當(dāng)于交換R[I]和R[J]// ????????J := J - 1 ???????end ??Until I = J; ??R[I] := X ??????//基準(zhǔn)X已被最終定位// End; ??????????//Parttion // Procedure QuickSort(Var R :FileType; S,T: Integer); //對(duì)R[S..T]快速排序// Begin ?

15、?If S < T Then ???//當(dāng)R[S..T]為空或只有一個(gè)元素是無需排序// ????begin ??????Partion(R, S, T, I); ???//對(duì)R[S..T]做劃分// ??????QuickSort(R, S, I-1);? //遞歸處理左區(qū)間R[S,I-1]// ??????QuickSort(R, I+1,T);? //遞歸處理右區(qū)間R[I+1..T] // ????end; End.???????????????? ?//QuickSort// ? 五、堆排序(Heap Sort) 1. 基本思想: ??? ?堆排序是一樹形選擇排序,

16、在排序過程中,將R[1..N]看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu),利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。 2. 堆的定義: N個(gè)元素的序列K1,K2,K3,...,Kn.稱為堆,當(dāng)且僅當(dāng)該序列滿足特性: ?????? Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2]) ???? 堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹:樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個(gè)堆,它對(duì)應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點(diǎn)(稱為堆頂)的關(guān)鍵字最小,我們把它稱為小根堆。反之,若完全二叉樹中任一非葉子結(jié)點(diǎn)的關(guān)

17、鍵字均大于等于其孩子的關(guān)鍵字,則稱之為大根堆。 3. 排序過程: ??? 堆排序正是利用小根堆(或大根堆)來選取當(dāng)前無序區(qū)中關(guān)鍵字小(或最大)的記錄實(shí)現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是:將當(dāng)前無序區(qū)調(diào)整為一個(gè)大根堆,選取關(guān)鍵字最大的堆頂記錄,將它和無序區(qū)中的最后一個(gè)記錄交換。這樣,正好和直接選擇排序相反,有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個(gè)記錄區(qū)。 【示例】:對(duì)關(guān)鍵字序列42,13,91,23,24,16,05,88建堆 Procedure Sift(Var R :FileType; I, M : Integer); //在數(shù)組R[I..M]中調(diào)

18、用R[I],使得以它為完全二叉樹構(gòu)成堆。事先已知其左、右子樹(2I+1 <=M時(shí))均是堆// Begin ??X := R[I]; J := 2*I; ???????????//若J <=M, R[J]是R[I]的左孩子// ??While J <= M Do ???????????//若當(dāng)前被調(diào)整結(jié)點(diǎn)R[I]有左孩子R[J]// ???begin ????If (J < M) And R[J].Key < R[J+1].Key Then ??????J := J + 1 ????????????????//令J指向關(guān)鍵字較大的右孩子// ????????????????????

19、????????? ??//J指向R[I]的左、右孩子中關(guān)鍵字較大者// ????If X.Key < R[J].Key Then ????//孩子結(jié)點(diǎn)關(guān)鍵字較大// ??????begin ????????R[I] := R[J]; ?????????????//將R[J]換到雙親位置上// ????????I := J ; J := 2*I ???????????//繼續(xù)以R[J]為當(dāng)前被調(diào)整結(jié)點(diǎn)往下層調(diào)整// ??????end; ?????Else ??????Exit????????????????? //調(diào)整完畢,退出循環(huán)// ???end ??R[I] := X

20、;?????????????? //將最初被調(diào)整的結(jié)點(diǎn)放入正確位置// End;//Sift// Procedure HeapSort(Var R : FileType); ???????//對(duì)R[1..N]進(jìn)行堆排序//  Begin   For I := N Div Downto 1 Do?????????????? //建立初始堆//    Sift(R, I , N)   For I := N Downto 2 do ?????????????????//進(jìn)行N-1趟排序//    begin     T := R[1]; R[1] := R[I]; R[I] := T

21、;???? //將當(dāng)前堆頂記錄和堆中最后一個(gè)記錄交換//     Sift(R, 1, I-1) ????????????????//將R[1..I-1]重成堆//    end  End; ????????????????//HeapSort// ? 六、幾種排序算法的比較和選擇 1. 選取排序方法需要考慮的因素: (1) 待排序的元素?cái)?shù)目n; (2) 元素本身信息量的大??; (3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況; (4) 語言工具的條件,輔助空間的大小等。 2. 小結(jié): (1) 若n較小(n <= 50),則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記

22、錄移動(dòng)操作較直接選擇排序多,因而當(dāng)記錄本身信息量較大時(shí),用直接選擇排序較好。 (2) 若文件的初始狀態(tài)已按關(guān)鍵字基本有序,則選用直接插入或冒泡排序?yàn)橐恕? (3) 若n較大,則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法:快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內(nèi)部排序法中被認(rèn)為是最好的方法。 (4) 在基于比較排序方法中,每次比較兩個(gè)關(guān)鍵字的大小之后,僅僅出現(xiàn)兩種可能的轉(zhuǎn)移,因此可以用一棵二叉樹來描述比較判定過程,由此可以證明:當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí),任何借助于"比較"的排序算法,至少需要O(nlog2n)的時(shí)間。 (5) 當(dāng)記錄本身信息量較大時(shí),為避免耗費(fèi)大量時(shí)間移動(dòng)記錄,可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!