---
# System prepended metadata

title: 資料結構 第七章 排序
tags: [資料結構]

---

---
tags: 資料結構
---
# 資料結構 第七章 排序
![](https://i.imgur.com/SkbZzkI.jpg)

## 一、搜尋與驗證
    討論影響排序因素，搜尋資料可能可以分成有序資料及亂序，可以分成內部(記憶體)搜尋或是外部(硬碟)搜尋...等等。
### (一)有序搜尋
#### 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)程式碼
![](https://i.imgur.com/8tEcEqt.jpg)


#### 2、特性
##### (1)內部排序、外部排序
    內部排序應用在列表size較小時(在記憶體中)，排序速度較快(但容量小)，外部排序則是列表size較大無法直接在(記憶體中排序)，使用硬碟(disk)速度較慢(但容量大)。
##### (2)穩態(stable)、非穩態(unstable)
    穩態:排序的過程每次的交換不影響已排序完成的列表。
    非穩態:排序的過程每次交換可能會影響排序完成中元素的順序。
## 二、插入排序
    分成2個集合(已排序、非排序)
    step1:每回合從非排序中取一數至已排序集合中(做排序)
    step2:直到非排序集合已空，則完成排序
### (一)圖示:
#### 【粗體為已排序集合、非粗體為非排序集合】
![](https://i.imgur.com/mQh2FwI.jpg)
### (二)時間複雜度:
    每一回合插入一個數做排序，最壞情況(每次插入的數皆為做小)故原先的資料皆向右移動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)。
    
### (二)程式碼:
![](https://i.imgur.com/u5kZuSt.jpg)


## 四、最佳排序時間:
### (1)圖示
![](https://i.imgur.com/zJIe2mB.jpg)
### (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)圖示:
![](https://i.imgur.com/p15rONg.jpg)

#### (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)圖示:
![](https://i.imgur.com/SoKwblt.jpg)
![](https://i.imgur.com/GQ9qLCX.jpg)

#### (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;
     }

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

#### 2、從最低有效位元至最高(Least Significant Digit)
##### 圖示:
    以數字(13種不同數字)做比較故最右側為Ace，最左側為2。
![](https://i.imgur.com/YkvH9PZ.jpg)
#### 3、範例圖示(以LSD為例):
    以下為個位數排序後結果，使用排序後結果再為十位數做排序，再使用十位數排序結果，去做百位數排序，將得到由小到大的排序數列
![](https://i.imgur.com/RxIrNcm.jpg)
![](https://i.imgur.com/1RvLLw1.jpg)
![](https://i.imgur.com/uXCjAeA.jpg)
#### 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
![](https://i.imgur.com/slNYdNr.jpg)

#### 2、課本範例圖解:
![](https://i.imgur.com/xPrfqnJ.jpg)
![](https://i.imgur.com/jhPAlJr.jpg)

#### 3、程式碼
![](https://i.imgur.com/NfcXL4y.jpg)



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


### (三) Table sort

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

#### 2、課本範例圖解:
![](https://i.imgur.com/gpiicTY.jpg)

#### 3、程式碼
![](https://i.imgur.com/LRfWSCJ.jpg)






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

### 程式碼
371

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

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

### (三)圖示
![](https://i.imgur.com/VgzuHtV.jpg)
![](https://i.imgur.com/3J2v979.jpg)


## 十一、A-way合併
    高階合併，一次合併多筆資料，不限2筆。
### (一)以4-way為例:
![](https://i.imgur.com/P9YL5z3.jpg)

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

### (三)時間複雜度討論
![](https://i.imgur.com/af4yjlJ.jpg)

    上圖: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下無法並行(同時)合併
![](https://i.imgur.com/QNhnOci.jpg)
![](https://i.imgur.com/hedP81z.jpg)
### (三)解決:
    使用2個output buffer(輸出緩衝)，被寫出的同時，並記錄合併結果至緩衝區；每個輸入也皆準備2個buffer，可避免延遲輸入。
### (四)範例圖示:
    Run1、Run2、Run3為3組已排列完成的序列
![](https://i.imgur.com/z6O9aGR.jpg)
    
    先從Run1、Run2、Run3取出最小的list
    在從Run1取出第2小list，改變link做排序
    使用input buffer讓合併時可有重疊，讓合併不會延遲。
![](https://i.imgur.com/4CvT6wx.jpg)





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

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



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