《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序（10頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第9章 內(nèi)部排序 排序：調(diào)整記錄表中記錄次序，使之按關(guān)鍵值有序(增序)。 記錄表結(jié)構(gòu)：SeqList類 內(nèi)部排序 記錄集全部在內(nèi)存中（戰(zhàn)術(shù)問題） 外部排序 記錄集部分在內(nèi)存中，排序過程中，需訪問外存（戰(zhàn)略問題） 穩(wěn)定性：關(guān)鍵值相同的記錄，排序前后的相對次序不變。 排序前 排序后 5 1 4 3 4 1 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)鍵值大小插入到有序子

2、序列中。 初始化時(shí)，有序子序列只有一個(gè)記錄； n-1趟后，有序子序列有n個(gè)記錄。 初始 21 25 49 25* 8 16 第1趟 21 25 49 25* 8 16 第2趟 21 25 49 25* 8 16 第3趟 21 25 25* 49 8 16 第4趟 8 21 25 25* 49 16 第5趟 8 16 21 25 25* 49 1.1.2 算法實(shí)現(xiàn) //直接插入排序 template void SeqList::InsertSort() { int n=

3、m_Data.size(); for(int i=1; i=0 && m_Data[j]>tmp; j--) m_Data[j+1]=m_Data[j]; // 記錄移1位 m_Data[j+1]=tmp; } } 1.1.3 性能分析 屬于穩(wěn)定排序。時(shí)間復(fù)雜度是O(n2)。 KCN：關(guān)鍵值比較次數(shù) RMN：記錄移動(dòng)次數(shù) 比較 移動(dòng) 最好 情況 記錄集有序 1次/趟=>KCN=n-1 2次/趟

4、=>RMN=2(n-1) 最壞 情況 記錄集逆序 i次/趟 =>KCN=n(n-1)/2 i+2次/趟 =>RMN=(n+4)(n-1)/2 1.2 希爾排序 發(fā)明人：D.L.Shell，發(fā)明于1959年。 1.2.1 算法思路與步驟 直接插入排序的缺點(diǎn)：每個(gè)記錄被一步一步地挪到目標(biāo)位置。 將記錄較快地挪到目標(biāo)位置的方法：加大步長。 僅僅加大步長的值，可行嗎？ 縮小增量法：最后一次的步長一定為1。 希爾排序：將記錄序列按某個(gè)步長分成若干子序列；分別對各子序列排序。 步長的取值方法之一：n/2,n/4,……,8,4,2,1。 初始 5 6

5、1 7 4 8 3 2 9 第1趟 步長=4 4 6 1 2 5 8 3 7 9 第2趟 步長=2 1 2 3 6 4 7 5 8 9 第3趟 步長=1 1 2 3 4 5 6 7 8 9 1.2.2 算法實(shí)現(xiàn) template void SeqList::ShellSort() { int n=m_Data.size(); for(int step=n/2; step>0; step=step/2) { for(int i=step; i

6、T tmp=m_Data[i]; for(int j=i-step; j>=0 && m_Data[j]>tmp; j=j-step) m_Data[j+step] = m_Data[j]; // 記錄移step位 m_Data[j+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 算法思路與步驟

7、 每趟：在剩余序列中找到最小值，將之交換到目標(biāo)位置。 n-1趟選出n-1個(gè)極值，置于相應(yīng)目標(biāo)位置。 初始 5 6 1 7 4 8 3 2 9 第1趟 1 6 5 7 4 8 3 2 9 第2趟 1 2 5 7 4 8 3 6 9 3.1.2 算法實(shí)現(xiàn) template void SeqList::SelectSort() { int n=m_Data.size(); for(int i=0; i

8、=i+1; j

9、選擇排序 初始 5 6 3 1 4 第1趟 1 6 3 5 4 例：基于靜態(tài)鏈表的直接選擇排序 下標(biāo) 0 1 2 3 4 5 初始 5 6 3 1 4 1 2 3 4 5 -1 第1趟 5 6 3 1 4 4 5 3 1 2 -1 第4趟 5 6 3 1 4 4 2 -1 5 3 1 3.2 樹排序 3.2.1 算法思路 減少比較次數(shù)的方法：錦標(biāo)賽的賽制。 選出冠軍的過程：（比較次數(shù)=n-1） 選出亞軍的方法：將冠軍值改為∞。（比較次數(shù)=lo

10、g2n） 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

11、調(diào)整！ 初始情形 調(diào)整結(jié)點(diǎn)(i=3) 3,4,5,1,6,8,2,7 3,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,7 3,1,2,4,6,8,5,7 調(diào)整結(jié)點(diǎn)(i=0) 1,3,2,4,6,8,5,7 3.3.3 堆排序方法 堆排序是n-1次交換、調(diào)整結(jié)點(diǎn)的過程。 第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,

12、(2,1) 3.3.4 堆排序的實(shí)現(xiàn) template void SeqList::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_Data[0]; m_Data[0]=m_Data[i]; m_Data[i]=tmp; HeapShift(0,i-1); } } // 調(diào)整范圍：m_Data[root]……m_Data[bot

13、tom] template void SeqList::HeapShift(int root,int bottom) { T tmp=m_Data[root]; int ch_i=2*root+1; while(ch_i<=bottom) { if(ch_i+1<=bottom && m_Data[ch_i]>m_Data[ch_i+1]) ch_i++; // ch_i是左右孩子中較小者的下標(biāo) if(m_Data[ch_i] >= tmp) break; m_Data[root] = m_Data[ch

14、_i]; root=ch_i; ch_i=2*root+1; } m_Data[root]=tmp; } 3.3.5 性能分析 時(shí)間復(fù)雜度： O(nlog2n) 其中：建堆O(n)，每次調(diào)整O(log2n) 空間復(fù)雜度： O(1) 穩(wěn)定性：不穩(wěn)定排序。示例： 2個(gè)3最初的位置，誰先誰后？ 直觀的經(jīng)驗(yàn)：比賽分組不同，結(jié)果有差異。 最糟情形：針對基本有序序列的排序。 試題：一組記錄的關(guān)鍵值為(4,7,5,2,3,8)，利用堆排序算法建立的初始堆為 C 。 A、2,4,5,7,3,8 B、4,2,5,7,3,8 C、2,3,5,7,4,8 D、8,3,5,7,4,2