秋霞电影网午夜鲁丝片无码,真人h视频免费观看视频,囯产av无码片毛片一级,免费夜色私人影院在线观看,亚洲美女综合香蕉片,亚洲aⅴ天堂av在线电影猫咪,日韩三级片网址入口

2022年高中信息技術 全國青少年奧林匹克聯賽教案 排序算法

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

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

9.9 積分

下載資源

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

資源描述:

《2022年高中信息技術 全國青少年奧林匹克聯賽教案 排序算法》由會員分享,可在線閱讀,更多相關《2022年高中信息技術 全國青少年奧林匹克聯賽教案 排序算法(8頁珍藏版)》請在裝配圖網上搜索。

1、2022年高中信息技術 全國青少年奧林匹克聯賽教案 排序算法 ? 一、插入排序(Insertion Sort) 1. 基本思想: ???? 每次將一個待排序的數據元素,插入到前面已經排好序的數列中的適當位置,使數列依然有序;直到待排序數據元素全部插入完為止。 2. 排序過程:  【示例】: [初始關鍵字] [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); //對R[1..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、一趟從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素,順序放在已排好序的數列的最后,直到全部待排序的數據元素排完。 2. 排序過程: 【示例】: ??初始關鍵字 [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] 最后排序結果 13 27 38 49 49 76 76 97 Procedure SelectSort(Var R : FileType); ?????//對R[1..N]進行直接選擇排序 // ??Begin ????for I := 1 To N - 1 Do ?????????????????//做N - 1趟選擇排序// ?????begin ??????K := I; ??????For J := I + 1 To N Do ???????????????//在當前無序區(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、:   兩兩比較待排序數據元素的大小,發(fā)現兩個數據元素的次序相反時即進行交換,直到沒有反序的數據元素為止。 2. 排序過程:   設想被排序的數組R[1..N]垂直豎立,將每個數據元素看作有重量的氣泡,根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組R,凡掃描到違反本原則的輕氣泡,就使其向上"漂浮",如此反復進行,直至最后任何兩個氣泡都是輕者在上,重者在下為止。 【示例】: 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; ???//置未排序的標志// ?????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、想:   在當前無序區(qū)R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X),用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū):R[1..I-1]和R[I+1..H],且左邊的無序子區(qū)中數據元素均小于等于基準元素,右邊的無序子區(qū)中數據元素均大于等于基準元素,而基準X則位于最終排序的位置上,即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),當R[1..I-1]和R[I+1..H]均非空時,分別對它們進行上述的劃分過程,直至所有無序子區(qū)中的數據元素均已排序為止。 2. 排序過程: 【示例】: 初始關鍵字 [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] (一次劃分過程) 初始關鍵字 [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 最后的排序結果 13 27 38 49 49 65 76 97 各趟排序之后的狀態(tài) Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer); //對無序區(qū)R[1,H]做劃分,I給以出本次劃分后已被定位的基準元素的位置 // Begin ??I := 1; J := H; X := R[I] ;?? //初始化,X為基準// ??Repeat ????While (R[J] >= X) And (I < J)

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

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

15、?If S < T Then ???//當R[S..T]為空或只有一個元素是無需排序// ????begin ??????Partion(R, S, T, I); ???//對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]看成是一顆完全二叉樹的順序存儲結構,利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。 2. 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆,當且僅當該序列滿足特性: ?????? Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2]) ???? 堆實質上是滿足如下性質的完全二叉樹:樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆,它對應的完全二叉樹如上圖所示。這種堆中根結點(稱為堆頂)的關鍵字最小,我們把它稱為小根堆。反之,若完全二叉樹中任一非葉子結點的關

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

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

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

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

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

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

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

相關資源

更多
正為您匹配相似的精品文檔
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網版權所有   聯系電話:18123376007

備案號:ICP2024067431-1 川公網安備51140202000466號


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