《數(shù)據(jù)結構之排序算法講義ppt課件.ppt》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構之排序算法講義ppt課件.ppt（33頁珍藏版）》請在匯文網(wǎng)上搜索。

1、,在此幻燈片插入公司的徽標從“插入”菜單選擇圖片找到徽標文件單擊“確定”重新設置徽標大小單擊徽標內(nèi)任意位置?；諛送獠砍霈F(xiàn)的方框是“調(diào)整控點”使用這些重新設置對象大小如果在使用尺寸調(diào)整控點前按下 shift 鍵，則對象改變大小但維持原比例。,DATA,10,65,865,姓名 學號 成績 班級 李紅 9761059 95 機97.6,數(shù)據(jù)結構,2022/2/18,2,注意帶以下內(nèi)容：圖2-8-1圖2-8-2圖2-8-3圖2-8-4圖2-8-5,2022/2/18,3,第二章數(shù)據(jù)結構與算法,(續(xù)),2022/2/18,4,2.8 排 序2.8.1 概 述,1、排序的功能：將一個數(shù)據(jù)元素（或記錄）的

2、任意序列，重新排成一個按關鍵字有序的序列。2、排序過程的組成步驟： 首先比較兩個關鍵字的大??； 然后將記錄從一個位置移動到另一個位置。,2022/2/18,5,假設待排序的記錄存放在地址連續(xù)的一組存儲單元中，那么這種存儲方式下的數(shù)據(jù)類型可描述為：,MAX,0,1,2,3,4,key,info,#define MAX 20 typedef struct int key; float otherinfo; RedType;,2022/2/18,6,排序方法,插入排序,選擇排序,交換排序,歸并排序,直接插入排序,折半插入排序,簡單選擇排序,堆排序,起泡排序,快速排序,2022/2/18,7,2.8.

3、2 插入排序 直接插入、折半插入,1、直接插入排序:基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當位置上。舉例：圖8-2-1,2022/2/18,8,2.8.2 插入排序 直接插入、折半插入,該算法適合于n 較小的情況，時間復雜度為O(n2).,1、直接插入排序:基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當位置上,待排元素序列：53 27 36 15 69 42第一次排序： 27 53 36 15 69 42第二次排序： 27 36 53 15 69 42第三次排序： 15 27 36 5

4、3 69 42第四次排序： 15 27 36 53 69 42第五次排序： 15 27 36 42 53 69 直接插入排序示例,對于有n個數(shù)據(jù)元素的待排序列，插入操作要進行n-1次,2022/2/18,9,void insertSort(RedType L ,int n) int i ,j; for(i=2; i=n; i+) if(Li.keyLi-1.key) L0=Li; /* 作為監(jiān)視哨*/ for( j=i-1; L0.keyLj.key; j ) Lj+1=Lj; /* 記錄后移*/ Lj+1=L0; /* 插入 */ ,插入算法如下：方法:Ki與Ki-1,K i-2,K1依次比

5、較,直到找到應插入的位置。,2022/2/18,10,2、折半插入排序 折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置 。待排序元素越多，改進效果越明顯。,折半插入排序的條件： 在有序序列中插入一個關鍵字。,舉例，圖8-2-2,2022/2/18,11,2、折半插入排序 折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。,(highlow ，查找結束，插入位置為low 或high+1 ),( 4236 ),( 4253 ),2022/2/18,12,void BinsertSort(RedType L ,

6、int n) int i,low,high,mid; for(i=2; i=high+1; j ) Lj+1=Lj; /* 記錄后移*/ Lhigh+1=L0; /* 插入*/ /* for*/ /*折半插入排序*/,折半插入排序減少了關鍵字的比較次數(shù)，但記錄的移動次數(shù)不變，其時間復雜度與直接插入排序相同。,/*折半后的位置*/,2022/2/18,13,1、簡單選擇排序思想：首先從1n個元素中選出關鍵字最小的記錄交換到第一個位置上。然后再從第2 個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。時間復雜度為O(n2)，適用于待排序元素較少的情況。,2.8.3 選擇排序 簡單選擇排序

7、、堆排序,舉例：圖8-2-3,2022/2/18,14,2.8.3 選擇排序 簡單選擇排序、堆排序。 1、簡單選擇排序思想：首先從1n個元素中選出關鍵字最小的記錄交換到第一個位置上。然后再從第2 個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。時間復雜度為O(n2)，適用于待排序元素較少的情況。,初態(tài),8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,2022/2/18,15,簡單選擇排序的算法如下：void SelectSort( RedType L ,int n) int i,j,k,t;

