數(shù)據(jù)結(jié)構(gòu)之排序課件(編輯修改稿)
2024-10-06 09:02 本頁面
【文章內(nèi)容簡介】 個一維數(shù)組 r中，具體的做法是：設(shè)兩個指示器 i和 j，初始時(shí) i指向數(shù)組中的第一個數(shù)據(jù)， j指向最末一個數(shù)據(jù)。 i先不動使 j逐步前移，每次對二者所指的數(shù)據(jù)進(jìn)行比較，當(dāng)遇到 r[i]大于 r[j]的情況時(shí)，就將二者對調(diào)位置；然后令 j固定使 i逐步后移做數(shù)據(jù)比較，當(dāng)遇到 r[i]大于 r[j] 時(shí)，又進(jìn)行位置對調(diào)；然后又是 i不動使 j前移作數(shù)據(jù)比較； …… ； ?如此反復(fù)進(jìn)行，直至 i與 j兩者相遇為止。 ?圖 過程。 ?圖中括號中的數(shù)據(jù)表示正進(jìn)行比較的兩個數(shù)據(jù)，左面一個的下標(biāo)為 i，右面一個的下標(biāo)為j。 ?最后一行只有一個括號，說明 i與 j相等了，此單元即是數(shù)據(jù) 13的最終位置。 圖 一趟數(shù)據(jù)比較和互換 ( 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++。 } 快速排序算法續(xù) 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)。 } } 快速排序分析 ?當(dāng)初始序列有序或基本有序時(shí)，快速排序就接近于冒泡排序了，其時(shí)間復(fù)雜度為 O(n*n). ?該算法是霍爾 1962年提出的。在所有已發(fā)表的排序算法中，該算法是研究最深的。當(dāng)時(shí)他就發(fā)現(xiàn)了以上的問題，他在文章中建議用兩種方法改進(jìn)：產(chǎn)生一個隨機(jī)數(shù)，或選擇一個小樣本中值。 1969年，辛格爾頓就遵循了這一建議，采用R[1].key, R[n].key, R[n/2].key的中間值，故稱作“三者取中”法。 快速排序分析 ?快速排序的平均時(shí)間復(fù)雜性為 O(nlogn)，對 n較大的情況，這種算法是平均速度最快的排序算法，但當(dāng) n很小時(shí)，此方法往往比其他簡單排序方法還要慢。 ?快速排序更偏愛一個“ 雜亂無章 ”的序列。 ?快速排序是不穩(wěn)定的。 返回 堆排序 ?堆的概念 ?堆排序（ Heap Sort）是利用二叉樹的一種排序方法。 ?（大根）堆（ Heap）：在一棵完全二叉樹中，每個結(jié)點(diǎn)如果有兒子的話，此結(jié)點(diǎn)必須大于或等于其兒子結(jié)點(diǎn)。 ?由于堆是完全二叉樹，采用將結(jié)點(diǎn)順序編號存入一維數(shù)組中的表示法比鏈接表示法節(jié)省存儲空間，也便于計(jì)算。 ?設(shè)某堆的結(jié)點(diǎn)數(shù)共有 n個，順序?qū)⑺鼈兇嫒胍痪S數(shù)組 r[] 中。根據(jù)順序表示二叉樹的特點(diǎn)，除下標(biāo)為 1的結(jié)點(diǎn) (根結(jié)點(diǎn) )沒有父結(jié)點(diǎn)以外，其余下標(biāo)為 j 的結(jié)點(diǎn)（ 2≤j≤n）都有父結(jié)點(diǎn)，父結(jié)點(diǎn)的下標(biāo)為 i= 。 ? ?2/j?由堆的定義可知，其根結(jié)點(diǎn)（即在數(shù)組中下標(biāo)為 1的結(jié)點(diǎn)）具有最小的關(guān)鍵字，堆排序就是利用這一特點(diǎn)進(jìn)行的。 ?實(shí)現(xiàn)堆排序需要解決兩個問題： 1. 把一組待排序的元素構(gòu)建成堆； 2. 輸出堆頂后 , 如何將剩下的 n1個元素 調(diào)整成一個新的堆 . 先介紹第 2個問題 設(shè)堆頂輸出后，以堆的最后一個元素代替之，此時(shí)的左子樹、右子樹都是堆，則只需自上而下地調(diào)整即可。這個調(diào)整過程稱為“ 篩選 ”。 例： void sift (r[], i, m) /*把 R[i： m]看成完全二叉樹 ， 以 { j=2*i。 /*R[i+1]和 R[i+2]為根的左右子樹是 x=r[i]。 /*堆 ， 現(xiàn)要調(diào)整 R[i]， 使整個序列 while (j=m) /*R[i： m]成為一個堆 { if ((jm amp。amp。 r[j].keyr[j+1].key)) j++。 if (r[j].key) /*j為左右兒子中較小者的下標(biāo) { r[i]=r[j]。 /*左右兒子中較小者上移 ， i=j。 j=2*i } else break 。 /*x不大于左右兒子 ， 即已找到 } /*了合適的位置 i， 循環(huán)結(jié)束 r[i]=x。 /*把 x放在 i的位置上 } 篩選算法 ?介紹第 1個問題，即把一個無序的序列建成一個堆。 ?把一個 n個元素的無序序列看成一棵完全二叉樹，則最后一個內(nèi)部結(jié)點(diǎn)的下標(biāo)是 ?n/2? .因此，只需從第 ?n/2? 個元素開始，直到第 1個元素，依次調(diào)用 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)。 /*元素交換 } } 堆排序算法分析 ?其運(yùn)行時(shí)間主要消耗在建初始堆和進(jìn)行反復(fù)的篩選上。對 n個元素，樹的深度 k=?log2n? +1，篩選算法中關(guān)鍵字的比較次數(shù)最多為 2（ k1），共調(diào)用了 n1次，所以總的比較次數(shù)小于 2n（ ?log2n?）次；在建初始堆
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1