排序演算法(Sorting Algorithm)
本篇將簡單的介紹以及實作選擇排序法 (Selection sort)、插入排序法 (Insertion sort)、氣泡排序法(Bubble sort)、合併排序法(Merge sort)，排序演算法在新鮮人面試中也很常被提及。
Simple sorts
選擇排序法(Selection sort)、插入排序法(Insertion sort)兩種簡易的排序演算法(Simple sorts)，適用於小量的資料，在大量的資料中效能表現較差。
選擇排序法 (Selection sort)
選擇排序法 — 將資料分為" 已排序 " 和 " 未排序 "，在未排序中找出最小(or 最大)值，加入已排序的末端。
- 時間複雜度(Time Complexity)： 最好 Ο(n²)、最差 Ο(n²)、平均 Ο(n²)
- 空間複雜度(Space Complexity)：θ(1)
插入排序法 (Insertion sort)
插入排序法 — 將資料分為” 已排序 “ 和 “ 未排序 “，將未排序的第一筆值和已排序的資料由右而左相比大小並插入適當位置。
- 時間複雜度(Time Complexity)： 平均 Ο(n²)
最好 Ο(1) - 當資料的順序為由小到大時(or 大到小)，每回只需比較1次。
最差 Ο(n²) - 當資料的順序為由大到小時(or 小到大)，第i回合需比i次。
- 空間複雜度(Space Complexity)：θ(1)
Bubble sorts
氣泡排序法(Bubble sort)，簡單但效率較低的排序方法，因為易於分析、理解因此常用於排序演算法介紹中，較少被使用在實際實作上。
氣泡排序法(Bubble sort)
氣泡排序法 — 將資料中的第 i 筆和第 i+1 筆資料比較大小，若 i+1 大於 i 則交換兩值，依此搜尋所有值。若沒有值交換則代表資料皆已排序好。
- 時間複雜度(Time Complexity)： 平均 Ο(n²)
最好 Ο(n) — 當資料的順序為由小到大時(or 大到小)，因此不須交換。
最差 Ο(n²) — 當資料的順序為由大到小時(or 小到大)，每回皆需要交換。
- 空間複雜度(Space Complexity)：θ(1)
Efficient sorts
合併排序法(Merge sort)、 堆積排序法(Heap Sort)、快速排序法(Quick Sort)，皆屬於較快速的排序法，平均時間複雜度皆有 Ο(n log n)，然而空間複雜度較其他排序來的高。
合併排序法(Merge sort)
合併排序法 — 將資料分割為左子樹以及右子樹，接著遞迴分割每一次分割後的左子樹以及右子樹，直到每個子樹只剩下一個元素，再將這些子樹依小到大(or 大到小)合併(Merge)。
- 時間複雜度(Time Complexity)： 平均 Ο(n log n)、最差Ο(n log n)、平均 Ο(n log n)
- 空間複雜度(Space Complexity)：θ(n)
