[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)-wenkub.com
2024-10-16 04:11 本頁(yè)面
【正文】 3. 歸并排序所需輔助空間最多，其空間復(fù)雜度為 O (n)。當(dāng)排序是按記錄的次關(guān)鍵字進(jìn)行時(shí)，則應(yīng)根據(jù)問題所需慎重選擇。 各種排序法的比較 ： （ 5）從穩(wěn)定性來(lái)看，大部分時(shí)間復(fù)雜度為 O(n2)的簡(jiǎn)單排序法都是穩(wěn)定的。 內(nèi)部排序方法的比較和選擇 選取排序方法時(shí)需要考慮的因素有： ? 待排序的記錄數(shù)目 ? 記錄本身信息量的大小 ? 關(guān)鍵字的結(jié)構(gòu)及其分布情況 ? 對(duì)排序穩(wěn)定性的要求 ? 語(yǔ)言工具的條件、輔助空間的大小 排序方法 最壞時(shí)間 復(fù)雜度 平均時(shí)間 復(fù)雜度 輔助空間 穩(wěn)定性 直接插 入排序 O(n2) O(n2) O(1) 穩(wěn)定的 二分法 插入排序 O(n2) O(n2) O(1) 穩(wěn)定的 表插入排序 O(n2) O(n2) O(n) 穩(wěn)定的 Shell排序 O() O() O(1) 不穩(wěn)定的 直接選 擇排序 O(n2) O(n2) O(1) 不穩(wěn)定的 堆排序 O(nlog2n) O(nlog2n) O(1) 不穩(wěn)定的 起泡排序 O(n2) O(n2) O(1) 穩(wěn)定的 快速排序 O(n2) O(nlog2n) O(log2n) 不穩(wěn)定的 基數(shù)排序 O(d(n+r)) O(d(n+r)) O(r+n) 穩(wěn)定的 歸并排序 O(nlog2n) O(nlog2n) O(n) 穩(wěn)定的 （ 1）平均時(shí)間性能：以快速排序法最佳，但最壞情況 下不如堆排序和歸并排序；在 n較大時(shí)，歸并排序比堆排序 快，但所需輔助空間最多。 MSort(SR, TR2, m+1, t)。 RedType TR2[MAXSIZE+1]。 length=2*length。jn。 while (i+2*length1n) { MERGE(R,R1,i,i+length1,i+2*length1)。 l=nj。 if( i = m ) for( l=0。amp。 ? 將待排序記錄序列 R1,R2,… ,Rn看成為 n個(gè)長(zhǎng)度為 1 的有序子序列 ， 把這些子序列兩兩進(jìn)行歸并 ， 便得到 ┌ n/2┐ 個(gè)長(zhǎng)度為 2的有序子序列 ， 然后再兩兩歸并 ， …… ,如此重復(fù) ， 直到最后得到一個(gè)長(zhǎng)度為 n的有序記錄序列為止 ， 這種方法成為二路歸并方法 。 ? ??????1212ki1i ik? 堆排序過程中進(jìn)行 n1次重建堆所進(jìn)行的總比較次數(shù)不超過下式： 2*( ?log2(n1)?+?log2(n2)?+… +?log22? ) 2n ?log2n? = O(nlog2n) ? 因 此 堆 排 序 總 的 時(shí) 間 復(fù) 雜 度 是 O(n+nlog2n)= O(nlog2n)。 // 將 [1..i1]重新調(diào)整為大頂堆 } } 堆排序的算法 : 算法分析 : ? 堆排序的時(shí)間主要由 建立初始堆 和不斷 重復(fù)調(diào)整堆 這兩部分的時(shí)間開銷構(gòu)成。 i ){ temp = [1]。 i0。 91 88 42 23 24 16 05 13 91 88 42 23 24 16 05 13 （ a）初始堆 R[1]到 R[8] 13 88 42 23 24 16 05 91 13 88 42 23 24 16 05 91 （ b）第一趟排序之后 （ c）重建的堆 R[1]到 R[7] 88 24 42 23 13 16 05 91 88 24 42 23 13 16 05 91 05 24 42 23 13 16 88 91 05 24 42 23 13 16 88 91 （ d）第二趟排序之后 （ e）重建的堆 R[1]到 R[6] 42 24 16 23 13 05 88 91 42 24 16 23 13 05 88 91 （ f）第三趟排序之后 05 24 16 23 13 42 88 91 05 24 16 23 13 42 88 91 （ g）重建的堆 R[1]到 R[5] 24 23 16 05 13 42 88 91 24 23 16 05 13 42 88 91 （ h）第四趟排序之后 13 23 16 05 24 42 88 91 13 23 16 05 24 42 88 91 （ i）重建的堆 R[1]到 R[4] 23 13 16 05 24 42 88 91 23 13 16 05 24 42 88 91 （ j）第五趟排序之后 05 13 16 23 24 42 88 91 05 13 16 23 24 42 88 91 （ k）重建的堆 R[1]到 R[3] 16 13 05 23 24 42 88 91 16 13 05 23 24 42 88 91 （ l）第六趟排序之后 05 13 16 23 24 42 88 91 05 13 16 23 24 42 88 91 （ m）重建的堆 R[1]到 R[2] 13 05 16 23 24 42 88 91 13 05 16 23 24 42 88 91 （ n）第七趟排序之后 05 13 16 23 24 42 88 91 05 13 16 23 24 42 88 91 void HeapSort(HeapType amp。結(jié)果具有次最大關(guān)鍵字的記錄又上浮到堆頂，即 R[1]位置。 } // 已知 [s..m]中記錄的關(guān)鍵字除 [s].key之外均滿足堆的定義，本算法調(diào)整 [s] 的關(guān)鍵字，使 [s..m]成為一個(gè)大頂堆 . 上述算法只是對(duì)一個(gè)指定的結(jié)點(diǎn)進(jìn)行調(diào)整。 if( = [j].key ) break。 j=m。 void HeapAdjust(HeapType amp。 ? 在堆排序主要需解決兩個(gè)問題： ① 如何建堆 ？ 在完全二叉樹中 ， 所有序號(hào) i ?n/2? 的結(jié)點(diǎn)都是葉子 ，因此 ， 以這些結(jié)點(diǎn)為根的子樹均已是堆 ， 這樣只需將以序號(hào)為 ?n/2? , ?n/2?1, ?n/2?2, … , 1的結(jié)點(diǎn)為根的子樹都調(diào)整為堆即可 。 ? 簡(jiǎn)單選擇排序總的時(shí)間復(fù)雜度是 O(n2) ? 簡(jiǎn)單選擇排序是一種不穩(wěn)定的排序方法。第 i 趟選擇具有最小關(guān)鍵字記錄所需的比較次數(shù)總是 ni 次，此處假定整個(gè)待排序記錄序列有 n 個(gè)記錄。 if( k != i ){ temp = [i]。 i++ ){ // 做 n1趟選擇排序 k = i。L){ int i, j。 08 16 21 25 25* 49 0 1 2 3 4 5 pivot 21 初始 08 16 21 25 25* 49 08 25* 08 16 21 25 25* 49 i = 1 i = 2 基本思想 ：每一趟 (例如第 i 趟， i = 1, 2, …, n1) 在后面 ni+1 個(gè)待排序記錄中選出關(guān)鍵字最小的記錄 , 作為有序記錄序列的第 i 個(gè)記錄。 ? 若能更合理地選擇 基準(zhǔn)記錄 ，使得每次劃分所得的兩個(gè)子序列中的記錄個(gè)數(shù)盡可能地接近，可以加速排序速度，但是由于記錄的初始排列次序是隨機(jī)的，這個(gè)要求很難辦到。若設(shè) T(n) 是對(duì) n 個(gè)元素的序列進(jìn)行排序所需的時(shí)間，而且每次對(duì)一個(gè)記錄正確定位后，正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為： T(n) ? n + 2 T(n/2 ) // 一趟劃分比較次數(shù)為 n1次 ? n + 2 ( n/2 + 2T(n/4) ) = 2n + 4T(n/4) ? 2n + 4 ( n/4 +2T(n/8) ) = 3n + 8T(n/8) ……… ? n log2n + nT(1) = O(n log2n ) ? 可以證明 ， 函數(shù) quicksort的平均計(jì)算時(shí)間也是 o(nlog2n)。 21 25* 25 49 08 16 ? 算法 partition利用序列第一個(gè)記錄作為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1