---
# System prepended metadata

title: 排序演算法報告 巫俊吉 11228108

---

五種排序法報告 巫俊吉 11228108 
# 五種排序演算法
## **1.氣泡排序法**
### 1.原理
    重複地走訪要排序的數列，一次比較兩個元素，如果它們的順序錯誤就將它們交換位置。
### 2.方法
    1.從第一筆資料開始，逐一比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，
    2.再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。
### 3.優點
    1.簡單易懂，實現容易
    2.對於小型數據集表現良好
### 4.缺點
    1.效率較低，尤其是在大型數據集上，其時間複雜度為 O(n^2)，效率不高。
    2.需要大量的交換操作，對於資源有限的系統可能不太適合。
    3.在數列已經排序好的情況下，仍需完整地執行一次排序過程，這導致了額外的計算浪費。
![20121027K4gjOElSjD](https://hackmd.io/_uploads/SkzZ8ORJ0.jpg)
---

## **2.插入排序法**
### 1.原理
    將數列中的每個元素插入到已排序部分的適當位置中，從而逐步構建整個有序數列。
### 2.方法
    1.從第二個元素開始，將其與已排序部分進行比較。
    2.將該元素插入到已排序部分中適當的位置，使得插入後的部分仍然是有序的。
    3.重複上述步驟，直到所有元素都被插入並排序完成。
### 3.優點
    1.簡單易懂，容易實現。
    2.對於小型數據集表現良好，效率高於一些其他排序算法，如氣泡排序法和選擇排序法。
    3.在部分有序的數列中，表現優異，時間複雜度可以降低到 O(n)。
### 4.缺點
    1.效率較低，尤其是對於大型數據集，其時間複雜度為 O(n^2)，效率較低。
    2.對於逆序數列，效率最差。
    3.插入排序法需要大量的元素移動操作，尤其是當需要將一個元素插入到已排序部分的最前面時，
    這可能需要移動大量元素，影響效率。
![201210273vOWVTDxu7](https://hackmd.io/_uploads/rJvc_u0yA.jpg)
---

## **3.選擇排序法**
### 1.原理
    原理是反覆從未排序數列中找出最小值，將它與左邊的數做交換。
### 2.方法
    1.從待排序的數列中選擇最小（或最大）的元素。
    2.將該元素與待排序部分的第一個元素進行交換。
    3.接下來，在剩餘的元素中再次找到最小（或最大）的元素，並與待排序部分的第二個元素進行交換。
    4.重複上述步驟，直到所有元素都被排序完成。
### 3.優點
    1.簡單易懂，容易實現。
    2.不需要額外的空間存儲，是一種原地排序算法。
    3.對於小型數據集表現良好。
### 4.缺點
    1.效率較低，尤其是對於大型數據集，其時間複雜度為 O(n^2)，效率較低。
    2.選擇排序法在每一次選擇最小（或最大）元素的過程中，都需要進行多次比較操作，即使已經找到
    最小（或最大）元素，也需要將其和待排序部分的第一個元素進行交換操作，這增加了不必要的交換
    次數。
    3.不穩定，即相等元素的相對位置可能會改變。
        
![20121027Z3FUzMHujx](https://hackmd.io/_uploads/ryYkc_RJA.jpg)
---


## **4.合併排序法**

### 1.原理
    每次從待排序的數列中選擇最小（或最大）的元素，與待排序部分的第一個元素進行交換，逐步構建
    整個有序數列。這個過程不斷地在剩餘的未排序部分中選擇最小（或最大）的元素，並將其放置在已
    排序部分的末尾，直到所有元素都被排序完成。
### 2.方法
    1.從待排序的數列中選擇最小（或最大）的元素。
    2.將該元素與待排序部分的第一個元素進行交換。
    3.在剩餘的元素中再次找到最小（或最大）的元素，與待排序部分的第二個元素進行交換。
    4.重複上述步驟，直到所有元素都被排序完成。
### 3.優點
    1.簡單易懂，容易實現。
    2.不需要額外的空間存儲，是一種原地排序算法。
    3.對於小型數據集表現良好。
### 4.缺點
    1.效率較低，尤其是對於大型數據集，其時間複雜度為 O(n^2)，效率較低。
    2.每一次選擇最小（或最大）元素的過程中，都需要進行多次比較操作，增加了不必要的比較次數。
    3.不穩定性較高，即相等元素的相對位置可能會改變。

![201210276xe8hMfgbN](https://hackmd.io/_uploads/BJWEn_A1C.jpg)

## **5.基數排序法**
### 1.原理
    將整數按位元數切割成不同的數字，然後按每個位數分別比較。
### 2.方法
    1.確定數據集中最大數字的位數，然後初始化10個桶（0到9）以存放數字。
    2.從最低有效位（個位）到最高有效位（最高位），將數字按照位數的值依次放入對應的桶中。
    3.將數字按照桶的順序依次收集起來，形成新的數據集。
    4.重複步驟2和步驟3，直到所有位數都被考慮過。
    5.當所有位數都被考慮過後，得到的數據集就是排好的。
### 3.優點
    1.基數排序法是一種穩定的排序算法，即相同數值的元素在排序後的相對位置不會改變。
    2.基數排序法不需要進行元素之間的比較，而是根據數字的位數來進行排序，因此對於某些特定情
    況下，它的效率可能比比較型的排序算法更高。
### 4.缺點
    1.基數排序法需要額外的空間來存儲每個位上的桶，當數據集較大時，可能會佔用大量的內存
    空間。
    2.基數排序法通常適用於數字範圍較小、位數固定的情況，對於位數變化很大的數據集效果可能
    不佳。


![lsd-radix-sort](https://hackmd.io/_uploads/HyAdXYC10.gif)

---
# **複雜度比較**
1. 氣泡排序法：
最壞情況時間複雜度：O(n^2)。
最佳情況時間複雜度：O(n)。
平均情況時間複雜度：O(n^2)。
2. 插入排序法：
最壞情況時間複雜度：O(n^2)。
最佳情況時間複雜度：O(n)。
平均情況時間複雜度：O(n^2)。
3. 選擇排序法：
最壞情況時間複雜度：O(n^2)。
最佳情況時間複雜度：O(n^2)。
平均情況時間複雜度：O(n^2)。 
4. 合併排序法：
 最壞情況時間複雜度：O(nlogn)。
最佳情況時間複雜度：O(nlogn)。
平均情況時間複雜度：O(nlogn)。
5. 基數排序法：
最壞情況時間複雜度：O(d * (n + k))。
最佳情況時間複雜度：O(d * (n + k))。
平均情況時間複雜度：O(d * (n + k))。
其中 d 是數字的位數，n 是數據集大小，k 是基數範圍。

        基於以上比較，合併排序法通常具有更好的性能，特別是在處理大型數據集時。但是，對於某
        些特定的情況，例如對於位數較少且數據集範圍有限的情況下，基數排序法可能會更加有效。

---
# **時間模擬實驗&程式碼**

## 1.  **氣泡排序法**
![螢幕擷取畫面 2024-04-06 163136](https://hackmd.io/_uploads/HJTxjK0k0.png)
---
## 2.  **插入排序法** 
![螢幕擷取畫面 2024-04-06 164408](https://hackmd.io/_uploads/S1OtotR10.png)
---
## 3.  **選擇排序法** 
![螢幕擷取畫面 2024-04-06 164555](https://hackmd.io/_uploads/rJHJhKC10.png)
---
## 4.  **合併排序法**
![螢幕擷取畫面 2024-04-06 164727](https://hackmd.io/_uploads/ByqBnFA10.png)
---
![螢幕擷取畫面 2024-04-06 164843](https://hackmd.io/_uploads/SJ8iht0y0.png)
---
![螢幕擷取畫面 2024-04-06 164918](https://hackmd.io/_uploads/ByIjnYAkA.png)
---
## 5.  **基數排序法**
![螢幕擷取畫面 2024-04-06 165119](https://hackmd.io/_uploads/rkNHpFA1R.png)
---
![螢幕擷取畫面 2024-04-06 165157](https://hackmd.io/_uploads/HyEBaYCJA.png)
---

# **心得**
    這次藉由排序演算法報告，我知道了如何寫出N個數排列的程式，以及學到了如何計算程式的執行
    時間並將其顯示出來，也找到了除了課堂中教授教導的四種排序法以外，其他種的排序法能夠進行
    排序，還有希爾排序法、快速排序法，讓我反思到我們不該拘泥於課堂上，而是藉由課堂去做更多
    的延伸學習。這次的排序法僅是其中一項，之後在課堂中所學到的我都會在課後多多查詢相關資料
    ，尋找出各種不一樣的思考方式，並試著融會貫通做出屬於自己的一套方式。