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

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

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

---

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

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


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


---
# **複雜度比較**
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. **氣泡排序法**
---
## 2. **插入排序法**
---
## 3. **選擇排序法**
---
## 4. **合併排序法**
---
---
---
## 5. **基數排序法**
---
---

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