【正文】 t=e[j]。 e[k]=p。 for(i=d。 datatype other。 排序從最低關(guān)鍵字位 開始直到最高關(guān)鍵字位 ； ?每一趟按一個關(guān)鍵字位的值把各記錄分配到 rd個鏈隊(duì)列中去 ， 同一鏈隊(duì)列中的記錄都是用鏈域指針鏈接起來的 ， 所有的隊(duì)頭和隊(duì)尾指針分別存放在兩個數(shù)組中 ， 每一趟分配后通過修改指針將這 rd個鏈隊(duì)列中的記錄收集起來； ?如此這樣重復(fù)分配和收集 d趟 ， 便得到了待排序文件中各記錄的一個有序序列 。 ?它是先按最低關(guān)鍵字位 對待排序文件中的 n個記錄進(jìn)行排序 ， 按 的值把待排序文件中的 n個記錄分配到具有不同 值的若干個堆 ， ?然后按 值從小到大的次序收集在一起；下一次再按高一位關(guān)鍵字位 的值進(jìn)行分配和收集 ， 如此不斷地按更高一位關(guān)鍵字位進(jìn)行分配和收集； ?直到用 分配和收集之后 ， 整個文件按多關(guān)鍵字位 有序 。 ?因此 ， 要比較任意兩張撲克牌的大小 ， 方法是先比較花色 ， 若花色相同時再比較點(diǎn)力 。 len=2*len。 } if(i+len1n) merge(R,i,i+len1,n,R1)。 merge(R1,L,m,h,R)。 while(j=h) R1[k++]=R[j++]。 i=L。 ?堆排序 適宜用于 待排序文件中記錄較多的情況 ， 因?yàn)槠渲饕獣r間開銷在于建堆和調(diào)整堆 ， 記錄較少時不合算 。i) {temp=R[1]。 } R[i]=temp。 j=2*i。 堆排序過程舉例（續(xù)） ?由于 K3K2且 K3K1， 則 82與 25所在的兩個記錄交換位置； ?又由于交換破壞了右子樹的堆 ， 則需再次進(jìn)行類似的調(diào)整 ， 直至進(jìn)行到葉子結(jié)點(diǎn)； ?調(diào)整后的狀態(tài)如圖 (c)所示 ， 即得到一個有 n1個記錄的新堆 ， 同時得到次小關(guān)鍵字 25所在的記錄 。 ?這種方法就像過篩子一樣 ， 把最小關(guān)鍵字值的記錄一層一層地篩選出來 ， 最后輸出堆頂?shù)?最小關(guān)鍵字記錄 。 ?因此在一個堆中 ， 堆頂元素 （ 完全二叉樹的根 ） 必為堆中的最小 （ 或最大 ） 元素 ， 并且堆中的每一棵子樹也都是堆 。 樹形選擇排序舉例 ?選擇關(guān)鍵字值最小的記錄放在根結(jié)點(diǎn)位置的過程如下圖 (a)的二叉樹所示 。 R[m]=temp。 for(i=1。 ?所謂三者取中是指在 R[s]、 R[t]和 R[(s+t)/2]三者中選取關(guān)鍵字值居中的記錄作為分割區(qū)間的基準(zhǔn) ， 這種選取基準(zhǔn)記錄的方法可以大大改善快速排序在最壞情況下的性能 。 } } /*quicksort end*/ 快速排序的算法舉例 ?下面我們使用快速排序算法對關(guān)鍵字序列 （ 36， 73， 65，97， 13， 27， ， 29） 排序 ， 在下面的排序過程示例中 ，先給出第一趟中的區(qū)間分割的整個過程 ， 然后給出各趟的排序結(jié)果；用方括號表示區(qū)間 ， 用方框表示暫存變量 temp的關(guān)鍵字值 （ 并未參加交換 ， 在分割完成后才放入最終位置上 ） 。 } }while(ij)。(ij)) j。 快速排序算法 ?設(shè)兩個指示器變量 i和 j， 分別指向待排序區(qū)間的第一個記錄和最后一個記錄； ?先將第一個記錄移到暫存變量 temp中 ， 然后 j從區(qū)間的最后一個記錄起向前掃描 ， 直到找到滿足 R[j].key的記錄時 ， 將 R[j]移入 R[i]中； ?再令 i 自 i+1 起 向 后 掃 描 ， 直 到 找 到 滿 足R[i].key ， 將 R[i]移入 R[j]中； ?就這樣 j自 j1從后向前掃描一次移入一個 R[j]于 R[i]中 ，i自 i+1從前向后掃描一次移入一個 R[i]于 R[j]中 ， 反復(fù)交替的掃描和移動記錄； ?直到 i=j時把 temp移入 R[i]中 （ 區(qū)間中第一個記錄應(yīng)在的位置 ） ， 它把整個待排序區(qū)間分割為相互獨(dú)立的兩個更小的區(qū)間 。 ?在平均情況下 ， 關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)大約為最壞情況下的一半 ， 因此冒泡排序算法的時間復(fù)雜度為 O(n2)。j = i+1。 ?事實(shí)上存在不需要 n1趟就可以完全排好序的情況 ，如上例的第五趟排序后就已經(jīng)排好序了； ?其識別辦法是 ， 若某一趟冒泡排序過程中沒有進(jìn)行記錄的位置交換 ， 則說明待排序文件已經(jīng)完全排好序了 。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡介 交換排序 ?交換排序 的基本方法是 ， 兩兩比較待排序記錄的關(guān)鍵字值 ， 并交換那些不滿足順序要求的記錄對 ， 直到全部待排序記錄都已滿足順序要求時為止 。 即 R[i].key≥R[top1].key 且R[i].key≤R[top2].key時進(jìn)棧 1， 只須改變 top1的值為top1+1即可 。 二路插入排序舉例 二路插入排序舉例（續(xù)） 二路插入排序（續(xù)） ?在二路插入排序中 ， 記錄的移動次數(shù)約為 n2/8， 比直接插入排序減少移動次數(shù)約一半 。 由算法分析的乘法法則可知 ， 前面給出的兩個希爾排序算法 ，shellsorting和 shellsort的時間復(fù)雜度為 O(n(log2n)2)。 while(R[0].keyR[jd].key) {R[j] = R[jd]。i=(n+1)/2。 } /*shellsorting end*/ 希爾排序（續(xù)） ?需要說明的是 ， 算法中沒有調(diào)用直接插入排序算法insertsorting， 而是獨(dú)立設(shè)計直接插入排序的部分；這是因?yàn)橄柵判蛑芯嚯x為 d的倍數(shù)的記錄為一組 ， 組中成員記錄之間有間隔不連續(xù)不能直接調(diào)用的緣故 。i++) {j = i。 ?但也有人提出不同的 di選取方法 ， 如克努特 （ Knuth） 提出的方法是 d1=,di+1=(i=2， 3， 4 … )。 ?換句話說 ， 如果待排序文件能夠基本有序 ， 則文件中的大多數(shù)記錄都不需要進(jìn)行插入 （ 即后移 ） 操作 ， 整個排序的時間開銷就可以大大減少 。 直接插入排序的算法分析 (續(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)。i++) {R[0]=R[i]。 ?一開始 ， 第一個記錄是一個長度為 1的有序序列； ?從第二個記錄起 ， 每次用第 i(i=2， 3 … n)個記錄的關(guān)鍵字 Ki與前面有序序列中記錄的關(guān)鍵字 Ki Ki2 … K1進(jìn)行比較 ， 從而找到 Ki所在記錄應(yīng)該插入的位置并依次后移各記錄后插入之 ， 使得有序序列的長度加 1； ?這樣插入 n1次就會得到 n個記錄的有序序列 ， 從而完成整個文件的排序工作 。 ?內(nèi)部排序的時間代價主要用關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)來衡量； ?而外部排序的時間代價主要用訪問外存儲器的次數(shù)來衡量 。 排序的分類 ?根據(jù)排序過程中待排序文件存放的位置不同 ， 可以把排序分為 內(nèi)部 和 外部排序 兩大類 。 ?排序 （ sort） 是這樣一種操作 ， 它確定文件中 n個記錄的一種排列 （ Rj1， Rj2 … Rjn） ， 使得其相應(yīng)關(guān)鍵字滿足遞增 （ 即不減 ） 關(guān)系 Kj1≤Kj2≤… ≤Kjn或遞減 （ 即不增 ） 關(guān)系 Kj1≥Kj2≥… ≥Kjn。 ?又如為了方便檢索 ， 需要構(gòu)造二叉檢索樹 、 B樹和 B+樹等樹表 ， 構(gòu)造這些樹表的過程本身就是一個排序的過程 。 ?在現(xiàn)今的計算機(jī)系統(tǒng)中 ， 有相當(dāng)大的一部分 CPU時間開銷是用于對數(shù)據(jù)的排序整理上的 。 ?若關(guān)鍵字滿足遞增 （ 即不減 ） 關(guān)系時 ， 稱作按關(guān)鍵字 升序排序 (ascending sort)； ?若關(guān)鍵字滿足遞減 （ 即不增 ） 關(guān)系時 ， 稱作按關(guān)鍵字 降序排序 (descending sort)。 ?內(nèi)部排序 是指待排序文件放在內(nèi)存中進(jìn)行排序的排序；內(nèi)部排序 適用于 記錄個數(shù)不很多的較小待排序文件的排序； ?外部排序 是指在待排序文件很大時 ， 內(nèi)存中不能一次容納全部記錄 ， 還要借助于外存存放待排序文件 ， 在排序過程中需要對外存進(jìn)行訪問的排序；外部排序則 適用于 記錄個數(shù)太多不能一次全部放入內(nèi)存的較大待排序文件的排序 。 排序的基本概念（續(xù)） ?在本章主要討論內(nèi)部排序算法 ， 以記錄數(shù)組作為待排序文件的組織形式 ， 并假定關(guān)鍵字均為整數(shù) ，按遞增次序討論排序算法 （ 即討論升序排序問題 ） 。 直接插入排序 舉例 ?例如 ， 已知待排序文件中記錄的關(guān)鍵字序列為 （ 23，48， 32， 107， 86， 75， 68） ， 直接插入排序的過程可示意如下： ?其中 ， 方括號表示已排好序的序列 ， i表示插入第 i個記錄 。 j=i1。 直接插入排序的算法分析 (續(xù) ) ?若初始文件中各記錄是隨機(jī)排列 ， 即關(guān)鍵字的各種排列的出現(xiàn)概率相同時 ， 我們可取上述最好與最壞情況的平均值作為比較和移動的平均次數(shù) ， 約為 n2/4,由此可得直接插入排序的時間復(fù)雜度為 O(n2)。 ?另外 ， 當(dāng) n的值很小時 ， n2的值受 n的值的影響也不太大 ， 直接插入排序的效率也比較高 。 如何選取增量序列才能產(chǎn)生最好的排序效果 ， 至今仍無法從數(shù)學(xué)角度得出圓滿的結(jié)論；然而逐步縮小增量和最后一次增量為 1是大家不爭的事實(shí) 。 R[0] = R[j]。 ?另外 ， 在 for循環(huán)中的分組執(zhí)行直接插入排序的過程 ，是依次先插入 d個組中的第二個記錄 ， 再插入 d個組中的第三個記錄 …… 最后插入 d個組中的最后一個記錄；是 d個組的交替插入過程 ， 而不是一個組的直接插入排序完成后再進(jìn)行下一組 ， 這樣有利于算法設(shè)計的簡潔性和算法描述的方便性 。i++) R[i].key = maxint。 j = j – d。 插入排序 直接插入排序 希爾排序 其它插入排序簡介 ? 由第七章的討論我們知道 ， 對有序表采用二分法檢索 ， 檢索性能大大優(yōu)于順序檢索 。 它只能減少移動次數(shù)而不能絕對避免移動記錄 ， 若要大幅度降低移動次數(shù) ， 可改變存儲結(jié)構(gòu)為靜態(tài)鏈表 ， 進(jìn)行表插入排序 。 ?當(dāng) R[i].key[top1].key時 ， 由棧 1反復(fù)傳送記錄到棧 2，直到 R[i].key≥R[top1].key時將 R[i]插入棧 1。 ?本節(jié)介紹兩種交換排序的方法： ?一種是冒泡排序 ， ?一種是快速排序 。 ?為此 ， 需在算法中引入一個交換狀態(tài)變量 flag， 在每一趟排序之前置 flag為 0， 每次交換時給 flag加 1，若一趟結(jié)束時 flag為 0則終止算法 。j) if(R[j1].key R[j].key) {temp=R[j1]。 冒泡排序算法分析（續(xù)） ?上述的冒泡排序算法還可以作一些改進(jìn)來提高排序速度 ， 比如： ?在每趟排序中記住最后一次發(fā)生交換記錄的位置 K， 因?yàn)槲恢?K之前的記錄都已排好了序 ， 下一趟的排序可以終止于位置 K而不必進(jìn)行到預(yù)定的下界位置 i。 快速排序的算法描述 ?這種把一個待排序區(qū)間通過基準(zhǔn)記錄 （ 第一個記錄 ） 分割成為兩個區(qū)間的一次分割排序算法如下： int divideareasort(recordtype R[],int s,int t) {int i,j。 if(ij) {R[i]=R[j]。 R[i]=temp。 快速排序的算法舉例（續(xù)） 快速排序的算法舉例（續(xù)） 快速排序的算法舉例（續(xù)） 快速排序的算法分析 ?快速排序過程中各趟中所選擇的基準(zhǔn)可以用一棵二叉樹來表示 ， 如上例中的基準(zhǔn)二叉樹如右圖所示 。 ?快速排序算法是一種 不穩(wěn)定的排序 方法 。i=n1。 } } }