數(shù)據(jù)結(jié)構(gòu)之排序算法講義ppt課件.ppt

《數(shù)據(jù)結(jié)構(gòu)之排序算法講義ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

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

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

5、入一個關(guān)鍵字。舉例，圖8-2-22021/7/30102、折半插入排序折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。例：有6個記錄，前5個已排序的基礎(chǔ)上，對第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*/}/*折半插入排序*/折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動次數(shù)不變，其時間復(fù)雜度與直接插入排序相同。/*折半后的位

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