8、 for (i=1,i=n;+i） /*選擇第i小的元素，并交換到位*/ k=i； for(j=i+1;j=n;+j) if ( Lj.keyLk.key) k=j; /*Lk 中存放的是第I小的元素*/ if(k!=i) t=Li; /*交換*/ Li=Lk; Lk=t ； /*FOR*/ /* SelectSort*/,2022/2/18,16,2堆排序也是一種選擇排序。是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結點的關鍵字大于等于（或小于等于）子女的關鍵字的值。 (1) 堆的示例,(a):堆頂元素取最大值,(b):堆頂元素取最小值,(2) 實現(xiàn)堆排序需解決兩個問題

9、： （1） 如何由一個無序序列建成一個堆？ （2） 輸出堆頂元素后，如何將剩余元素調(diào)整成一個新的堆？,舉例：圖8-2-4,2022/2/18,17,(3) 輸出堆頂元素并調(diào)整建新堆的過程(篩選),把自堆頂至葉子的調(diào)整過程稱為“篩選。從一個無序序列建堆的過程就是一個反復”篩選“的過程。,2022/2/18,18,（4）由無序序列建初始堆的過程,(c): 49被篩選后的狀態(tài),(d): 56被篩選后的狀態(tài),(e): 被篩選之后建成堆,2022/2/18,19,E、篩選算法（調(diào)整建堆）typedef Sqlist HeapType; /堆采用順序表存儲表示void HeapAdjust( HeapTy

10、pe ,2022/2/18,20,typedef Sqlist HeapType; void HeapAdjust( HeapType ,2022/2/18,21,void HeapSort( HeapType /把H.r1.i-1重新調(diào)整為一個堆 ,F、堆排序算法,2022/2/18,22,A:,F、堆排序算法,2022/2/18,23,2022/2/18,24,2.8.4 交 換 排 序交換排序的特點在于交換。有冒泡和快速排序兩種。 1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較， 大則交換，關鍵字最大的記錄交換到

11、最后一個位置上；第二趟：對前n-1個記錄進行同樣的操作，關鍵字次大的記錄交換 到第n-1個位置上； 依次類推，則完成排序。正序：時間復雜度為O(n) 逆序：時間復雜度為O(n2) 適合于數(shù)據(jù)較少的情況。 排序n個記錄的文件最多需要n-1趟冒泡排序。,舉例：圖8-2-5,2022/2/18,25,第六趟排序后,第五趟排序后,第四趟排序后,第三趟排序后,第二趟排序后,第一趟排序后,初始關鍵字,思想：小的浮起，大的沉底。,2022/2/18,26,冒泡排序的C程序段：Void bubsort(RedType L ,int n) int i,x,j=1,k=1; while (j0); k=0; fo

12、r (i=1;i=n-j; i+) if (Li+1.keyLi.key) k+;x=Li;Li=Li+1;Li+1=x; j+; /*while*/ /*Bobsort*/,2022/2/18,27,2、快速排序 (對冒泡排序的改進）思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關鍵字均比另一部分小，再分別對這兩部分排序，以達到整個序列有序。關鍵字通常取第一個記錄的值為基準值。做法：附設兩個指針low和high ，初值分別指向第一個記錄和最后一個記錄，設關鍵字為 key ，首先從 high所指位置起向前搜索，找到第一個小于基準值的記錄與基準記錄交換，然后從low 所指位置起向后搜

13、索，找到第一個大于基準值的記錄與基準記錄交換，重復這兩步直至low=high為止。時間復雜度：O(log2n),舉例圖8-2-6,2022/2/18,28,快速排序過程示意圖：,有序序列 6 18 23 52 67,key,low,high,一次交換 18 52 6 67 23,low,high,二次交換 18 23 6 67 52,high,三次交換 18 6 23 67 52/ 完成一趟排序后分別進行快速排序,low,high,2022/2/18,29,2.8.5 歸并排序,初始序列 23 52 67 6 18 10一趟歸并后 23 52 6 67 10 18二趟歸并后 6 23 52 6

14、7 10 18三趟歸并后 6 10 18 23 52 67,歸并排序示例,功能：將兩個或兩個以上的有序表組成一個新的有序表。思想：把具有n個記錄的表看成是n個有序的子表，每個子表的長度為1，然后兩兩歸并，得到n/2個長度為2或為1的有序子表；再兩兩歸并，如此重復，直到得到一個長度為n的有序表為止。,2022/2/18,30,2.8.6 內(nèi)部排序方法的選擇各種排序方法各有優(yōu)缺點，故在不同情況下可作不同的選擇。通常需考慮的因素有：待排序的記錄個數(shù)；記錄本身的大??；記錄的鍵值分布情況等。 若待排序的記錄個數(shù)n較小時，可采用簡單排序方法。 若n 較大時，應采用快速排序或堆排序。 若待排序的記錄已基本有序，可采用起泡排序。,2022/2/18,31,作業(yè)：P77 第34題P78 第3544題,人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋?！蓖ㄟ^閱讀科技書籍，我們能豐富知識，培養(yǎng)邏輯思維能力；通過閱讀文學作品，我們能提高文學鑒賞水平，培養(yǎng)文學情趣；通過閱讀報刊，我們能增長見識，擴大自己的知識面。有許多書籍還能培養(yǎng)我們的道德情操，給我們巨大的精神力量，鼓舞我們前進。,