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

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

1、第九章排序本章要求【教學(xué)目的】掌握內(nèi)排序方法的插入排序；選擇排序；交換排序；基數(shù)排序；歸并排序；排序的存儲方式：連續(xù)地址、靜態(tài)鏈表、索引；穩(wěn)定的和不穩(wěn)定的排序方法的判定方法，常見的穩(wěn)定的排序方法和的不穩(wěn)定的排序方法。了解外部排序的方法以及外部排序方法的特點。【教學(xué)重點】每種排序方法的算法及算法的性能分析【教學(xué)難點】排序方法的比較及穩(wěn)定性的確定第八章查找一、基本概念二、插入排序三、交換排序四、選擇排序五、歸并排序一、基本概念排序的目的排序是為了通過關(guān)鍵字高效的查找相關(guān)的記錄排序就是要調(diào)整原文件中的記錄順序，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其形式化定義描述如下：輸入：n個記錄r1，r2，…

2、，rn，其相應(yīng)的關(guān)鍵字分別為k1，k2，…，kn輸出：rl′，r2′，…，rn′，使得k1′≤k2′≤…≤kn′。(或k1′≥k2′≥…≥kn′)//有序升序或者降序一、基本概念排序的數(shù)據(jù)結(jié)構(gòu)待排序的記錄采用順序存儲，待排序記錄的定義為：#defineMAXSIZE100/*假定順序表的最大長度為100*/typedefintKeyType；/*假定關(guān)鍵字類型為整數(shù)類型*/typedefstruct{KeyTypekey；/*關(guān)鍵字項*/OtherTypeother；/*其他項*/}DataType；/*數(shù)據(jù)元素類型*/typedefstruct{DataTyper[MAXSIZE+1]；/*

3、r[0]閑置或充當(dāng)哨兵*/intlength；/*順序表長度*/}SqList；/*順序表類型*/一、基本概念排序的數(shù)據(jù)結(jié)構(gòu)排序的穩(wěn)定性：若存在關(guān)鍵字相同的多個記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；否則則稱這種排序方法是不穩(wěn)定的。排序的分類：按是否涉及數(shù)據(jù)的內(nèi)、外存交換分類：內(nèi)排序、外排序。內(nèi)部排序方法有：插入排序、選擇排序、交換排序、歸并排序排序的效率分析：時間代價和空間代價二、插入排序基本思想通過構(gòu)建有序序列，將待排序的數(shù)據(jù)，在已排好序的序列中從后向前掃描，找到其相應(yīng)位置并進行插入操作。直接插入排序二分法插入排序Shell排序二、插入排序直接插

4、入排序算法思想：將待插入子序列元素逐步插入到有序子序列中，設(shè)有一待排序序列S={r1，r2，r3，…，ri，…，rn},其中{r1，r2，…，ri}(1≤i≤n)是按照關(guān)鍵字{k1≤k2≤…≤ki}有序的子序列，序列{ri+1，…，rn}無序。從序列{ri+1，…，rn}的第一個元素ri+1開始取數(shù)據(jù)元素，每取一個元素就將其插入到前面的有序序列中，并使插入后的序列有序，直到所有元素插入完成，得到一個有序序列。二、插入排序直接插入排序算法：voidStraightInsertSort(SqList*S){/*對順序表s中的s->r[1..length]作直接插入排序*/for(i=2；i<=S-

5、>length；i++){S->r[0]=S->r[i]；/*復(fù)制為哨兵*/j=i-1;while(S->r[0].keyr[j].key){S->r[j+1]=S->r[j]；j--;}/*記錄后移*/S->r[j+1]=S->r[0]；/*插入到正確位置*/}}能不能改為<=?二、插入排序直接插入排序效率分析：空間效率：用了一個輔助單元r[0]，因此輔助空間為O(1)時間效率：最好情形：待排序序列中各數(shù)據(jù)元素在排序前已按關(guān)鍵字大小排好序，總的比較次數(shù)=n-1次,總的移動次數(shù)=n-1次,所以時間復(fù)雜度為O（n）最壞情形：待排序序列中各數(shù)據(jù)元素為逆序狀態(tài)時，直接插入排序是穩(wěn)定的排序算法

6、二、插入排序二分插入排序算法思想：在插入第i個關(guān)鍵碼時，前i－1個關(guān)鍵已經(jīng)有序，可以通過折半的方式找到插入點。但是，雖然可以更快地找到插入點，但意義不大？因為，找到插入點后還需要進行移動元素，并沒有改變移動元素的次數(shù)，因此其時間復(fù)雜度并沒有發(fā)生改變。二、插入排序Shell排序算法思想：先將待排序列分割為若干個子序列分別進行直接插入排序；待整個序列基本有序時，再對全體記錄進行一次直接插入排序。也稱縮小增量的直接插入排序。二、插入排序Shell排序算法：voidShellInsert(SqList*s，intgap)//步長為gap的插入排序{for(i=gap+1；i<=S->length；i+

7、+)if(S->r[i].keyr[i-gap].key){/*小于時，需將r[i]插入有序表*/S->r[0]=S->r[i]；/*為統(tǒng)一算法設(shè)置監(jiān)視哨*/for(j=i-gap；j>0&&S->r[0].keyr[j].key；j=j-gap)S->r[j+gap]=S->r[j]；/*記錄后移*/S->r[j+gap]=S->r[0]；/*插入到正確位置*/}/*if*/}/