數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第9章 排序

第9章 內(nèi)部排序排序：調(diào)整記錄表中記錄次序，使之按關(guān)鍵值有序(增序)。記錄表結(jié)構(gòu)：SeqList類內(nèi)部排序記錄集全部在內(nèi)存中（戰(zhàn)術(shù)問題）外部排序記錄集部分在內(nèi)存中，排序過(guò)程中，需訪問外存（戰(zhàn)略問題） 穩(wěn)定性：關(guān)鍵值相同的記錄，排序前后的相對(duì)次序不變。排序前排序后5 1 4 3 41 3 4 4 5穩(wěn)定排序1 3 4 4 5不穩(wěn)定排序 1 插入排序 思路：起源于數(shù)據(jù)陸續(xù)達(dá)到的思路，摸牌的行為。1.1 直接插入1.1.1 算法思路與步驟設(shè)已存在一個(gè)有序子序列；每趟將一個(gè)記錄按關(guān)鍵值大小插入到有序子序列中。初始化時(shí)，有序子序列只有一個(gè)記錄；n-1趟后，有序子序列有n個(gè)記錄。初始21254925*816第1趟21254925*816第2趟21254925*816第3趟212525*49816第4趟8212525*4916第5趟816212525*491.1.2 算法實(shí)現(xiàn)/直接插入排序template<class T> void SeqList<T>:InsertSort() int n=m_Data.size(); for(int i=1; i<n; i+) T tmp=m_Datai; for(int j=i-1; j>=0 && m_Dataj>tmp; j-) m_Dataj+1=m_Dataj; / 記錄移1位 m_Dataj+1=tmp; 1.1.3 性能分析 屬于穩(wěn)定排序。時(shí)間復(fù)雜度是O(n2)。 KCN：關(guān)鍵值比較次數(shù) RMN：記錄移動(dòng)次數(shù)比較移動(dòng)最好情況記錄集有序1次/趟=>KCN=n-12次/趟=>RMN=2(n-1)最壞情況記錄集逆序i次/趟=>KCN=n(n-1)/2i+2次/趟=>RMN=(n+4)(n-1)/21.2 希爾排序發(fā)明人：D.L.Shell，發(fā)明于1959年。1.2.1 算法思路與步驟直接插入排序的缺點(diǎn)：每個(gè)記錄被一步一步地挪到目標(biāo)位置。將記錄較快地挪到目標(biāo)位置的方法：加大步長(zhǎng)。僅僅加大步長(zhǎng)的值，可行嗎？縮小增量法：最后一次的步長(zhǎng)一定為1。 希爾排序：將記錄序列按某個(gè)步長(zhǎng)分成若干子序列；分別對(duì)各子序列排序。步長(zhǎng)的取值方法之一：n/2,n/4,8,4,2,1。初始561748329第1趟步長(zhǎng)=4461258379第2趟步長(zhǎng)=2123647589第3趟步長(zhǎng)=11234567891.2.2 算法實(shí)現(xiàn)template<class T> void SeqList<T>:ShellSort() int n=m_Data.size(); for(int step=n/2; step>0; step=step/2) for(int i=step; i<n; i+) T tmp=m_Datai; for(int j=i-step; j>=0 && m_Dataj>tmp; j=j-step) m_Dataj+step = m_Dataj; / 記錄移step位 m_Dataj+step=tmp; 1.2.3性能分析 屬于不穩(wěn)定排序。(各子序列彼此獨(dú)立的交換) 時(shí)間復(fù)雜度：O(n1.5)O(n1.3)。第9章 內(nèi)部排序3 選擇排序思路：“比較”比“賦值”速度快得多3.1 直接選擇排序3.1.1 算法思路與步驟 每趟：在剩余序列中找到最小值，將之交換到目標(biāo)位置。 n-1趟選出n-1個(gè)極值，置于相應(yīng)目標(biāo)位置。初始561748329第1趟165748329第2趟1257483693.1.2 算法實(shí)現(xiàn)template<class T> void SeqList<T>:SelectSort() int n=m_Data.size(); for(int i=0; i<n-1; i+) int min_i=i; for(int j=i+1; j<n; j+) if(m_Dataj<m_Datamin_i) min_i=j; if(i!=min_i) T tmp=m_Datai; m_Datai=m_Datamin_i; m_Datamin_i=tmp; 3.1.3 性能分析 時(shí)間復(fù)雜度：O(n2) 空間復(fù)雜度：O(1) 穩(wěn)定性：不穩(wěn)定。示例：排序前3 4 5 3 1 一趟后1 4 5 3 33.1.4 擴(kuò)展思考 減少移動(dòng)記錄的方法：采用靜態(tài)鏈表結(jié)構(gòu)。 示例：普通的直接選擇排序 初始56314第1趟16354 例：基于靜態(tài)鏈表的直接選擇排序 下標(biāo)012345初始5631412345-1第1趟5631445312-1第4趟5631442-15313.2 樹排序3.2.1 算法思路減少比較次數(shù)的方法：錦標(biāo)賽的賽制。選出冠軍的過(guò)程：（比較次數(shù)=n-1）選出亞軍的方法：將冠軍值改為。（比較次數(shù)=log2n）3.2.2 性能分析時(shí)間復(fù)雜度： O(nlog2n)空間復(fù)雜度： O(n)3.3 堆排序3.3.1 堆的定義60年代Williams首先提出堆排序算法。 有n個(gè)記錄的序列,其關(guān)鍵值序列為(K0,K1,Kn-1) 若2i+1<n，則有Ki<=K2i+1 若2i+2<n，則有Ki<=K2i+2本質(zhì)：將序列當(dāng)作完全二叉樹的順序存儲(chǔ)形式。 每個(gè)分支結(jié)點(diǎn)的關(guān)鍵值 <= 其左右孩子結(jié)點(diǎn)的關(guān)鍵值稱為小根堆。3.3.2 建堆方法 建堆是一個(gè)依次調(diào)整結(jié)點(diǎn)的過(guò)程。 從簡(jiǎn)單的事做起：從最后一個(gè)分支結(jié)點(diǎn)開始調(diào)整！初始情形調(diào)整結(jié)點(diǎn)(i=3)3,4,5,1,6,8,2,73,4,5,1,6,8,2,7調(diào)整結(jié)點(diǎn)(i=2)調(diào)整結(jié)點(diǎn)(i=1)3,4,2,1,6,8,5,73,1,2,4,6,8,5,7調(diào)整結(jié)點(diǎn)(i=0)1,3,2,4,6,8,5,73.3.3 堆排序方法 堆排序是n-1次交換、調(diào)整結(jié)點(diǎn)的過(guò)程。 第1次交換第1次調(diào)整7,3,2,4,6,8,5,(1)2,3,5,4,6,8,7,(1)第2次交換第2次調(diào)整7,3,5,4,6,8,(2,1)3,4,5,7,6,8,(2,1)3.3.4 堆排序的實(shí)現(xiàn)template<class T> void SeqList<T>:HeapSort() int n=m_Data.size(); for(int i=n/2-1; i>=0; i-) HeapShift(i,n-1); for(i=n-1; i>0; i-) T tmp=m_Data0; m_Data0=m_Datai; m_Datai=tmp; HeapShift(0,i-1); / 調(diào)整范圍：m_Datarootm_Databottomtemplate<class T> void SeqList<T>:HeapShift(int root,int bottom) T tmp=m_Dataroot; int ch_i=2*root+1; while(ch_i<=bottom) if(ch_i+1<=bottom && m_Datach_i>m_Datach_i+1) ch_i+; / ch_i是左右孩子中較小者的下標(biāo) if(m_Datach_i >= tmp) break; m_Dataroot = m_Datach_i; root=ch_i; ch_i=2*root+1; m_Dataroot=tmp;3.3.5 性能分析時(shí)間復(fù)雜度： O(nlog2n) 其中：建堆O(n)，每次調(diào)整O(log2n)空間復(fù)雜度： O(1) 穩(wěn)定性：不穩(wěn)定排序。示例：2個(gè)3最初的位置，誰(shuí)先誰(shuí)后？ 直觀的經(jīng)驗(yàn)：比賽分組不同，結(jié)果有差異。 最糟情形：針對(duì)基本有序序列的排序。試題：一組記錄的關(guān)鍵值為(4,7,5,2,3,8)，利用堆排序算法建立的初始堆為 C 。 A、2,4,5,7,3,8B、4,2,5,7,3,8 C、2,3,5,7,4,8D、8,3,5,7,4,2