【文章內(nèi)容簡(jiǎn)介】 1… 2） 則交換兩個(gè)記錄 ， 直到全部記錄都比較和交換完畢 （ 即 j=2） ， 第一趟冒泡排序結(jié)束； ?此時(shí)最小關(guān)鍵字值的記錄上浮到了 R[1]的位置上 。 然后對(duì) n1個(gè)記錄重復(fù)類似的操作 ， 次小關(guān)鍵字值的記錄上浮到 R[2]的位置上 。 ?重復(fù)進(jìn)行這樣的過(guò)程 ， 直到?jīng)]有記錄需要交換為止 （ 最多需 n1趟冒泡排序 ） ， 整個(gè)待排序文件就按關(guān)鍵字值升序排列完畢 。 冒泡排序算法舉例 ?例如 ， 對(duì)于 8個(gè)記錄的關(guān)鍵字序列 （ 46， 26， 43， 18，74， 21, ,57） ， 冒泡排序的過(guò)程如下圖所示： 冒泡排序算法（續(xù)） ?由該冒泡排序的實(shí)例 ， 也證實(shí)了至多需要 n1趟冒泡排序即可完成整個(gè)排序 。 ?事實(shí)上存在不需要 n1趟就可以完全排好序的情況 ，如上例的第五趟排序后就已經(jīng)排好序了； ?其識(shí)別辦法是 ， 若某一趟冒泡排序過(guò)程中沒(méi)有進(jìn)行記錄的位置交換 ， 則說(shuō)明待排序文件已經(jīng)完全排好序了 。 ?為此 ， 需在算法中引入一個(gè)交換狀態(tài)變量 flag， 在每一趟排序之前置 flag為 0， 每次交換時(shí)給 flag加 1，若一趟結(jié)束時(shí) flag為 0則終止算法 。 冒泡排序的算法描述 void bubblesort(recordtype R[],int n) {int i,j,flag。 recordtype temp。 for(i=1。in1。i++) {flag = 0。 for(j = n。j = i+1。j) if(R[j1].key R[j].key) {temp=R[j1]。 R[j1]=R[j]。 R[j]=temp。 flag=flag+1。 } /*置已交換標(biāo)志 */ if(flag==0) break。 } } /*bubblesort end */ 冒泡排序算法分析 ?冒泡排序也是一種 穩(wěn)定的排序 方法 。 ?其時(shí)間復(fù)雜度可以如下分析： ?在最好的情況下 ， 是初始記錄的關(guān)鍵字已遞增有序時(shí) ，只需一趟排序 ， 比較次數(shù)為 n1， 沒(méi)有交換記錄即記錄的移動(dòng)次數(shù)為 0； ?在最壞的情況下 ， 是初始記錄遞減有序 （ 即逆序 ） 時(shí) ，需進(jìn)行 n1趟排序 ， 比較次數(shù)為 ， 交換次數(shù)為 ， 每次交換需三次移動(dòng)記錄 ， 其移動(dòng)次數(shù)為 。 ?在平均情況下 ， 關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)大約為最壞情況下的一半 ， 因此冒泡排序算法的時(shí)間復(fù)雜度為 O(n2)。 冒泡排序算法分析（續(xù)） ?上述的冒泡排序算法還可以作一些改進(jìn)來(lái)提高排序速度 ， 比如： ?在每趟排序中記住最后一次發(fā)生交換記錄的位置 K， 因?yàn)槲恢?K之前的記錄都已排好了序 ， 下一趟的排序可以終止于位置 K而不必進(jìn)行到預(yù)定的下界位置 i。 ?在排序過(guò)程中交替變化掃描比較的方向 ， 即前一趟由后向前掃描 ， 后一趟則由前向后掃描 ， 而不是一直都由后向前掃描 。 由后向前掃描比較交換一趟 ， 可使最輕的氣泡上浮到頂部 ， 但只能使最重的氣泡下沉一個(gè)位置；由前向后掃描比較交換一趟 ， 可使最重的氣泡下沉到底部 ， 但只能使最輕的氣泡上浮一個(gè)位置 。 交替變化掃描方向可以加速最輕和最重的氣泡向兩端迅速沉浮 ， 有利于加速排序過(guò)程 。 交換排序 冒泡排序 快速排序 快速排序 ?快速排序 （ quick sort） 也稱作分區(qū)交換排序 ， 是對(duì)冒泡排序的一種改進(jìn)排序方法 。 它是目前各種內(nèi)部排序方法中較快的方法 ， 故稱之為快速排序 。 ?快速排序的 基本思想 是： ?在待排序文件的 n個(gè)記錄中 ， 任取一個(gè)記錄 （ 通常是選取第一個(gè)記錄 ） 作為基準(zhǔn)； ?經(jīng)過(guò)一趟排序后以基準(zhǔn)記錄的關(guān)鍵字把全部記錄分為兩部分 ， 所有關(guān)鍵字值比基準(zhǔn)記錄關(guān)鍵字值小的記錄都排列在基準(zhǔn)記錄之前 ， 而所有關(guān)鍵字值比基準(zhǔn)記錄關(guān)鍵字值大的記錄都排列在基準(zhǔn)記錄之后； ?然后對(duì)基準(zhǔn)記錄前后的這兩個(gè)部分分別重復(fù)這樣的過(guò)程 ，得到本趟排序的兩個(gè)新到位的基準(zhǔn)和四個(gè)部分 …… 如此重復(fù)上述過(guò)程 ， 直到每一個(gè)部分只剩下一個(gè)記錄 （ 即全部到位 ） 時(shí)為止 。 快速排序算法 ?設(shè)兩個(gè)指示器變量 i和 j， 分別指向待排序區(qū)間的第一個(gè)記錄和最后一個(gè)記錄； ?先將第一個(gè)記錄移到暫存變量 temp中 ， 然后 j從區(qū)間的最后一個(gè)記錄起向前掃描 ， 直到找到滿足 R[j].key的記錄時(shí) ， 將 R[j]移入 R[i]中； ?再令 i 自 i+1 起 向 后 掃 描 ， 直 到 找 到 滿 足R[i].key ， 將 R[i]移入 R[j]中； ?就這樣 j自 j1從后向前掃描一次移入一個(gè) R[j]于 R[i]中 ，i自 i+1從前向后掃描一次移入一個(gè) R[i]于 R[j]中 ， 反復(fù)交替的掃描和移動(dòng)記錄； ?直到 i=j時(shí)把 temp移入 R[i]中 （ 區(qū)間中第一個(gè)記錄應(yīng)在的位置 ） ， 它把整個(gè)待排序區(qū)間分割為相互獨(dú)立的兩個(gè)更小的區(qū)間 。 快速排序的算法描述 ?這種把一個(gè)待排序區(qū)間通過(guò)基準(zhǔn)記錄 （ 第一個(gè)記錄 ） 分割成為兩個(gè)區(qū)間的一次分割排序算法如下： int divideareasort(recordtype R[],int s,int t) {int i,j。 recordtype temp。 i=s。 j=t。 temp=R[s]。 do {while((R[j].key=)amp。amp。(ij)) j。 if(ij) {R[i]=R[j]。 i++。} 快速排序的算法描述（續(xù)） while((R[i].key=)amp。amp。(ij)) i++。 if(ij) {R[j]=R[i]。 j。 } }while(ij)。 R[i]=temp。 return i。 } /*divideareasort end*/ 快速排序的算法描述（續(xù)） ? 對(duì)于待排序文件 R[]利用一次分割區(qū)間排序算法時(shí) ， 令 s=1和 t=n即可完成第一趟排序；由此得到的兩個(gè)更小的區(qū)間R[1… i1]和 R[i+1… n]， 繼續(xù)利用算法 divideareasort分割為更小的四個(gè)區(qū)間；如此一直進(jìn)行下去 ， 直到都分割為只有一個(gè)記錄時(shí)排序結(jié)束 。 調(diào)用 divideareasort對(duì) R[ ]進(jìn)行快速排序的遞歸算法可描述如下： void quicksort(recordtype R[],int s,int t) {int i。 if(st) {i=divideareasort(R,s,t)。 quicksort(R,s,i1)。 quicksort(R,i+1,t)。 } } /*quicksort end*/ 快速排序的算法舉例 ?下面我們使用快速排序算法對(duì)關(guān)鍵字序列 （ 36， 73， 65，97， 13， 27， ， 29） 排序 ， 在下面的排序過(guò)程示例中 ，先給出第一趟中的區(qū)間分割的整個(gè)過(guò)程 ， 然后給出各趟的排序結(jié)果；用方括號(hào)表示區(qū)間 ， 用方框表示暫存變量 temp的關(guān)鍵字值 （ 并未參加交換 ， 在分割完成后才放入最終位置上 ） 。 快速排序的算法舉例（續(xù)） 快速排序的算法舉例（續(xù)） 快速排序的算法舉例（續(xù)） 快速排序的算法分析 ?快速排序過(guò)程中各趟中所選擇的基準(zhǔn)可以用一棵二叉樹(shù)來(lái)表示 ， 如上例中的基準(zhǔn)二叉樹(shù)如右圖所示 。 基準(zhǔn)二叉樹(shù)反映了快速排序的遞歸調(diào)用過(guò)程 ， 也便于我們對(duì)快速排序算法進(jìn)行性能分析 。 ?快速排序的基準(zhǔn)二叉樹(shù)是關(guān)鍵字的一棵二叉檢索樹(shù) ， 其中序遍歷序列就是關(guān)鍵字的升序排列 。 ?在 最好的情況 下 ， 基準(zhǔn)二叉樹(shù)是一棵理想的平衡二叉檢索樹(shù) ， 深度為 ， 遞歸所需棧的存儲(chǔ)開(kāi)銷為 O(log2n)，時(shí)間開(kāi)銷為結(jié)點(diǎn)數(shù)乘平均檢索長(zhǎng)度 ， 即 O(n?log2n)。 快速排序的算法分析（續(xù)） ?在 最壞情況 下 ， 基準(zhǔn)二叉樹(shù)是一棵單枝二叉檢索樹(shù) ， 深度為 n， 存儲(chǔ)開(kāi)銷為 O(n)， 時(shí)間開(kāi)銷為 O(n2)。 ?在 平均情況 下 ， 基準(zhǔn)二叉樹(shù)是一棵隨機(jī)的二叉檢索樹(shù) ， 由于二叉檢索樹(shù)的平均檢索長(zhǎng)度為 O(log2n)， 故時(shí)間開(kāi)銷也是O(n?log2n)。 ?為了避免初始關(guān)鍵字序列有序或基本有序時(shí)快速排序蛻化為冒泡排序 （ 即基準(zhǔn)二叉樹(shù)為單枝或近似單枝二叉樹(shù) ） 的情況 ， 通常采取 “ 三者取中 ” 的基準(zhǔn)記錄選取辦法改進(jìn)之 。 ?所謂三者取中是指在 R[s]、 R[t]和 R[(s+t)/2]三者中選取關(guān)鍵字值居中的記錄作為分割區(qū)間的基準(zhǔn) ， 這種選取基準(zhǔn)記錄的方法可以大大改善快速排序在最壞情況下的性能 。 ?快速排序算法是一種 不穩(wěn)定的排序 方法 。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡(jiǎn)介 選擇排序 ?選擇排序的基本方法 是 ， 每次從待排序文件的各個(gè)記錄中 ， 依次選出關(guān)鍵字值最小的記錄放在已排好序的序列中 ， 直到選完為止 。 ?本節(jié)介紹： ?直接選擇排序 ?樹(shù)型選擇排序 ?堆排序 。 選擇排序 直接選擇排序 樹(shù)形選擇排序 堆排序 直接選擇排序 ?直接選擇排序 （ direct selection sort） 也稱作簡(jiǎn)單選擇排序 。 ?其 具體做法 是： ?對(duì)于待排序文件 R[1..n]， 通過(guò)比較首先選出關(guān)鍵字值最小的記錄與 R[1]交換 ， ?然后在其余記錄中選出次小關(guān)鍵字的記錄與R[2]交換 …… ?如此進(jìn)行 n1次的選擇與交換 ， R[1..n]中所有記錄就按關(guān)鍵字升序次序排列完畢 。 直接選擇排序舉例 ? 直接選擇排序的過(guò)程可示例如下： 直接選擇排序舉例（續(xù)） 直接選擇排序的算法描述 ? 直接選擇排序的算法可描述如下： void selectsort(recordtype R[],int n) {int i,j,m。 recordtype temp。 for(i=1。i=n1。i++) {m=i。 for(j=i+1。i=n。j++) if(R[j].keyR[m].key) m=j。 if(m!=i) {temp=R[i]。 R[i]=R[m]。 R[m]=temp。 } } } /*selectsort end*/ 直接選擇排序的算法分析 ?直接選擇排序只需要一個(gè)記錄大小的輔助存儲(chǔ)空間用于記錄交換 ， 其空間復(fù)雜度為 O(1)。 ?在排序過(guò)程中至多進(jìn)行 n1趟排序 ， 即至多交換記錄 n1次 ，做 3(n1)次記錄移動(dòng)；然而不論初始狀態(tài)如何 ， 在每一趟中都需要和所有記錄的關(guān)鍵字進(jìn)行比較； ?為了選出第 i趟的最小關(guān)鍵字 ， 需要的比較次數(shù)為 ni， 總的比較次數(shù)為 。 由此得到直接選擇排序的時(shí)間復(fù)雜度為 O(n2)。 ? 由于在直接選擇排序中存在著任意位置上的記錄互換的可能性 ， 所以有可能改變具有相同關(guān)鍵字值的記錄的相對(duì)位置次序 ， 如 （ 5, ,2） 的直接選擇排序結(jié)果為 （ 2, ,5） ； ?因此直接選擇排序方法是 不穩(wěn)定的 。 選擇排序 直接選擇排序 樹(shù)形選擇排序 堆排序 樹(shù)形選擇排序 ?樹(shù)形選擇排序 （ tree selection sort） 也稱作 錦標(biāo)賽排序 （ tournament sort） ， 這種排序方法是按照錦標(biāo)賽的思路進(jìn)行的 。 ?錦標(biāo)賽是將 n個(gè)參賽選手兩兩之間進(jìn)行比賽 （ 余下的一個(gè)輪空直接進(jìn)入下一輪比賽 ） ， 勝出者再兩兩之間比賽 ， 經(jīng)過(guò) 輪比賽后產(chǎn)生出第一名 。 ?樹(shù)形選擇排序 是將待排序的 n個(gè)記錄的關(guān)鍵字作為完全二叉樹(shù)的葉子結(jié)點(diǎn) ， 依次兩兩之間比較 ， 關(guān)鍵字值小者作為其雙親結(jié)點(diǎn) ， 最后若余下一個(gè)則輪空參加下一輪比較；然后對(duì)得到的這些雙親結(jié)點(diǎn)再兩兩之間比較產(chǎn)生其