---
tags: 資料結構
---
# 資料結構 第七章 排序

## 一、搜尋與驗證
討論影響排序因素，搜尋資料可能可以分成有序資料及亂序，可以分成內部(記憶體)搜尋或是外部(硬碟)搜尋...等等。
### (一)有序搜尋
#### 1、討論時間複雜度
如果有N筆資料，使用(環狀鏈結)搜尋失敗時則link+1指向下一個位置，直到搜尋成功為止，時間複雜度分析為:若在第1個link找到資料所花時間為(1)+若在第2個link找到資料所花時間為(2)+...+若在第n個link找到資料所花時間為(n)【分攤時間】=(1+2+...+n)/n = ((1+n)*n)/2/n = O(N)
#### 2、程式碼:
int seqsearch(int list[], int searchnum, int n)
{
int i;
list[n] = searchnum;
for(i = 0; list[i] != searchnum; i++);
return((i<n) ? i : -1);
}
### (二)二元搜尋
#### 1、討論:
二元搜尋結構為，搜尋值與目前節點值做比較。
搜尋值=節點值，直接列印樹根
搜尋值>節點值，向樹根的右子樹遞迴搜尋
搜尋值<節點值，向樹根的左子樹遞迴搜尋
#### 2、程式碼:
int binsearch(element list[],int searchnum,int n)
{
int left =0, right = n-1, middle;
while (left<=right)
{
middle = (left+right)/2;
switch(compare(list[middle].key,searchnum))
{
case -1: left = middle +1;
break;
case 0: return middle;
case 1: right = middle-1;
}
}
return -1;
}
### (三)列表驗證
我們驗證2個列表是否相同
【討論2個列表不同時會有的狀況】
1.列表1的元素列表2沒有
2.列表2的元素列表1沒有
3.列表1&2元素一樣但順序不同
#### 1、時間複雜度討論
##### (1)在非有序列表中
##### 【worst case】【假設列表~1~元素為m個，列表~2~元素為n個】

列表1的每個單獨元素，皆與列表2的所有元素做比較，故時間複雜度為O(mn)

##### (2)改善
先將２個列表有序排列後，在做比較。
討論時間複雜度為Ｏ（sort(m)+sort(n)+O(n)+O(m)）
sort(m):為列表1排列所需時間
sort(n):為列表2排列所需時間
排列完成後因2個列表已完成排列(已知每個index內的資料)
列表1比較次數最多為m次
列表1比較次數最多為n次
比較時間複雜度遠小於排序時間
故時間複雜度則改善為O(max(mlogm,nlogn))
##### (3)程式碼

#### 2、特性
##### (1)內部排序、外部排序
內部排序應用在列表size較小時(在記憶體中)，排序速度較快(但容量小)，外部排序則是列表size較大無法直接在(記憶體中排序)，使用硬碟(disk)速度較慢(但容量大)。
##### (2)穩態(stable)、非穩態(unstable)
穩態:排序的過程每次的交換不影響已排序完成的列表。
非穩態:排序的過程每次交換可能會影響排序完成中元素的順序。
## 二、插入排序
分成2個集合(已排序、非排序)
step1:每回合從非排序中取一數至已排序集合中(做排序)
step2:直到非排序集合已空，則完成排序
### (一)圖示:
#### 【粗體為已排序集合、非粗體為非排序集合】
### (二)時間複雜度:
每一回合插入一個數做排序，最壞情況(每次插入的數皆為做小)故原先的資料皆向右移動1格(共移動N-1次)
假設N筆資料做排序(n回合)，時間複雜度則為O(n(n-1))= O(n^2-N) = O(n)
### (三)變化
#### 1、二元插入排序:
若使用二元搜尋方式插入，則可以減少比較次數(約為樹高O(logn))
#### 2、列表插入排序
使用link list的插入特性，因為不是array故不需要搬動資料的時間。
## 三、快速排序
選擇一個數當pivot點，插入列表中。
pivot左側的數皆比pivot值小
pivot右側的數皆比pivot值大
每回合執行約莫O(logn)，假設n筆資料(n回合)
時間複雜度約為O(nlogn)
### (一)時間複雜度:
時間複雜度約為O(nlogn)
#### 【worst case】
1、假設此列表為由小到大(pivot皆為列表第1數)，則每回合的比較，都需要比較n-1次(但無搬動)
n筆資料(n回合)故時間複雜度為O(n^2)。

