【正文】 行各分枝結(jié)點子女之間的比較 ， 上升到根結(jié)點的是次小關(guān)鍵字值的記錄 ， 如下圖 (b)所示；如此繼續(xù)進(jìn)行下去 ， 直到所有記錄都已選出時為止 。 選擇排序 直接選擇排序 樹形選擇排序 堆排序 樹形選擇排序 ?樹形選擇排序 （ tree selection sort） 也稱作 錦標(biāo)賽排序 （ tournament sort） ， 這種排序方法是按照錦標(biāo)賽的思路進(jìn)行的 。 } } } /*selectsort end*/ 直接選擇排序的算法分析 ?直接選擇排序只需要一個記錄大小的輔助存儲空間用于記錄交換 ， 其空間復(fù)雜度為 O(1)。j++) if(R[j].keyR[m].key) m=j。i=n1。 ?其 具體做法 是： ?對于待排序文件 R[1..n]， 通過比較首先選出關(guān)鍵字值最小的記錄與 R[1]交換 ， ?然后在其余記錄中選出次小關(guān)鍵字的記錄與R[2]交換 …… ?如此進(jìn)行 n1次的選擇與交換 ， R[1..n]中所有記錄就按關(guān)鍵字升序次序排列完畢 。 ?快速排序算法是一種 不穩(wěn)定的排序 方法 。 快速排序的算法分析（續(xù)） ?在 最壞情況 下 ， 基準(zhǔn)二叉樹是一棵單枝二叉檢索樹 ， 深度為 n， 存儲開銷為 O(n)， 時間開銷為 O(n2)。 快速排序的算法舉例（續(xù)） 快速排序的算法舉例（續(xù)） 快速排序的算法舉例（續(xù)） 快速排序的算法分析 ?快速排序過程中各趟中所選擇的基準(zhǔn)可以用一棵二叉樹來表示 ， 如上例中的基準(zhǔn)二叉樹如右圖所示 。 if(st) {i=divideareasort(R,s,t)。 R[i]=temp。(ij)) i++。 if(ij) {R[i]=R[j]。 temp=R[s]。 快速排序的算法描述 ?這種把一個待排序區(qū)間通過基準(zhǔn)記錄 （ 第一個記錄 ） 分割成為兩個區(qū)間的一次分割排序算法如下： int divideareasort(recordtype R[],int s,int t) {int i,j。 交換排序 冒泡排序 快速排序 快速排序 ?快速排序 （ quick sort） 也稱作分區(qū)交換排序 ， 是對冒泡排序的一種改進(jìn)排序方法 。 冒泡排序算法分析（續(xù)） ?上述的冒泡排序算法還可以作一些改進(jìn)來提高排序速度 ， 比如： ?在每趟排序中記住最后一次發(fā)生交換記錄的位置 K， 因為位置 K之前的記錄都已排好了序 ， 下一趟的排序可以終止于位置 K而不必進(jìn)行到預(yù)定的下界位置 i。 } /*置已交換標(biāo)志 */ if(flag==0) break。j) if(R[j1].key R[j].key) {temp=R[j1]。in1。 ?為此 ， 需在算法中引入一個交換狀態(tài)變量 flag， 在每一趟排序之前置 flag為 0， 每次交換時給 flag加 1，若一趟結(jié)束時 flag為 0則終止算法 。 然后對 n1個記錄重復(fù)類似的操作 ， 次小關(guān)鍵字值的記錄上浮到 R[2]的位置上 。 ?本節(jié)介紹兩種交換排序的方法： ?一種是冒泡排序 ， ?一種是快速排序 。 共享棧插入排序舉例 共享棧插入排序舉例（續(xù)） 共享棧插入排序（續(xù)） ?共享棧插入排序不需要增加額外的存儲開銷 ， 在時間性能上與二路插入排序相當(dāng) ， 而且有效地避免了因 R[1]為待排序記錄中關(guān)鍵字值為最大或最小記錄時完全失去優(yōu)越性的不足 。 ?當(dāng) R[i].key[top1].key時 ， 由棧 1反復(fù)傳送記錄到棧 2，直到 R[i].key≥R[top1].key時將 R[i]插入棧 1。 ?其基本思想是： ?把待排序的記錄數(shù)組 R看作是一個靜態(tài)的共享棧 （ 棧 1和棧 2） ， 棧 1按數(shù)組下標(biāo)由小到大方向增長 ， 棧 2按數(shù)組下標(biāo)由大到小方向增長；棧 1中按關(guān)鍵字升序排列壓入待排序記錄 ， 棧 2中按關(guān)鍵字降序排列壓入待排序記錄 。 它只能減少移動次數(shù)而不能絕對避免移動記錄 ， 若要大幅度降低移動次數(shù) ， 可改變存儲結(jié)構(gòu)為靜態(tài)鏈表 ， 進(jìn)行表插入排序 。 ?二路插入排序 （ 2way insertion sort） 是在二分法插入排序基礎(chǔ)上的進(jìn)一步改進(jìn) ， 改進(jìn)的目標(biāo)是減少排序過程中記錄的移動次數(shù) ， 但為此多開銷了 n個記錄大小的輔助存儲空間 。 插入排序 直接插入排序 希爾排序 其它插入排序簡介 ? 由第七章的討論我們知道 ， 對有序表采用二分法檢索 ， 檢索性能大大優(yōu)于順序檢索 。 算法中的主要時間開銷在于三重循環(huán)： ?外層 dowhile循環(huán)控制排序趟數(shù) ， 共執(zhí)行 log2n次 。 j = j – d。i=d+n。i++) R[i].key = maxint。 這種監(jiān)視哨的設(shè)置方法 ， 沒有在監(jiān)視哨中保存各組中的一個個待插入記錄 ， 但可以統(tǒng)一保存待插入記錄于R[0]中 。 ?另外 ， 在 for循環(huán)中的分組執(zhí)行直接插入排序的過程 ，是依次先插入 d個組中的第二個記錄 ， 再插入 d個組中的第三個記錄 …… 最后插入 d個組中的最后一個記錄；是 d個組的交替插入過程 ， 而不是一個組的直接插入排序完成后再進(jìn)行下一組 ， 這樣有利于算法設(shè)計的簡潔性和算法描述的方便性 。 j = jd。 R[0] = R[j]。 do {d = (d+1)/2。 如何選取增量序列才能產(chǎn)生最好的排序效果 ， 至今仍無法從數(shù)學(xué)角度得出圓滿的結(jié)論；然而逐步縮小增量和最后一次增量為 1是大家不爭的事實 。 ?隨著 di減小 ， 組數(shù)變少組中記錄個數(shù)變多的同時 ， 組中記錄也逐步變得基本有序 ， 使得在一趟中進(jìn)行直接插入排序時的效率大大地提高 。 ?另外 ， 當(dāng) n的值很小時 ， n2的值受 n的值的影響也不太大 ， 直接插入排序的效率也比較高 。 它是 1959年由 的對直接插入排序的一種改進(jìn)方法 。 直接插入排序的算法分析 (續(xù) ) ?若初始文件中各記錄是隨機排列 ， 即關(guān)鍵字的各種排列的出現(xiàn)概率相同時 ， 我們可取上述最好與最壞情況的平均值作為比較和移動的平均次數(shù) ， 約為 n2/4,由此可得直接插入排序的時間復(fù)雜度為 O(n2)。 } }/*insertsorting end*/ 直接插入排序的算法分析 ?在上面的算法中 ， 外層 for循環(huán)控制 n1趟插入 ， 內(nèi)層 while循環(huán)完成一趟的關(guān)鍵字比較 、 記錄后移和確定位置后的插入操作 。 j=i1。 直接插入排序的算法描述 ? 直接插入排序的算法描述如下： void insertsorting(recordtype R[],int n) {int i,j。 直接插入排序 舉例 ?例如 ， 已知待排序文件中記錄的關(guān)鍵字序列為 （ 23，48， 32， 107， 86， 75， 68） ， 直接插入排序的過程可示意如下： ?其中 ， 方括號表示已排好序的序列 ， i表示插入第 i個記錄 。 ?本節(jié)介紹的插入排序方法有 直接插入排序 和 希爾排序 ；并簡介二分法插入排序 、 二路插入排序和共享棧插入排序 。 排序的基本概念（續(xù)） ?在本章主要討論內(nèi)部排序算法 ， 以記錄數(shù)組作為待排序文件的組織形式 ， 并假定關(guān)鍵字均為整數(shù) ，按遞增次序討論排序算法 （ 即討論升序排序問題 ） 。通常待排序文件的組織形式有三種方式： ?以一維數(shù)組作為組織形式 ， 排序過程是對記錄本身進(jìn)行物理重排 ， 通過比較和判定把記錄移動到合適的位置； ?以鏈表 （ 動態(tài)鏈表或靜態(tài)鏈表 ） 作為組織形式 ， 排序過程中無需移動記錄 ， 僅需修改指針即可 ， 通常把這類排序稱為表排序； ?為待排序文件組織一個輔助表 ， 如組織一張含關(guān)鍵字和指向記錄指針的索引表 ， 在排序過程中只需對輔助表的表目進(jìn)行物理重排 ， 不需移動記錄本身 ， 在排序結(jié)束后按輔助表調(diào)整記錄位置 。 ?內(nèi)部排序 是指待排序文件放在內(nèi)存中進(jìn)行排序的排序；內(nèi)部排序 適用于 記錄個數(shù)不很多的較小待排序文件的排序； ?外部排序 是指在待排序文件很大時 ， 內(nèi)存中不能一次容納全部記錄 ， 還要借助于外存存放待排序文件 ， 在排序過程中需要對外存進(jìn)行訪問的排序；外部排序則 適用于 記錄個數(shù)太多不能一次全部放入內(nèi)存的較大待排序文件的排序 。 ?當(dāng)排序碼是次關(guān)鍵字時 ， 同一關(guān)鍵字值可能標(biāo)識了兩個或兩個以上的記錄 ， 所以排序結(jié)果不惟一 。 ?若關(guān)鍵字滿足遞增 （ 即不減 ） 關(guān)系時 ， 稱作按關(guān)鍵字 升序排序 (ascending sort)； ?若關(guān)鍵字滿足遞減 （ 即不增 ） 關(guān)系時 ， 稱作按關(guān)鍵字 降序排序 (descending sort)。 例如在實際問題的數(shù)據(jù)處理中常會遇到這樣的情況 ， 需要把若干名字如人名 、 地名 、 國名 、 書名 、 校名 、 物名等按字母順序列表；需要把若干數(shù)值如各種考試分?jǐn)?shù) 、 田賽的長度 、 徑賽的時間等按成績次序排名；需要把若干不同屬性的記錄按照某種方法排列次序 …… 。 ?在現(xiàn)今的計算機系統(tǒng)中 ， 有相當(dāng)大的一部分 CPU時間開銷是用于對數(shù)據(jù)的排序整理上的 。算法與數(shù)據(jù)結(jié)構(gòu) 第 8章 排序及基本算法 排序及基本算法 ?為了便于檢索 ， 人們通常希望能在計算機中保存的數(shù)據(jù)是按關(guān)鍵字值大小排列的有序表 。 ?又如為了方便檢索 ， 需要構(gòu)造二叉檢索樹 、 B樹和 B+樹等樹表 ， 構(gòu)造這些樹表的過程本身就是一個排序的過程 。 ? 排序的實際應(yīng)用領(lǐng)域也是非常廣泛的 。 ?排序 （ sort） 是這樣一種操作 ， 它確定文件中 n個記錄的一種排列 （ Rj1， Rj2 … Rjn） ， 使得其相應(yīng)關(guān)鍵字滿足遞增 （ 即不減 ） 關(guān)系 Kj1≤Kj2≤… ≤Kjn或遞減 （ 即不增 ） 關(guān)系 Kj1≥Kj2≥… ≥Kjn。 ?當(dāng)排序碼是主關(guān)鍵字時 ， 由于主關(guān)鍵字可以惟一標(biāo)識一個記錄 ， 所以排序結(jié)果是惟一的 。 排序的分類 ?根據(jù)排序過程中待排序文件存放的位置不同 ， 可以把排序分為 內(nèi)部 和 外部排序 兩大類 。 內(nèi)部排序文件的組織形式 ? 每種內(nèi)部排序方法均可在不同的存儲結(jié)構(gòu)上實現(xiàn) 。 ?內(nèi)部排序的時間代價主要用關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)來衡量； ?而外部排序的時間代價主要用訪問外存儲器的次數(shù)來衡量 。 /*其它域 */ }recordtype /*記錄類型標(biāo)識符 */ 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡介 插入排序 ?插入排序 的基本方法是：每次將一個待排序的記錄 Ri， 按其關(guān)鍵字 Ki的大小插入到前面已經(jīng)排好序的部分文件中的適當(dāng)位置 ， 直到全部記錄插完整個文件已排好序為止 。 ?一開始 ， 第一個記錄是一個長度為 1的有序序列； ?從第二個記錄起 ， 每次用第 i(i=2， 3 … n)個記錄的關(guān)鍵字 Ki與前面有序序列中記錄的關(guān)鍵字 Ki Ki2 … K1進(jìn)行比較 ， 從而找到 Ki所在記錄應(yīng)該插入的位置并依次后移各記錄后插入之 ， 使得有序序列的長度加 1； ?這樣插入 n1次就會得到 n個記錄的有序序列 ， 從而完成整個文件的排序工作 。 ?設(shè)置 監(jiān)視哨 是一種程序設(shè)計技巧 ， 既使程序控制簡單 ， 又節(jié)省了測試時間提高了檢索效率 。i++) {R[0]=R[i]。 } R[j+1]=R[0]。 直接插入排序的算法分析 (續(xù) ) ?在最壞的情況下是待排序文件中各記錄為關(guān)鍵字的逆序排列 （ 即遞減序列 ） ， 每一趟中需要和前面已排好序的 i1個記錄以及監(jiān)視哨中 R[0]進(jìn)行關(guān)鍵字值的比較 ， 即第 i趟中需進(jìn)行 i次比較操作； ?向后移動次數(shù)為 i1次 ， 加上與監(jiān)視哨之間的兩次移 動 ， 第 i趟需要移動記錄 i+1次；總的比較次數(shù)為 次 ， 總的移動次數(shù)為 次 ， 算法的時間復(fù)雜度為 O(n2)。 插入排序 直接插入排序 希爾排序 其它插入排序簡介 希爾排序 ?希爾排序 （ shell’s method ） ， 又稱作縮小增量排序（ diminishing increatment） 。 ?換句話說 ， 如果待排序文件能夠基本有序 ， 則文件中的大多數(shù)記錄都不需要進(jìn)行插入 （ 即后移 ） 操