數據結構之排序課件(編輯修改稿)

　

【文章內容簡介】 個一維數組 r中，具體的做法是：設兩個指示器 i和 j，初始時 i指向數組中的第一個數據， j指向最末一個數據。 i先不動使 j逐步前移，每次對二者所指的數據進行比較，當遇到 r[i]大于 r[j]的情況時，就將二者對調位置；然后令 j固定使 i逐步后移做數據比較，當遇到 r[i]大于 r[j] 時，又進行位置對調；然后又是 i不動使 j前移作數據比較； …… ； ?如此反復進行，直至 i與 j兩者相遇為止。 ?圖 過程。 ?圖中括號中的數據表示正進行比較的兩個數據，左面一個的下標為 i，右面一個的下標為j。 ?最后一行只有一個括號，說明 i與 j相等了，此單元即是數據 13的最終位置。 圖 一趟數據比較和互換 ( 13 ) 15 7 10 30 4 8 ( 25 ) ( 13 ) 15 7 10 30 4 ( 8) 25 8 ( 15 ) 7 10 30 4 ( 13 ) 25 8 ( 13 ) 7 10 30 ( 4) 15 25 8 4 ( 7) 10 30 ( 13 ) 15 25 8 4 7 ( 10 ) 30 ( 13 ) 15 25 8 4 7 10 ( 30 ) ( 13 ) 15 25 8 4 7 10 ( 13 ) 30 15 25 一趟快速排序 void quickOnePass ( r[ ], low, hig) { i=low, j=hig。 x=r[i]。 do { while( r[j].key= amp。amp。 (ij)) j。 if (ij) /*已找到了滿足 { r[i]=r[j]。 /*r[j].keyx的 r[j] i++。 } 快速排序算法續 while (r[i].key =) amp。amp。 ( ij )) i++。 if (ij) /*已找到了滿足 r[i].keyx的 r[i] { r[j]=r[i]。 j。 } } while (ij)。 r[i]=x。 return(i)。 } ?整個快速排序過程如下： Void quicksort(r[], low, hig) { int k。 If(lowhig) { k=quickonepass(r, low, hig)。 Quicksort(r, low, k1)。 Quicksort(r, k+1, hig)。 } } 快速排序分析 ?當初始序列有序或基本有序時，快速排序就接近于冒泡排序了，其時間復雜度為 O(n*n). ?該算法是霍爾 1962年提出的。在所有已發表的排序算法中，該算法是研究最深的。當時他就發現了以上的問題，他在文章中建議用兩種方法改進：產生一個隨機數，或選擇一個小樣本中值。 1969年，辛格爾頓就遵循了這一建議，采用R[1].key, R[n].key, R[n/2].key的中間值，故稱作“三者取中”法。 快速排序分析 ?快速排序的平均時間復雜性為 O(nlogn)，對 n較大的情況，這種算法是平均速度最快的排序算法，但當 n很小時，此方法往往比其他簡單排序方法還要慢。 ?快速排序更偏愛一個“ 雜亂無章 ”的序列。 ?快速排序是不穩定的。 返回 堆排序 ?堆的概念 ?堆排序（ Heap Sort）是利用二叉樹的一種排序方法。 ?（大根）堆（ Heap）：在一棵完全二叉樹中，每個結點如果有兒子的話，此結點必須大于或等于其兒子結點。 ?由于堆是完全二叉樹，采用將結點順序編號存入一維數組中的表示法比鏈接表示法節省存儲空間，也便于計算。 ?設某堆的結點數共有 n個，順序將它們存入一維數組 r[] 中。根據順序表示二叉樹的特點，除下標為 1的結點 (根結點 )沒有父結點以外，其余下標為 j 的結點（ 2≤j≤n）都有父結點，父結點的下標為 i= 。 ? ?2/j?由堆的定義可知，其根結點（即在數組中下標為 1的結點）具有最小的關鍵字，堆排序就是利用這一特點進行的。 ?實現堆排序需要解決兩個問題： 1. 把一組待排序的元素構建成堆； 2. 輸出堆頂后 , 如何將剩下的 n1個元素 調整成一個新的堆 . 先介紹第 2個問題 設堆頂輸出后，以堆的最后一個元素代替之，此時的左子樹、右子樹都是堆，則只需自上而下地調整即可。這個調整過程稱為“ 篩選 ”。 例： void sift (r[], i, m) /*把 R[i： m]看成完全二叉樹 ， 以 { j=2*i。 /*R[i+1]和 R[i+2]為根的左右子樹是 x=r[i]。 /*堆 ， 現要調整 R[i]， 使整個序列 while (j=m) /*R[i： m]成為一個堆 { if ((jm amp。amp。 r[j].keyr[j+1].key)) j++。 if (r[j].key) /*j為左右兒子中較小者的下標 { r[i]=r[j]。 /*左右兒子中較小者上移 ， i=j。 j=2*i } else break 。 /*x不大于左右兒子 ， 即已找到 } /*了合適的位置 i， 循環結束 r[i]=x。 /*把 x放在 i的位置上 } 篩選算法 ?介紹第 1個問題，即把一個無序的序列建成一個堆。 ?把一個 n個元素的無序序列看成一棵完全二叉樹，則最后一個內部結點的下標是 ?n/2? .因此，只需從第 ?n/2? 個元素開始，直到第 1個元素，依次調用 sift, 即可建成一個堆。 ?例： 堆排序算法 void heapsort (r[], n) { int i。 for (i=n/2。 i=1。 i) sift (r, i, n)。 /* 初始建堆 */ for (i=n。 i1。 i) { r[1]?r[i]。 /*堆頂元素和最后一個 sift (r, 1, i1)。 /*元素交換 } } 堆排序算法分析 ?其運行時間主要消耗在建初始堆和進行反復的篩選上。對 n個元素，樹的深度 k=?log2n? +1，篩選算法中關鍵字的比較次數最多為 2（ k1），共調用了 n1次，所以總的比較次數小于 2n（ ?log2n?）次；在建初始堆