2、或是列表為由大到小(pivot皆為列表第1數)，則每回合每筆資料皆向右1格(合計n-1次)
n筆資料(n回合)故時間複雜度為O(n^2)。

### (二)程式碼:

## 四、最佳排序時間:
### (1)圖示
### (2)決策樹
使用決策樹來分析排序時間複雜度最快可以多快。
(1)決策樹(每次都可以分成yes或no)2個分支，故為二元樹形態。
(root則為左右兒子的比較)
(左右兒子為root的比較結果)
(2)葉節點(leaf):則為整顆樹的比較結果，若有n筆資料做排序，總結果會有n!種。
(3)結合上述2點討論二元樹型態葉節點樹為n!個，n! = 2^(h-1) 【第五章樹公式】，那此樹高為log n! +1 【比較次數為樹高-1】故時間複雜度為 Ω(nlogn)【此討論n!個葉節點最矮樹高，所以其他不同二元樹樹高必定高於 nlogn 故使用 Ω 】

## 五、合併排序
### (一)合併
1、將兩個list合併: list[i],...,list[m] & list[m+1],...,list[n]
將兩個串列合併時間複雜度為O(n-i+1)【想像成合併完的長度，然後將資料一格一格放入O(1)，共n-i+1格】
---
2、程式碼
void merge(element list[], element sorted[], int i, int m,int n)
{
int j, k, t;
j = m+1;
k = i;
while(i <= m && j <= n)
{
if(list[i].key <= list[j].key)
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if ( i>m )
for(t = j; t<=n; t++)
sorted[k+t-j] = list[t];
else
for(t=i; t <=m; t++)
sorted[k+t-i] = list[t];
}

### (二)迭代合併
#### (1)方法:
若有n筆資料，將每個列表長度設為為1(n個列表)，每回合Merge合併(若n為奇數,則會有⌊n/2⌋個(長度為2)+1個(長度為1))，將2個列表長度為1的列表做合併(成為長度為2的長度列表)，合併直到長度為n的列表為完成。
#### (2)圖示:

#### (3)時間複雜度:
為一個倒立樹的型態，n筆資料為n個葉節點，故樹高為 h = ⌈logn⌉ +1
樹高為合併的回和數，每次合併都需要Scan所有資料O(n)，時間複雜度為 n*logn = O(nlogn)
### (三)遞迴合併
#### (1)方法:
若有n筆資料，將每個列表長度設為為1(n個列表)，另設定兩個指標(righ,left)，每次選取(righ+left)/2 【index】分割列表，直到遞迴至剩2個集合為止再做合併，合併至長度為n的列表為完成。
#### (2)圖示:

#### (3)程式碼:
int rmerge(element list[], int lower, int upper)
{
int middle;
if(lower<=upper)
return lower;
else
{
middle = (lower+upper)/2;
return listmerge(list,rmerge(list,lower,middle),rmerge(list,middle+1,upper));
}
}
## 六、堆積排序
雖然合併排序最壞時間複雜度也是O(nlogn)，但需要而外的空間，故討論堆積排序。
### 1、時間複雜度討論
堆積樹插入與刪除時間複雜度均為O(logn)
step1:先用bottom-up方式建立樹 = O(n)
step2:再使用adjust方式調整排序 = O(logn)
將最後一個點與樹根交換再透過adjust 調整為堆積樹特性。
執行(n-1)回合即完成。
總時間複雜度為(n-1)*logn = O(nlogn)
### 2、程式碼:
void adjust (element list[], int root, int n)
{
int child,rootkey;
element temp;
temp = list[root];
rootkey = list[root].key;
child = 2*root;
while (child <= n)
{
if((child <=n) && (list[child].key < list[child+1].key))
chikld++;
if (rootket > list[child].key)
break;
else
{
list[child/2] = list[child];
child *=2;
}
}
list[child/2] = temp;
}

## 七、基數排序
又稱分布式計數排序、桶子排序、高位元基數排序、低位元基數排序、線性排序。
### (一)課本範例圖示:
以花色為高位元
以數字為低位元
經過高位元排序和低位元排序後，則可以排出下圖順序
#### 1、從最高有效位元至最低(Most Significant Digit)
##### 圖示:
以花色(四種不同花色)做比較故最右側皆為黑桃，左側皆為梅花

#### 2、從最低有效位元至最高(Least Significant Digit)
##### 圖示:
以數字(13種不同數字)做比較故最右側為Ace，最左側為2。
#### 3、範例圖示(以LSD為例):
以下為個位數排序後結果，使用排序後結果再為十位數做排序，再使用十位數排序結果，去做百位數排序，將得到由小到大的排序數列
#### 4、時間複雜度
分派花O(n)+合併花O(r)=每一回合花O(n+r)
總花費 O(d(回合數)*(n+r))
#### 5、程式碼【LSD radix sort】
list_pointer radix_sort(list_pointer ptr)
{
list_pointer front[RADIX_SIZE], rear[RADIX_SIZE];
int i, j, digit;
for(i=MAX_DIGIT-1; i>=0; i++)
{
for (j = 0; j < RADIX_SIZE; j++ )
front[j] = rear[j] = NULL;
while (ptr)
{
digit = ptr->key[i];
if(!front[digit])
front[digit] = ptr;
else
rear[digit]->link = ptr;
rear[digit] = ptr;
ptr = ptr->link;
}
ptr = NULL;
for(j=RADIX_SIZE-1; j>=0; j--)
if(front[j])
{
rear[j] -> link = ptr;
ptr=front[j];
}

}
return ptr;
}

## 八、列表與表格排序
### (一)sort 1
使用link list來排序，因為link list只需要改變鏈結，不需要搬動資料，故可以節省原本搬動的時間。
step1:將single linklist 改成 Double linklist O(n)
step2:將鏈結值與後面連結相比找出最小值並交換共執行(n-1)回合
如果鏈結內的資料為m個 那交換一次最多需要O(3m) =O(m)
(排序=插入)【鏈結1(m筆)+鏈結2(m筆)+鏈結1元素至鏈結2】
O(n+(n-1)*m)，時間複雜度為O(mn)
#### 1、single linklist 改成 Double linklist

#### 2、課本範例圖解:

#### 3、程式碼

### (二)sort 2
#### 1、遞迴合併(不用改成雙鏈結)
#### 2、課本範例圖解:
i從0開始找到後面最小值做交換，並將最小值位置連結給程原本的位置
#### 3、程式碼

### (三) Table sort

#### 1、方法
step1:分成2個cycle，利用i是否與link相同，區分2個cycle集合
step2:再對i與link不同的這cycle，觀察link連至哪再找出不同的cycle
step3:重複step2直到所有i與link一至即排序結束

#### 2、課本範例圖解:

#### 3、程式碼

## 九、內部排序
### (一)特性
1、沒有最好的排序法，比如當資料量(n)少的時候有部分排序，此時插入排序法效果最佳。
2、合併排序法最佳及最差時間花費一樣，比堆積排序效能好，不過需要額外準備多餘空間。
3、快速排序平均效果最好，但它有最壞情況(正及反序)時間會是O(N^2)
4、基數排序為線性排序，但當資料量(n)大時時間複雜度也會隨之增加
### (二)圖示
1、當n<20為插入排序法最佳
2、其餘為快速排序法最佳
3、當n較大時為合併排序法最佳

### 程式碼
371

## 十、外部排序
### (一)源由
1、若資料量太大，無法一次搬至記憶體做排序的話(無法使用內部排序)，則選擇直接在硬碟實施排序。
但硬碟讀取時間遠低於記憶體
2、硬碟主要時間如下
(1)磁頭移動時間(Seek time): 磁頭需移動到正確軌道
(2)延遲時間(Latency time): 磁頭移動到正確位置讀取所需時間
(3)轉換時間(Transmission time): 將資料從硬碟轉換出來的時間，或是將資料存入硬碟的時間。

### (二)方法
1、外部排序較常使用合併排序法
2、因硬碟一次讀取以block為單位
3、block內資料使用內部排序，再將所有的block使用外部做排序

### (三)圖示

## 十一、A-way合併
高階合併，一次合併多筆資料，不限2筆。
### (一)以4-way為例:

### (二)用意:
若使用高階合併(需準備多的空間)，但一次合併多筆資料故所需回合數將會減少。
適合使用在外部排序，因為外部排序速度較慢但空間較大，利用空間換取使間。

### (三)時間複雜度討論

上圖:O(n log~2~ k)【時間複雜度＝合併比較次數+搬動次數】
k-way屬於外部排序的一種，電腦讀取一個block(run)但一個block內有許多Data，視一個節點為一堆資料。
---
【引用二元樹算高度的方式做變化】
【二元樹(分支度為2)】
2^h-1^ = 葉節點數量(m)
(h-1)*log~2~2 = log(葉節點數量)
高度 = log(葉節點數量)+1
h = log~2~ m +1
【高度＝回合數-1】
回合數 = log~2~ m

---
【樹(分支度為K)】
K^h-1^ = 葉節點數量(m)
(h-1)*log~k~k = log(葉節點數量)
高度 = log(葉節點數量)+1
h = log~k~m +1
【高度＝回合數-1】
回合數 = log~k~ m

---

總回合數 = (一堆)資料(並行)搬動次數
若每個節點內有n筆資料(每筆都需要搬)那搬動成本 = O(n log~k~m)

總比較次數 =
K-way 比較排序(最簡單2-way方式)，比較(k-1)次
每回合資料皆須被合併一次故每回合n*(k-1)
合併總比較次數
n*(k-1)log~2~ m = O(n log~2~ m)
【ｋ為常數】【log不論以誰為底數，使用換底後時間複雜度亦同】

總時間複雜度 O (n log~k~ m +n log~2~ m ) = O(n log~2~ m)

【分支(k)越多搬動次數越少（樹高），分支越多(k)比較次數越多】

## 十二、並行與緩衝
### (一)舉例
k筆資料需要合併(使用K-way merge)，那我們至少需要k個input跟1個output。
但這樣無法滿足平行(同時)合併【因為合併完結果沒有buffer可以記錄，則暫停了內部的合併】
### (二)圖示:固定buffer下無法並行(同時)合併
### (三)解決:
使用2個output buffer(輸出緩衝)，被寫出的同時，並記錄合併結果至緩衝區；每個輸入也皆準備2個buffer，可避免延遲輸入。
### (四)範例圖示:
Run1、Run2、Run3為3組已排列完成的序列

先從Run1、Run2、Run3取出最小的list
在從Run1取出第2小list，改變link做排序
使用input buffer讓合併時可有重疊，讓合併不會延遲。

## 十三、生成
### (一)討論
討論為了減少合併的比較次數，使用選擇樹（贏家樹、輸家樹）
葉節點儲存為每個Run下一個要比較的元素。
贏家樹:一路找出最小值為贏家。
輸家數:贏家樹相反，找出最大值。 //重要容易誤會
通常使用輸家樹，因為贏家樹還需要額外儲存兄弟節點。
### (二)程式碼
## 十四、最佳合併
### (一)圖示:
每個合併資料皆可以產生許多不同的樹(如下圖)
依下圖，從葉節點至樹根距離稱外部路徑長
倘若每個葉節點維權重的話，那此成本樹為:
各葉節點*各外部路徑長的加總，故使用Huffman方法找最佳解

### (二)霍夫曼樹 (Huffman Tree)
#### 1、方法
是一種貪婪演算法，因總成本=遠路長*權重。
為了達到最小成本將路徑最長安排給權重最小的點，故加總後即可得到最小成本樹。
#### 2、圖示

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed