《數據結構排序》課件.ppt

1、1,第10章 排序,陳守孔 孟佳娜 陳卓,2020/9/8,2,本章目錄,10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 折半插入排序 *10.2.3 二路插入排序 *10.2.4 表插入排序 10.2.5 希爾排序 10.3 交換排序 10.3.1 起泡排序 10.3.2 快速排序 10.4 選擇排序 10.4.1 直接選擇排序 10.4.2 樹形選擇排序 10.4.3 堆排序 10.5 歸并排序 10.6 分配排序 10.7 內部排序方法的比較 10.8 外部排序 10.8.1 文件管理 10.8.2 外部排序 10.8.3 多路歸并排序 10.8.4 置換選

2、擇排序 *10.8.5 最佳歸并樹 *10.8.6 磁帶排序,2020/9/8,3,主要內容,知識點 1、排序的定義，排序可以看作是線性表的一種操作 2、排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。 3、插入排序（直接插入、對分插入、二路插入、表插入、希爾插入排序）。 4、交換排序（冒泡排序、快速排序）。 5、選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。 6、歸并排序、基數排序。 7、外部排序 重點難點 1、各種排序所基于的基本思想。 2、排序性能的分析，是否是穩(wěn)定排序。 3、折半插入、希爾排序。 4、快速排序。 5、堆排序。 6、敗者樹、置換選擇排序、最佳歸并樹。 7、對每種排序方法的學習，

3、能舉一反三。,2020/9/8,4,基本概念,排序： 假設含n個記錄的序列為R1, R2, ,Rn ， 其相應的關鍵字序列為 K1, K2, ,Kn ， 這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系Ks1Ks2Ksn，按此固有關系將n個記錄的序列重新排列為 Rs1, Rs2, ,Rsn 的操作稱作排序。,2020/9/8,5,基本概念,穩(wěn)定排序 ：若Ki為關鍵字，Ki =Kj（ij），且在排序前的序列中Ri領先于Rj。經過排序后，Ri與Rj的相對次序保持不變（即Ri仍領先于Rj），則稱這種排序方法是穩(wěn)定的，否則稱之為不穩(wěn)定的。 內部排序 ：若整個排序過程不需要訪問外存便能完成

4、，則稱此類排序問題為內部排序 外部排序：若參加排序的記錄數量很大，整個序列的排序過程不可能一次在內存中完成，則稱此類排序問題為外部排序,2020/9/8,6,排序的類型定義,#define n 待排序記錄的個數 typedef struct int key; AnyType other; 記錄其它數據域 RecType; RecType Rn+1;,2020/9/8,7,基本思想：假定第一個記錄有序，從第2個記錄開始，將待排序的記錄插入到有序序列中，使有序序列逐漸擴大，直至所有記錄都進入有序序列中。,插入排序,插入排序種類： 直接插入排序 折半插入排序 二路插入排序 表插入排序 希爾排序,20

5、20/9/8,8,直接插入排序,基本思想：將記錄Ri(2=i=n)插入到有序子序列R1.i-1中，使記錄的有序序列從R1.i-1變?yōu)镽1.i,2020/9/8,9,示例,初始關鍵字序列： 51 33 62 96 87 17 28 51 i=2(33) 33 51 62 96 87 17 28 51 i=3(62) 33 51 62 96 87 17 28 51 i=4(96) 33 51 62 96 87 17 28 51 i=5(87) 33 51 62 87 96 17 28 51 i=6(17) 17 33 51 62 87 96 28 51 i=7(28) 17 28 33 51 62

6、 87 96 51 i=8(51) 17 28 33 51 51 62 87 96,2020/9/8,10,一趟直接插入排序算法,void StrOnePass(RecType R，int i) 已知R1.i-1中的記錄按關鍵字非遞減有序排列，本算法 插入Ri,使R1.i中的記錄按關鍵字非遞減有序排列 R0=Ri; j=i-1; 將待排序記錄放進監(jiān)視哨 x=R0.key; 從后向前查找插入位置，將大于待排序記錄向后移動 while (x Rj.key) Rj+1=Rj; j-; 記錄后移 Rj+1=R0; 將待排序記錄放到合適位置 StrOnePass,2020/9/8,11,直接插入排序算法

7、,void StrInsSort1(RecType R，int n) 本算法對R1.n進行直接插入排序 for(i=2;i=n;i+) 假定第一個記錄有序 StrOnePass(R， i)； ,2020/9/8,12,直接插入排序性能分析,最好情況,2020/9/8,13,折半插入排序,void BinsSort(RecType R，int n) 對R1.n進行折半插入排序 for(i=2;ihigh; j-) Rj+1 = Rj; 記錄后移 Rhigh+1 = R0; 插入 for BinsSort,2020/9/8,14,折半插入排序性能分析,減少了比較次數，移動次數不變。 時間復雜度仍為

8、O（n2）。,2020/9/8,15,在對一組記錄 （54，38，96，23，15，72，60，45，83） 進行直接排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較多少次,2020/9/8,16,二路插入排序,對折半插入排序改進，減少了移動記錄的次數，但它要借助n個記錄的輔助空間，即其空間復雜度為O（n）。 基本思想：另設一數組d，將R1賦值給d1，并將d1看作排好序的中間記錄，從第二個記錄起依次將關鍵字小于d1的記錄插入d1之前的有序序列，將關鍵字大于d1的記錄插入d1之后的有序序列。 借助兩個變量first和final來指示排序過程中有序序列第一個記錄和最后一個記錄在d中的

9、位置。,2020/9/8,17,初始關鍵字序列： 51 33 62 96 87 17 28 51 i=1 51 firstfinal i=2 51 33 final first i=3 51 62 33 final first i=4 51 62 96 33 final first i=5 51 62 87 96 33 final first i=6 51 62 87 96 17 33 final first i=7 51 62 87 96 17 28 33 final first i=8 51 51 62 87 96 17 28 33 final first,2020/9/8,18,二路插入

10、排序算法,void BiInsertSort(RecType R，int n) 二路插入排序的算法 int dn+1; 輔助存儲 d1= R1;first=1;final=1; for(i=2;i=d1.key) 插入后部 low=1;high=final; while (low=high+1;j-) dj+1 = dj; 移動元素 dhigh+1=Ri; final+; 插入有序位置 ,2020/9/8,19,else if(first=1) 插入前部 first=n; dn=Ri; else low=first;high=n; while (low=high) m=(low+high)/2

11、; if(Ri.key dm.key) high=m-1; else low=m+1; while for (j=first;j=high;j+) dj-1 = dj; 移動元素 dhigh=Ri; first-; if if /for ,2020/9/8,20,表插入排序,靜態(tài)鏈表 #define n 待排序記錄的個數 typedef struct int key; AnyType other; 記錄其他數據域 int next; STListType; STListType SLn+1;,2020/9/8,21,表插入排序算法,void ListInsSort(STListType SL,

12、int n) 對記錄序列SL1.n作表插入排序。 SL0.key=MAXINT ; SL0.next=1; SL1.next=0; for(i=2; i=n; i+ ) 查找插入位置 j=0; for(k=SL0.next; SLk.key=SLi.key; ) j=k, k=SLk.next; SLj.next=i; SLi.next=k; 結點i插入在結點j和結點k之間 for ListInsSort,2020/9/8,22,表物理排序,void Arrange(STListType SL， int n) 調整靜態(tài)鏈表SL中各結點的指針值，使記錄按關鍵字有序排列 p=SL0.next; p

13、指示第一個記錄的當前位置 for(i=1; in; i+ ) SL1.i-1 記錄已按關鍵字有序，第i個記錄的當前位置應不小于i while(pi) p= SLp.next; 找到第i個記錄，并用p指示其在SL中當前位置 q=SLp.next; q指示尚未調整的表尾 if(p!=i) SLpSLi;交換記錄，使第i個記錄到位 SLi.next=p; 指向被移走的記錄，使得以后可由while循環(huán)找回 if p=q; p指示尚未調整的表尾，為找第i+1個記錄作準備 for Arrange,2020/9/8,23,希爾(shell 1959)排序,基本思想：從“減小n”和“基本有序”兩方面改進。 將

14、待排序的記錄劃分成幾組，從而減少參與直接插入排序的數據量，當經過幾次分組排序后，記錄的排列已經基本有序，這個時候再對所有的記錄實施直接插入排序。,2020/9/8,24,希爾排序示例,二趟排序結果： 17 10 51 33 28 51 52 62 96 87 三趟排序結果： 10 17 28 33 51 51 52 62 87 96,初始關鍵字序列： 51 33 62 96 87 17 28 51 52 10,一趟排序結果： 17 28 51 52 10 51 33 62 96 87,2020/9/8,25,希爾排序算法,void ShellSort(RecType R，int n) 以步長d

15、i/2分組的希爾排序，第一個步長取n/2，最后一個取1 for(d=n/2;d=1;d=d/2) for(i=1+d;i0第i個元素插入到合適位置 for for ShellSort,2020/9/8,26,希爾排序示例,請給出對一組記錄 （54,38,96,23,15,90,72,60,45,83） 進行希爾排序（增量序列為5，3，1）時的排序過程。,2020/9/8,27,交換排序,主要思路：在排序過程中，通過對待排序記錄序列中元素間關鍵字的比較，發(fā)現(xiàn)次序相反的，即將元素位置交換來達到排序目的。,交換排序種類： 起泡排序 快速排序,2020/9/8,28,起泡排序,基本思想：對所有相鄰記錄

16、的關鍵字值進行比較，如果是逆序（ajaj+1），則將其交換，最終達到有序化,2020/9/8,29,起泡排序示例,初始關鍵字序列： 51 33 62 96 87 17 28 51 第一趟排序結果： 33 51 62 87 17 28 51 96 第二趟排序結果： 33 51 62 17 28 51 87 96 第三趟排序結果： 33 51 17 28 51 62 87 96 第四趟排序結果： 33 17 28 51 51 62 87 96 第五趟排序結果： 17 28 33 51 51 62 87 96 第六趟排序結果： 17 28 33 51 51 62 87 96,2020/9/8,30,

17、void BubbleSort(RecType R，int n) 起泡排序 i = n; i 指示無序序列中最后一個記錄的位置 while(i1) lastExchange=1; 記最后一次交換發(fā)生的位置 for(j=1;jRj+1.key） temp=Rj；Rj=Rj+1；Rj+1=temp； 逆序時交換 lastExchange=j; if i=lastExchange; while ,起泡排序算法,2020/9/8,31,一組關鍵字（19,01,26,92,87,11,43,87,21），進行冒泡排序，試列出每一趟排序后的關鍵字序列,2020/9/8,32,快速排序,基本思想：從待排序記錄序列中任選取一個記錄（通常可選第一個記錄）的關鍵字作為樞軸（或支點），凡其關鍵字小于樞軸的記錄均移動至該記錄之前，而關鍵字大于樞軸的記錄均移動至該記錄之后。一趟快速排序后就將排序序列分成兩