c語言數(shù)據(jù)結(jié)構(gòu)_第08講排序(編輯修改稿)
2024-11-13 03:54 本頁面
【文章內(nèi)容簡介】 ?nnjnj932 快速排序 （ Quick Sort） 1． 基本思想 就排序時間而言 ， 快速排序被認為是一種最好的內(nèi)部排序方法 。 通過一趟快速排序?qū)⒋判虻挠涗浗M分割成獨立的兩部分 ， 其中前一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字??；后一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字大 ， 樞軸記錄得到了它在整個序列中的最終位置并被存放好 ， 這個過程稱為一趟快速排序 。 第二趟再分別對分割成兩部分子序列 ，再進行快速排序 ， 這兩部分子序列中的樞軸記錄也得到了最終在序列中的位置而被存放好 ， 并且它們又分別分割出獨立的兩個子序列 …… 。 顯然 ， 這是一個遞歸的過程 ， 不斷進行下去 ， 直到每個待排序的子序列中只有一個記錄時為止 ， 整個排序過程結(jié)束 。 快速排序是對冒泡排序的一種改進 。 這里有個問題 ， 就是如何把一個記錄組分成兩個部分 ？通常是以序列中第一個記錄的關(guān)鍵字值作為樞軸記錄 。 2. 具體做法： 設待排序列的下界和上界分別為 low和 high， R[low]是樞軸記錄 ， 一趟快速排序的具體過程如下： （ 1） 首先將 R[low]中的記錄保存到 pivot變量中 ， 用兩個整型變量 i,j分別指向 low和 high所在位置上的記錄； （ 2） 先從 j所指的記錄起自右向左逐一將關(guān)鍵字和 進行比較 ， 當找到第 1個關(guān)鍵字小于 ， 將此記錄復制到 i 所指的位置上去； （ 3） 然后從 i+1所指的記錄起自左向右逐一將關(guān)鍵字和 ， 當找到第 1個關(guān)鍵字大于 錄時 ， 將該記錄復制到 j所指的位置上去； （ 4） 接著再從 j1所指的記錄重復以上的 （ 2） 、 （ 3） 兩步 ，直到 i=j為止 ， 此時將 pivot中的記錄放回到 i（ 或 j） 的位置上 ， 一趟快速排序完成 。 3.【 例 95】 對數(shù)據(jù)序列： 70， 75， 69， 32， 88， 18， 16，58進行快速排序 。 4． 算法 int Partition(int i,int j) //i、 j為形參 ， 分別代表 low和 high { RecType pivot=R[i]。 while(ij) // 從表的兩端交替地向中間掃描 { while(ijamp。amp。R[j].key=) j 。 if (ij) R[i++]=R[j]。 while (ijamp。amp。R[i].key=) i+ +。 if (ij) R[j ]=R[i]。 } R[i]=pivot。 return i。 } void QuickSort(int low,int high) // 遞歸形式的快排序 { int pivotpos,k。 if (lowhigh) { pivotpos=Partition(low,high)。 //調(diào)用 Partition(low,high)函數(shù) QuickSort(low,pivotpos1)。 // 對低子表遞歸排序 QuickSort(pivotpos+1,high)。 // 對高子表遞歸排序 } } 5． 效率分析 空間效率：快速排序是遞歸的 ， 每層遞歸調(diào)用時的指針和參數(shù)均要用棧來存放 ， 遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致 。 因而 ， 存儲開銷在理想情況下為 O(log2n)，即樹的高度；在最壞情況下 ， 即二叉樹是一個單鏈 ， 為O(n)。 時間效率：在 n個記錄的待排序列中 ， 一次劃分需要約n次關(guān)鍵碼比較 ， 時效為 O(n)， 若設 T(n)為對 n個記錄的待排序列進行快速排序所需時間 。 理想情況下：每次劃分 ， 正好將分成兩個等長的子序列 ， 則時間復雜度為 O(nlog2n)； 最壞情況下：快速排序每次劃分 ， 只得到一個子序列 ，這時快速排序蛻化為冒泡排序的過程 ， 其時間復雜度最差 ，為 O(n2)。 快速排序是通常被認為在同數(shù)量級 （ O(nlog2n)） 的排序方法中平均性能最好的 。 快速排序是一個不穩(wěn)定的排序方法 。 返 回 選擇排序主要是從待排序列中選取一個關(guān)鍵字值最小的記錄 ， 把它與第一個記錄交換存儲位置 ， 使之成為有序 。 然后在余下的無序的記錄中 ， 再選出關(guān)鍵字最小的記錄與無序區(qū)中的第一個記錄交換位置 ， 又使之成為有序 。 依次類推 ，直至完成整個排序 。 941 簡單選擇排序 1． 基本思想 （ 1） 初始狀態(tài)：整個數(shù)組 r劃分成兩個部分 ， 即有序區(qū) （ 初始為空 ） 和無序區(qū) 。 （ 2） 基本操作：從無序中選擇關(guān)鍵字值最小的記錄 ， 將其與無序區(qū)的第一個記錄交換 （ 實質(zhì)是添加到有序區(qū)尾部 ） 。 從初態(tài) （ 有序區(qū)為空 ） 開始 ， 重復步驟 （ 2） ， 直到終態(tài)（ 無序區(qū)為空 ） 。 94 選擇排序 2.【 例 96】 對： 53 36 48 36 60 7 18 41 進行簡單選擇排序 3． 算法 void Selectsort() { for (i=1。in。i++) { h=i。 for (j=i+1。j=n。j++) if (R[j].keyR[h].key) // 選擇關(guān)鍵字值最小的記錄 h=j。 if (h!=j) { R[0]=R[i]。R[i]=R[h]。R[h]=R[0]。} // 交換記錄 } } 4． 效率分析 簡單選擇排序比較次數(shù)與關(guān)鍵字初始排序無關(guān) 。 找第一個最小記錄需進行 n1次比較 ， 找第二個最小記錄需要比較 n2次 ， 找第 i個最小記錄需要進行 ni次比較 ，總的比較次數(shù)為： （ n1） +（ n2） +…… +（ ni） +…… 2+1=n(n1)/2=n2/2 時間復雜度： O(n2) 輔助空間： O（ 1） 簡單選擇排序是不穩(wěn)定的排序方法 。 942 樹形選擇排序 樹形選擇排序照錦標賽的思想進行 。 比賽開始 ， 將 n個參賽選手看成完全二叉樹 （ 或滿二叉樹 ） 的葉結(jié)點 ， 共有 2n2或 2n1個結(jié)點 。 首先 ， 兩兩進行比賽 (在樹中是兄弟的進行 ， 否則輪空 ， 直接進入下一輪 )， 勝出的再兄弟間再兩兩進行比較 ， 直到產(chǎn)生第一名 。 接下來 ， 將第一名的結(jié)點看成最差的 ， 并從該結(jié)點開始 ， 沿該結(jié)點到根的路徑上 ， 依次進行各分枝結(jié)點子女間的比較 ， 勝出的就是第二名 。 因為和他比賽的均是剛剛輸給第一名的選手 。 如此 ，繼續(xù)進行下去 ， 直到所有選手的名次排定 。
教學課件相關(guān)推薦
鄂ICP備17016276號-1