數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁(yè)
2024-11-03 22:18本頁(yè)面
【正文】 ? 算法參見(jiàn)課本 P272。 希爾排序 ? 提問(wèn)：對(duì)整數(shù)序列 32154進(jìn)行從小到大的排序，經(jīng)過(guò)一趟希爾排序 (增量為 3)之后的序列怎樣？ ? 答： 32154(原封不動(dòng) )。增量為 2時(shí)結(jié)果為： 12354；增量為 1時(shí)結(jié)果為：12345(雖只 1趟，但蛻化為插入排序 ) ★ 五、歸并排序 ? 將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表的方法叫 歸并 。 ? 假設(shè)初始序列含有 n個(gè)記錄，則可看成是 n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為 1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為 2或 1的有序子序列；再兩兩歸并，如此重復(fù)。由于歸并排序需要的輔助空間較多，內(nèi)部排序很少使用歸并排序方法。 趟次 49 38 65 97 76 13 27 49*1 38 49 65 97 13 76 27 49*2 38 49 65 97 13 27 49*763 13 27 38 49 49*65 76 97歸并排序 歸并排序的實(shí)現(xiàn)：注意是先等分，再等分，直到表長(zhǎng)為1以后才開(kāi)始?xì)w并，且是對(duì)相鄰子表進(jìn)行歸并。 void Merge(ElemType SR[], ElemType amp。TR[], int i, int m, int n) { //歸并有序表 SR[i～ m]和 SR[m+1～ n]為 TR[i～ n]。 //思路類似于 P26程序，不同之處是該算法是歸并一個(gè)表的兩個(gè)部分，而不是歸并兩個(gè)表 } 歸并排序 void MSort(ElemType SR[], ElemType amp。TR1[], int s, int t) { if (s==t) TR1[s]=SR[s]。 //遞歸調(diào)用終止條件 else { mid=(s+t)/2。 //將 SR[s～ t]平分為 SR[s～ m]和 SR[m+1～ t]兩部分 MSort(SR, TR2, s, mid)。 //歸并排序 SR[s～ m]為 TR2[s～ m] MSort(SR, TR2, mid+1, t)。 //歸并排序 SR[m+1～ t]為 TR2[m+1～ t] merge(TR2, TR1, s, mid, t)。 //歸并有序表 TR2[s～ m]和 TR2[m+1～ t] } } 歸并排序 void MergeSort(SqList amp。L) { MSort(, , 1, )。 } ? 例子程序參見(jiàn)： (為方便閱讀，此例完全沒(méi)考慮空間問(wèn)題，純粹參考用 ) 歸并排序 ? 提問(wèn)：對(duì)整數(shù)序列 32154135進(jìn)行從小到大的排序，經(jīng)過(guò)一趟歸并排序之后的序列怎樣？ ? 答： 23151435 ? 性能分析： 時(shí)間復(fù)雜度： O(nlogn) 空間復(fù)雜度： O(n) 穩(wěn)定性：穩(wěn)定。 ? 注意：歸并排序常用于外部排序，很少用于內(nèi)部排序 六、 基數(shù)排序 ? 基數(shù)排序：借助多關(guān)鍵字的排序的思想對(duì)單關(guān)鍵字進(jìn)行排序 ★ 七、總結(jié) 最好時(shí)間性能平均時(shí)間性能最壞時(shí)間性能平均輔助空間穩(wěn)定性O(shè) ( n lo g n ) O ( n lo g n ) O ( n lo g n ) O ( l o g n ) 穩(wěn)定冒泡排序 O ( n ) O ( n2) O ( n2) O ( 1 ) 穩(wěn)定快速排序 O ( n lo g n ) O ( n lo g n ) O ( n2) O ( l o g n ) 不穩(wěn)定簡(jiǎn)單選擇排序 O ( n2) O ( n2) O ( n2) O ( 1 )不穩(wěn)定/ 穩(wěn)定 *堆排序 O ( n lo g2n) O ( n lo g2n) O ( n lo g n ) O ( 1 ) 不穩(wěn)定插入 直接插入排序 O ( n ) O ( n2) O ( n2) O ( 1 ) 穩(wěn)定排序 希爾排序 約 O ( n1 . 3) O ( 1 ) 不穩(wěn)定O ( n lo g n ) O ( n lo g n ) O ( n lo g n ) O ( n ) 穩(wěn)定( 基于鏈隊(duì) ) O ( m n ) O ( m n ) O ( m n ) O ( n ) 穩(wěn)定( 基于順序隊(duì)列 ) O ( m n ) O ( m n ) O ( m n ) O ( m n ) 穩(wěn)定歸并排序基數(shù)排序排序方法平衡的二叉排序樹(shù)選擇排序交換排序總結(jié) ? 記憶方法： 冒炮 (泡 )躲飛 機(jī) (基 )，把 樹(shù) 插入 堆 ，快速 做 選擇 ， 希爾 凱旋 歸 。 ? 經(jīng)典算法： 快速排序 ，歸并操作，直接插入排序中使用哨兵，冒泡排序中使用交換標(biāo)志 ? n較大時(shí)平均時(shí)間性能：快速排序 歸并排序 堆排序 希爾排序 各種 O(n2)類簡(jiǎn)單排序； ? n較小或基本有序時(shí)：直接插入排序最快 ? 通過(guò) “ 關(guān)鍵字比較 ” 實(shí)現(xiàn)排序其性能極限為O(nlogn)級(jí)。 總結(jié) ? O(n2)類簡(jiǎn)單排序除 選擇排序 外皆穩(wěn)定 (注意該結(jié)論也是有爭(zhēng)議的，見(jiàn) P289。選擇排序如果通過(guò)移動(dòng)元素的方式實(shí)現(xiàn)元素的插入或以鏈表做存儲(chǔ)結(jié)構(gòu)，它也是穩(wěn)定的排序方法 )； ? O(nlogn)類高級(jí)排序除 歸并排序、二叉排序樹(shù)外都不穩(wěn)定。不過(guò)穩(wěn)定性不重要。 總結(jié) ? O(n2)類簡(jiǎn)單排序都含有兩個(gè)循環(huán)，第一個(gè)循環(huán)的范圍是 [1～ length1]或 [2～ length]，第 2個(gè)循環(huán)的范圍是 [1～ i1]或 [2～ i]或 [i+1～length]或 [i～ length1]，其 最大范圍 也是 [1～length1]或 [2～ length]，并且 一般 兩個(gè)循環(huán)的循環(huán)方向相反 (簡(jiǎn)單選擇排序例外 ，循環(huán)方向不受此特點(diǎn)限制 )。 ? 基于鏈?zhǔn)浇Y(jié)構(gòu)只需要修改指針域 (或游標(biāo) )，不必移動(dòng)記錄，可提高性能，但是有些算法 (如歸并排序、堆排序 )無(wú)法基于鏈表實(shí)現(xiàn)。 謝謝！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1