資源描述：
《《數(shù)據(jù)結(jié)構(gòu)排序》PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容10.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序第10章內(nèi)部排序10.1概述1.什么是排序？將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序——便于查找！10.1概述3.排序算法的好壞如何衡量？時(shí)間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復(fù)雜度是O(1)，則稱排序方法是就地排序，否則是非就地排序。穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等，
2、但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。4.什么叫內(nèi)部排序？什么叫外部排序？——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；內(nèi)部排序基本操作有兩種：◆比較兩個(gè)關(guān)鍵字的大小；(比不可少的操作)◆存儲(chǔ)位置的移動(dòng)?！舸判蛴涗浺徊糠衷趦?nèi)存，一部分在外存，則稱為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？處理方式：①順序排序——數(shù)據(jù)間的邏輯順序關(guān)系通過(guò)其物理存儲(chǔ)位置的相鄰來(lái)體現(xiàn)，排序時(shí)直接移動(dòng)記錄；適合數(shù)據(jù)較少的情況?、阪湵?/p>
3、排序——數(shù)據(jù)間的邏輯順序關(guān)系通過(guò)結(jié)點(diǎn)中的指針體現(xiàn)，排序時(shí)只修改指針，不移動(dòng)數(shù)據(jù)；③地址排序——數(shù)據(jù)存儲(chǔ)在一段連續(xù)地址的空間，構(gòu)造一個(gè)輔助表保持各數(shù)據(jù)的存放地址（指針），排序時(shí)先修改輔助表中的地址，最后再移動(dòng)記錄。②③適合數(shù)據(jù)較多的情況!注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)6.順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類型如何表示？Typedefstruct{//定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)KeyTypekey;//關(guān)鍵字InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RecordType;Typedefstruct{
4、//定義順序表的結(jié)構(gòu)RecordTyper[MAXSIZE+1];//存儲(chǔ)順序表的向量//r[0]一般作哨兵或緩沖區(qū)intlength;//順序表的長(zhǎng)度}SqList;#defineMAXSIZE20//設(shè)記錄不超過(guò)20個(gè)typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）7.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點(diǎn)是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長(zhǎng)度)——按排序算法的時(shí)間復(fù)雜度不同，可分為3類：簡(jiǎn)單的排序算法：時(shí)間效率低，O(n2)先進(jìn)的排序算法:時(shí)間效
5、率高，O(nlog2n)基數(shù)排序算法：時(shí)間效率高，O(d×n)10.2插入排序插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：1)直接插入排序2)折半插入排序3)2路插入排序4)希爾排序每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請(qǐng)寫出直接插入排序的中間過(guò)程序列?！?3】,6,3,31,9,27,5,11【6,13】,3
6、,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后順移。最簡(jiǎn)單的排序法！例2：關(guān)鍵字序列T=（21，25，49，25*，16，08）， 請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過(guò)程。*表示后一個(gè)25i=121254925*16080123456暫存21
7、i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組V[7]中，將V[0]作為緩沖或暫存單元（Temp）。則程序執(zhí)行過(guò)程為：21254925*21初態(tài)：164925*25211608完成!時(shí)間效率：O(n2)——因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動(dòng)元素的次數(shù)?？臻g效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：穩(wěn)定——因?yàn)?5*排序后仍然在25的后面。對(duì)應(yīng)程序參見教材P265。VoidIns
8、ertSort(SqList&L){//對(duì)順序表L做直接插入排序for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key))//“<“,需將L.r[i]插入有序子表{L.r[0]=L.r[i];//
