---
# System prepended metadata

title: '排序演算法 : 分解步驟程式碼'
tags: [school]

---

# 排序演算法 : 分解步驟程式碼  
###### 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效率比較好**

:::

![](https://d3i71xaburhd42.cloudfront.net/06d4e9f930efa63c5e99ba705250e0f4ab6e3b36/5-Table2-1.png)

![](https://i.imgur.com/yoJg3I7.jpg)


## 插入排序(Insertion Sort) 
**執行程式 :  [插入排序](https://replit.com/@LIANGcode/Cha-Ru-Pai-Xu-Insertion-Sort#main.cpp)**
![image alt](https://miro.medium.com/max/1023/1*_NOe6jL9veyR4yAyf85dzA.png)

## **選擇排序(Selection Sort)**
**執行程式 :  [選擇排序](https://replit.com/@LIANGcode/Xuan-Ze-Pai-Xu-Selection-Sort)**
![](https://he-s3.s3.amazonaws.com/media/uploads/2888f5b.png)

## **氣泡排序(Bubble Sort)**
**執行程式 :  [氣泡排序](https://replit.com/@LIANGcode/Qi-Pao-Pai-Xu-Bubble-Sort)**
![image alt](https://miro.medium.com/max/556/0*lq-ZpDYjvYGmS7PO)


## **快速排序(Quick Sort)**
**執行程式 :  [快速排序](https://replit.com/@LIANGcode/Kuai-Su-Pai-Xu-Quick-Sort)**
![image alt](https://iq.opengenus.org/content/images/2021/11/seqqs.drawio.svg)

##  **合併排序(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副程式
• 執行整個記錄串的遞迴切割

![](https://i.imgur.com/fjq9iP8.png)
![](https://i.imgur.com/nZcDnkX.png)

:::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)**
:::
![](https://i.imgur.com/pC4ATgC.png)
![](https://i.imgur.com/Oe7yJMO.png)

## **堆積排序法(Heap Sort)**
![image alt](https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcSglpbZfLExYAcTKXJ6qVuIT00BKMEkTZV9tg&usqp=CAU)


## **謝耳排序法** 
![image alt](https://1.bp.blogspot.com/-GUlOREIVn7w/YJeZDwZNi9I/AAAAAAAACMU/cW9rir6MsyYvNqsMRQptuSp6len1hwYwgCLcBGAsYHQ/s671/1%2BXTnzyR5jyD6wdRXbjJsf1A.png)