數(shù)據(jù)結(jié)構(gòu)排序ppt課件-wenkub.com
2024-10-31 22:18 本頁面
【正文】 ? 基于鏈式結(jié)構(gòu)只需要修改指針域 (或游標(biāo) )，不必移動記錄，可提高性能，但是有些算法 (如歸并排序、堆排序 )無法基于鏈表實現(xiàn)。 總結(jié) ? O(n2)類簡單排序除 選擇排序 外皆穩(wěn)定 (注意該結(jié)論也是有爭議的，見 P289。L) { MSort(, , 1, )。 //將 SR[s～ t]平分為 SR[s～ m]和 SR[m+1～ t]兩部分 MSort(SR, TR2, s, mid)。TR[], int i, int m, int n) { //歸并有序表 SR[i～ m]和 SR[m+1～ n]為 TR[i～ n]。 ? 假設(shè)初始序列含有 n個記錄，則可看成是 n個有序的子序列，每個子序列的長度為 1，然后兩兩歸并，得到n/2個長度為 2或 1的有序子序列；再兩兩歸并，如此重復(fù)。希爾排序的規(guī)律比較復(fù)雜，時間復(fù)雜度可以近似認為是，其高效的原因源于元素的跳躍式移動。 直接插入排序 ? 改進方法： 折半插入排序 —— 折半查找，順序插入； 2路插入排序 —— 折半查找， 2路插入(以首元素為基準，將剩余元素分成兩個部分排序，可減少插入操作 )； 表插入排序 —— 基于鏈表順序查找，修改指針代替移動記錄 希爾排序 ? (縮小增量排序 ) 直接插入排序在 n很小和序列基本有序時都很高效。 [j+1]=[0]。 //把大于 [i]的 記錄 [i1]后移 for(j=i2。 i=。 注意前、后兩循環(huán)語句走向相反 if([j+1].key [j].key) [j+1] [j]。每一趟把元素 [i] //插入到有序子表 [i1～ 1]中。 堆排序 ? 提問： ? 12345組成的小頂堆，其首元素輸出后，一趟堆調(diào)整的結(jié)果如何？ ? 答： 24351 ? 32154初建堆的結(jié)果如何？ ? 答：小頂堆： 12354；大頂堆： 54123 ? 堆排序性能分析： 時間復(fù)雜度： O(nlogn) 空間復(fù)雜度： O(1) 穩(wěn)定性：不穩(wěn)定 四、插入排序 ? ★ 直接插入排序 每一趟將一個新記錄 插入到 已排好序的 有序表中，從而得到一個新的、記錄數(shù)增 1的有序表 趟次 49 38 65 97 76 13 27 49*49 38 65 97 76 13 27 49*1 38 49 65 97 76 13 27 49*2 38 49 65 97 76 13 27 49*3 38 49 65 97 76 13 27 49*4 38 49 65 76 97 13 27 49*5 13 38 49 65 76 97 27 49*6 13 27 38 49 65 76 97 49*7 13 27 38 49 49*65 76 97直接插入排序 ? 算法 1： void InsertSort(SqList amp。 i1。H) { for(i=。 //比較 “ 堆 ” 頂元素與較大的孩子 [s] = [j]。 j*=2) //從 “ 孩子 ” 結(jié)點開始進行調(diào)整 { //j號元素是 s號元素的孩子 if(jm amp。 void HeapAdjust(HeapType amp。 (或者說滿足 ki=k[i/2], i=2,3,...,n) ? 理解：它對應(yīng)的二叉樹中各結(jié)點都小于兩個孩子結(jié)點(故不是二叉排序樹 )。利用樹形結(jié)構(gòu)很容易理解和實現(xiàn)。 問題：如何提高選擇的速度以提高性能？ 樹形選擇排序 ? ? 引言：如何減少簡單選擇排序的比較次數(shù)：第二趟找最小的元素時利用前一趟的比較結(jié)果。 i++) { j=SelectMinKey(L, i)。 if(min!=i) [min] [i]。 { //每趟從 [i～ length]中找出最小的元素，與第 i個元素交換 min=i。 三、選擇排序 ? ★ 每一趟從第 i到第 n個元素中 選取關(guān)鍵字最小的記錄將其放到第 i個位置 (如最小記錄與第 i個記錄交換 ) 趟次 49 38 65 97 76 13 27 49*1 13 38 65 97 76 49 27 49*2 13 27 65 97 76 49 38 49*3 13 27 38 97 76 49 65 49*4 13 27 38 49 76 97 65 49*5 13 27 38 49 49*97 65 766 13 27 38 49 49*65 97 767 13 27 38 49 49*65 76 97簡單選擇排序 ? 算法 1： void Select_Sort(SqList amp。 //對樞軸低端子表遞歸排序 QSort(L, pivot_location + 1, high)。 } 或為 if(lowhigh) [low++] = [high]。 [low].key = pivot_key) ++low。 //高端比樞軸大的記錄位置保持不變 [low] = [high]。 //暫存樞軸 (首元素 )。L, int low, int high) //以順序表 [low～ high]的首元素為樞軸 ,將關(guān)鍵字比它小的記錄置于其左側(cè) ,大的置于其右側(cè) ,并返回樞軸最終位置。如圖： 趟次 49 38 65 97 76 13 27 49 *1 38 13 27 49 65 97 76 49 *趟次 49 38 65 97 76 13 2749*說明lo w h i g h 期望以某元素 ( 如首元素 ) 為基準進行劃分49 38 65 97 76 13 2749*期望 lo w 所指元素小于 49, 否則放到 h i g h 側(cè)lo w
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1