[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)(參考版)
2024-10-22 04:11本頁面
【正文】 。 2. 快速排序?yàn)?O (logn)，為遞歸程序執(zhí)行過程中棧所需的輔助空間。 空間性能 ： ? 指的是排序過程中所需的輔助空間大小。大多數(shù)情況下排序是按記錄的主關(guān)鍵字進(jìn)行的，則所有的排序方法是否穩(wěn)定無關(guān)緊要。然而，快速排序、堆排序和希爾排序等時(shí)間性能較好的排序都是不穩(wěn)定的。 （ 3）當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)，插入排序和起泡排序能達(dá)到 O (n)的時(shí)間復(fù)雜度； （ 4）選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。 （ 2）簡單排序以直接插入排序最簡單，當(dāng)下列中記錄 “ 基本有序 “ 或 n值較小時(shí)，是最佳的排序方法。 鏈表的歸并排序方法是一種穩(wěn)定的排序方法。 Merge(TR2,TR1, s, m, t)。 // 將 SR[s..t]平分為 SR[s..m]和 SR[m+1..t] MSort(SR, TR2, s, m)。 if( s == t ) TR1[s]=SR[s]。 } } void MSort(RedType SR[], RedType TR1[], int s, int t){ int m。 MERGEPASS(R1,R,length)。 while (lengthn) { MERGEPASS(R,R1,length)。j++) R1[j]=R[j]。 else for (j=i。 i=i+2*length。 i=0。 l++) TR[k+l]=SR[j+l]。 // 將剩余的 SR[i..m]復(fù)制到 TR if( j =n ) for( l=0。 l=mi。 else TR[k]=SR[j++]。 j=n。 i=m amp。 歸并排序過程 21 25 25* 25* 93 62 72 08 37 16 54 49 21 25 49 62 93 08 72 16 37 54 21 25 25* 49 08 62 72 93 16 37 54 08 08 21 16 25 21 25* 25 49 25* 62 37 72 49 93 54 16 37 54 62 72 93 len=1 len=2 len=4 len=8 len=16 歸并算法： // 將有序的 SR[i..m]和 SR[m+1..n]歸并為有序的 TR[i..n] 算法 void Merge( RedType SR[], RedType TR[], int i,int m,int n) { int j, k, l 。 歸并排序 (Merge Sort) ? 歸并排序是利用 “ 歸并 ” 技術(shù)來進(jìn)行排序 ， 所謂歸并是指將兩個(gè)有序的序列合并形成一個(gè)新的有序序列 。 ? 堆排序在最壞情況下的時(shí)間復(fù)雜度也是 O(nlog2n)，相對于快速排序來說 ， 這是堆排序的最大優(yōu)點(diǎn) 。在第一個(gè)建立初始堆的 for循環(huán)中對每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法HeapAdjust( )，因此該循環(huán)所用的計(jì)算時(shí)間為： ? 其中， i 是層序號， 2i1 是第 i 層的最大結(jié)點(diǎn)數(shù)，(ki)是第 i 層結(jié)點(diǎn)能夠移動(dòng)的最大距離 。 ? 若設(shè)堆中有 n 個(gè)結(jié)點(diǎn)，且 2k1 ? n ? 2k，則對應(yīng)的完全二叉樹有 k 層。 HeapAdjust( H, 1, i1 )。 [1] = [i]。 i1。 i) // 把 [1..]建成大頂堆 HeapAdjust(H,i,)。 for(i=。H){ RedType temp。這個(gè)算法即堆排序算法。 ? 再對調(diào) R[1]和 R[n1]，調(diào)用 HeapAdjust(H, 1, n2)，對前 n2個(gè)記錄重新調(diào)整， … 。 i ) HeapAdjust( H, i, ) 基于初始堆進(jìn)行堆排序 ? 大頂堆的第一個(gè)記錄 R[1]具有最大的關(guān)鍵字，將 R[1]與 R[n]對調(diào)，把具有最大關(guān)鍵字的記錄交換到最后，再對前面的 n1個(gè)記錄，使用堆的調(diào)整算法 HeapAdjust(H, 1, n1)，重新建立大頂堆。有了這個(gè)算法，則將初始的無序區(qū) R[1]到 R[n]建成一個(gè)大根堆，可用以下語句實(shí)現(xiàn) ： for ( i = n/2。 } [s] = rc。 // rc應(yīng)插入在位置 s上 [s] = [j]。 [j].key[j+1].key ) j++。 j*=2 ){ // 沿 key較大的孩子結(jié)點(diǎn)向下篩選 if( jm amp。 for( j=2*s。H, int s, int m){ RedType rc。 例子： 關(guān)鍵字序列為 42， 13， 91， 23， 24， 16， 05， 88， n=8，故從第四個(gè)結(jié)點(diǎn)開始調(diào)整 42 13 91 23 24 16 05 88 42 13 91 23 24 16 05 88 42 13 91 88 24 16 05 23 42 13 91 88 24 16 05 23 不調(diào)整 42 13 91 88 24 16 05 23 42 13 91 88 24 16 05 23 42 88 91 23 24 16 05 13 42 88 91 23 24 16 05 13 91 88 42 23 24 16 05 13 91 88 42 23 24 16 05 13 建成的堆 調(diào)整算法： typedef SqList HeapType。 在按此次序調(diào)整每個(gè)結(jié)點(diǎn)時(shí) ， 其左 、 右子樹均已是堆 。 ? 堆排序基本思想 ： 首先將初始待排序記錄序列 建堆 ， 則堆頂元素必為含最大關(guān)鍵字或最小關(guān)鍵字的記錄 ， 輸出該記錄 ， 然后將剩余記錄再 調(diào)整為堆 ， 如此反復(fù) ，直至排序結(jié)束 。 堆排序 (Heap Sort) 堆的概念： 堆是一個(gè)關(guān)鍵字序列 { k1, k2, … , kn },它具有如下特性： ki ≤k2i 或 ki ≥ k2i ki ≤ k2i+1 ki ≥ k2i+1 ( i = 1,2,… , └n/2┘) 堆的特性在完全二叉樹中解釋為：完全二叉樹中任一結(jié)點(diǎn)的關(guān)鍵字都小于等于（或大于等于）它的左、右孩子的關(guān)鍵字。 ? 最壞情況是每一趟都要進(jìn)行交換，總的記錄移動(dòng)次數(shù)為 RMN = 3(n1)。因此，總的關(guān)鍵字比較次數(shù)為： ??????? 20 21ninninKCN )()(? 記錄的移動(dòng)次數(shù)與記錄序列的初始排列有關(guān)。 } } } 簡單選擇排序的算法 : 算法分析 : 簡單選擇排序的 關(guān)鍵字比較次數(shù) KCN與記錄的初始排列無關(guān)。 [i] = [k]。 j++ ) if( [j].key [k].key ) k = j 。 // 在當(dāng)前無序區(qū)選關(guān)鍵字最小的記錄 for( j=i+1。 i。 RedType temp。 簡單選擇排序 (Select Sort) 21 25 49 25* 16 08 0 1 2 3 4 5 初始 21 25* i = 0 25 16 49 08 最小者 08 交換 21,08 25 16 08 25* 49 21 i = 1 最小者 16 交換 25,16 49 i = 2 08 16 25* 25 21 最小者 21 交換 49,21 0 1 2 3 4 5 49 25* i = 3 08 16 25 21 最小者 25* 無交換 25* i = 4 49 最小者 25 無交換 25 21 16 08 25 16 08 25* 49 21 結(jié)果 各趟排序后的結(jié)果 0 1 2 3 4 5 49 16 08 25* 49 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1