數據結構之排序算法講義ppt課件.ppt

《數據結構之排序算法講義ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、在此幻燈片插入公司的徽標從“插入”菜單選擇圖片找到徽標文件單擊“確定”重新設置徽標大小單擊徽標內任意位置?；諛送獠砍霈F的方框是“調整控點”使用這些重新設置對象大小如果在使用尺寸調整控點前按下shift鍵，則對象改變大小但維持原比例。DATA1065865姓名學號成績班級李紅976105995機97.6ABCDEFG數據結構注意帶以下內容：圖2-8-1圖2-8-2圖2-8-3圖2-8-4圖2-8-52021/7/302第二章?數據結構與算法(續(xù))2021/7/3032.8排序2.8.1概述1、排序的功能：將一個數據元素（或記錄）的任意序列，重新排成一個按關鍵字有序的序列。2、排序過程的組成步驟：

2、首先比較兩個關鍵字的大??；然后將記錄從一個位置移動到另一個位置。2021/7/304假設待排序的記錄存放在地址連續(xù)的一組存儲單元中，那么這種存儲方式下的數據類型可描述為：MAX01234………keyinfo#defineMAX20typedefstruct{intkey;floatotherinfo;}RedType;2021/7/305排序方法插入排序選擇排序交換排序歸并排序直接插入排序折半插入排序簡單選擇排序堆排序起泡排序快速排序2021/7/3062.8.2插入排序直接插入、折半插入1、直接插入排序:基本思想：從數組的第2號元素開始，順序從數組中取出元素，并將該元素插入到其左端已排好序的

3、數組的適當位置上。舉例：圖8-2-12021/7/3072.8.2插入排序直接插入、折半插入該算法適合于n較小的情況，時間復雜度為O(n2).1、直接插入排序:基本思想：從數組的第2號元素開始，順序從數組中取出元素，并將該元素插入到其左端已排好序的數組的適當位置上待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]直接插入排序示例對于有n個數據元素的待排序列，插入操作要進行n-1次2021/7/308voi

4、dinsertSort(RedTypeL[],intn){inti,j;for(i=2;i<=n;i++)if(L[i].key

5、入一個關鍵字。舉例，圖8-2-22021/7/30102、折半插入排序折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。例：有6個記錄，前5個已排序的基礎上，對第6個記錄排序。[1527365369]42?low?mid?high[1527365369]42?low?high?mid[1527365369]42?high?low[152736425369](high36)(42<53)2021/7/3011voidBinsertSort(RedTypeL[],intn){in

6、ti,low,high,mid;for(i=2;i<=n;++i){L[0]=L[i];/*r[0]作為監(jiān)視哨*/low=1;high=i-1;While(low<=high){mid=(low+high)/2;if(L[0].key=high+1;??j)L[j+1]=L[j];/*記錄后移*/L[high+1]=L[0];/*插入*/}/*for*/}/*折半插入排序*/折半插入排序減少了關鍵字的比較次數，但記錄的移動次數不變，其時間復雜度與直接插入排序相同。/*折半后的位

7、置*/2021/7/30121、簡單選擇排序思想：首先從1~n個元素中選出關鍵字最小的記錄交換到第一個位置上。然后再從第2個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。時間復雜度為O(n2)，適用于待排序元素較少的情況。2.8.3選擇排序簡單選擇排序、堆排序舉例：圖8-2-32021/7/30132.8.3選擇排序簡單選擇排序、堆排序。1、簡單選擇排序思想：首先從1~n個元素中選出關