# 排序演算法 : 分解步驟程式碼
###### tags: `school`
https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FrkwOakKo_
:::warning
**執行程式 : [插入排序](https://replit.com/@LIANGcode/Cha-Ru-Pai-Xu-Insertion-Sort#main.cpp)**
**執行程式 : [選擇排序](https://replit.com/@LIANGcode/Xuan-Ze-Pai-Xu-Selection-Sort)**
**執行程式 : [氣泡排序](https://replit.com/@LIANGcode/Qi-Pao-Pai-Xu-Bubble-Sort)**
**執行程式 : [快速排序](https://replit.com/@LIANGcode/Kuai-Su-Pai-Xu-Quick-Sort2)**
**執行程式 : [堆積排序](https://replit.com/@LIANGcode/Dui-Ji-Pai-Xu-Fa-Heap-Sort)**
**執行程式 : [謝耳排序法](https://replit.com/@LIANGcode/Xie-Er-Pai-Xu-Fa)**
:::

:::success
### **氣泡排序** : **相鄰比較**
* **比較次數"不受"輸入資料順序影響，但交換次數有影響**
* **每回合至少一個資料到正確位置**
* **回合數 : n-1**

### **選擇排序** : **每回合找最小與第一個資料交換**
* **比較次數"不受"輸入資料順序影響，最差最佳相同**
* **每回合至少一個資料到正確位置**
* **回合數 : n-1**

### **插入排序** : **與以排序好的資料比較，插入適當的位置**
* **比較次數"會"受輸入資料順序影響**
* **回合數 : n-1**

### **快速排序** :**找中間值，小左，大右，直到完成**
* **每回合至少一個資料到正確位置**
* **需額外堆疊空間**
* **平均時間最快的內部排序法**
* **回合數 : n-1**

### **堆積排序** : **為了減少選擇排序比較次數，樹根與最後一個節點交換，重建堆積樹**
* **完整二元樹**
* **回合數 : n-1**
* **每回合至少一個資料到正確位置**

### **謝耳排序法** : **減少插入排序搬移次數 Gap=[n DIV 2]**
* **每回合至少一個資料到正確位置**

### **合併排序法 : 分治，分割再合併**
* **適用於內部 外部**
* **每回合至少一個資料到正確位置**

### **基數排序法 : 依個位數分類 LSD : 右 MSD : 左**
* **幾位數 幾回合**
* **額外空間大**
* **無法負數**
* **位數多 MSD效率比較好**

:::



## 插入排序(Insertion Sort)
**執行程式 : [插入排序](https://replit.com/@LIANGcode/Cha-Ru-Pai-Xu-Insertion-Sort#main.cpp)**

## **選擇排序(Selection Sort)**
**執行程式 : [選擇排序](https://replit.com/@LIANGcode/Xuan-Ze-Pai-Xu-Selection-Sort)**

## **氣泡排序(Bubble Sort)**
**執行程式 : [氣泡排序](https://replit.com/@LIANGcode/Qi-Pao-Pai-Xu-Bubble-Sort)**

## **快速排序(Quick Sort)**
**執行程式 : [快速排序](https://replit.com/@LIANGcode/Kuai-Su-Pai-Xu-Quick-Sort)**

## **合併排序(Merge Sort)**
**時間複雜度都是 : O(n log n)**

**Merge Sort is a divide and conquer method of sorting
• 將兩個已排序過的記錄合併，而得到另一個排序好的記錄。
• 可分為兩種類型：
• Iterative (迴圈, 非遞迴)
• Recursive (遞迴)**

Recursive Merge Sort
• 將資料量 n 切成 n/2 與 n/2 兩半部，再各自Merge Sort，最後合併
兩半部之排序結果即成。
• 切割資料量 n 的公式為：⌊(low+high)/2⌋
Algorithm主要由2個副程式組成：
• Merge2副程式
• 將兩筆已排序的記錄，合併成一筆已排序的記錄 U
• 需要三個整數變數 i, j, k.及一個額外的陣列空間U
• If S[i] ≤ S[j] then output S[i], i 前進且 k 前進
else output S[j], j 前進且 k 前進
• 當 i > mid 或 j > high 時則停止，並將剩餘記錄output
• MergeSort2副程式
• 執行整個記錄串的遞迴切割


:::success
**MergeSort(arr[], l, r)**

* Find the middle point to divide the array into two halves: **middle m = l + (r – l)/2**
* Call mergeSort for first half: **Call mergeSort(arr, l, m)**
* Call mergeSort for second half: **Call mergeSort(arr, m + 1, r)**
* Merge the two halves sorted in step 2 and 3: **Call merge(arr, l, m, r)**
:::

## **堆積排序法(Heap Sort)**

## **謝耳排序法**