《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序（10頁珍藏版）》請(qǐng)?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)鍵值相同的記錄，排序前后的相對(duì)次序不變。
排序前
排序后
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)位置的方法：加大步長(zhǎng)。
僅僅加大步長(zhǎng)的值，可行嗎？
縮小增量法：最后一次的步長(zhǎng)一定為1。
希爾排序：將記錄序列按某個(gè)步長(zhǎng)分成若干子序列；分別對(duì)各子序列排序。
步長(zhǎng)的取值方法之一：n/2,n/4,……,8,4,2,1。
初始
5
6
5、1
7
4
8
3
2
9
第1趟
步長(zhǎng)=4
4
6
1
2
5
8
3
7
9
第2趟
步長(zhǎng)=2
1
2
3
6
4
7
5
8
9
第3趟
步長(zhǎng)=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é)果有差異。
最糟情形：針對(duì)基本有序序列的排序。
試題：一組記錄的關(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
數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序
