數(shù)據(jù)結(jié)構(gòu)排序ppt課件(參考版)
2024-11-06 22:18本頁(yè)面
【正文】 謝謝！ 。 總結(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)限制 )。選擇排序如果通過移動(dòng)元素的方式實(shí)現(xiàn)元素的插入或以鏈表做存儲(chǔ)結(jié)構(gòu)，它也是穩(wěn)定的排序方法 )； ? O(nlogn)類高級(jí)排序除 歸并排序、二叉排序樹外都不穩(wěn)定。 ? 經(jīng)典算法： 快速排序 ，歸并操作，直接插入排序中使用哨兵，冒泡排序中使用交換標(biāo)志 ? n較大時(shí)平均時(shí)間性能：快速排序 歸并排序 堆排序 希爾排序 各種 O(n2)類簡(jiǎn)單排序； ? n較小或基本有序時(shí)：直接插入排序最快 ? 通過 “ 關(guān)鍵字比較 ” 實(shí)現(xiàn)排序其性能極限為O(nlogn)級(jí)。 } ? 例子程序參見： (為方便閱讀，此例完全沒考慮空間問題，純粹參考用 ) 歸并排序 ? 提問：對(duì)整數(shù)序列 32154135進(jìn)行從小到大的排序，經(jīng)過一趟歸并排序之后的序列怎樣？ ? 答： 23151435 ? 性能分析： 時(shí)間復(fù)雜度： O(nlogn) 空間復(fù)雜度： O(n) 穩(wěn)定性：穩(wěn)定。 //歸并有序表 TR2[s～ m]和 TR2[m+1～ t] } } 歸并排序 void MergeSort(SqList amp。 //歸并排序 SR[s～ m]為 TR2[s～ m] MSort(SR, TR2, mid+1, t)。 //遞歸調(diào)用終止條件 else { mid=(s+t)/2。 //思路類似于 P26程序，不同之處是該算法是歸并一個(gè)表的兩個(gè)部分，而不是歸并兩個(gè)表 } 歸并排序 void MSort(ElemType SR[], ElemType amp。 void Merge(ElemType SR[], ElemType amp。由于歸并排序需要的輔助空間較多，內(nèi)部排序很少使用歸并排序方法。增量為 2時(shí)結(jié)果為： 12354；增量為 1時(shí)結(jié)果為：12345(雖只 1趟，但蛻化為插入排序 ) ★ 五、歸并排序 ? 將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表的方法叫 歸并 。 ? 算法參見課本 P272。希爾排序 不穩(wěn)定 。故可以把記錄大跨度方式分組，組內(nèi)排序之后，整個(gè)序列便基本有序，然后縮小跨度繼續(xù)分組、排序。 穩(wěn)定性：穩(wěn)定。 //把元素 [i]插入到正確位置 } } ? 例子程序參見： 直接插入排序 ? 提問：對(duì)整數(shù)序列 32154進(jìn)行從小到大的排序，經(jīng)過一趟直接插入排序之后的序列怎樣？ ? 答： 23154 ? 性能分析： 比較操作：順序查找 O(n2)；移動(dòng)操作：順序移動(dòng) O(n2)，時(shí)間復(fù)雜度： O(n2)。 //把大于 [i]的記錄 [j]后移。 [0].key [j].key。 //復(fù)制 哨兵 ，暫存元素 [i] [i]=[i1]。 ++i) //每一趟把元素 [i]插入到有序子表中。L) { for(i=2。 else break。 j) //j：可能需要移動(dòng)的元素的位序。 i從 2開始 for(j=i1。 ++i) //i：待插元素的位序。L) { for(i=2。 //重新調(diào)整除尾元素外的剩余元素為堆 } } ? 堆排序只需 1個(gè)記錄大小的輔助空間。 i) { [1] [i]。 //初建堆 for(i=。 i0。 //把首元素放到目標(biāo)位置，堆調(diào)整結(jié)束 } 47563 5 6sj j + 1rc堆排序 void HeapSort(HeapType amp。 s=j。 //比較哪個(gè)孩子更 大 if( = [j].key) break。amp。 j=m。H, int s, int m) { //記錄 H.[s～ m]中 除首元素外均滿足堆定義 ，該算法將把該記錄調(diào)整為堆 rc=[s]。 堆排序 ? 問題 1的解決方法 (基于堆調(diào)整完成初建堆 )： 堆排序 ? 算法 (注 :要使 排序結(jié)果從小到大 ，要建立 大頂堆 )： typedef SqList HeapType。 提問：序列 123456是堆嗎？ 堆排序 ? 利用堆可以搜尋最小元素，進(jìn)而可用來排序。 答：是，小頂堆 堆排序 ? 堆 ： n個(gè)元素的序列 {k1,k2,...,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為 堆 (小頂堆 )： ki=k2i且 ki=k2i+1 (i=1,2,...,n/2)。 注意該方法與通過構(gòu)造二叉排序樹來排序不同 (二叉排序樹的非終端結(jié)點(diǎn)存儲(chǔ)有真正的記錄 ) 堆排序 ? ★ 引言：樹形選擇排序需要構(gòu)建一個(gè)完全二叉樹 (不是滿二叉樹，為什么？ )，非終端結(jié)點(diǎn)并不存儲(chǔ)元素，輔助空間多。如果把兩兩比較作為一種數(shù)據(jù)間的關(guān)系，該操作可以用下圖形象表示： 樹形選擇排序 ? 樹形選擇排序 (錦標(biāo)賽排序 )：首先對(duì) n個(gè)記錄的關(guān)鍵字進(jìn)行 兩兩 比較，然后在其中一半較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。 ? 例如： 49， 38， 65， 97， 76， 13， 27， 49*，第一趟中存在的比較： 49－ 38， 38－ 65， 38－ 97， 38－ 76， 38－ 13， 13－ 27， 13－ 49*。但找到最小元素后若將其插入到目標(biāo)位置，則算法是穩(wěn)定的！ ? 32154進(jìn)行從小到大的排序，經(jīng)過一趟簡(jiǎn)單選擇排序之后的序列怎樣？ ? 答： 12354，如果采用順序移動(dòng)策略，則為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1