JS Sorting Algorithm

十大經典排序演算法

排序演算法是《資料結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序，內部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要存取外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。用一張圖概括：

關於時間複雜度：

1. 平方階(O(n2)) 排序各類簡單排序：直接插入、直接選擇和冒泡排序。
2. 線性對數階(O(nlog2n)) 排序快速排序、堆排序與歸併排序；
3. O(n1+§)) 排序，§ 是介於0 和1 之間的常數。 希爾排序
4. 線性階(O(n)) 排序基數排序，此外還有桶子、箱排序。

關於穩定性：

穩定的排序演算法：冒泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n ：資料規模

k ：「桶」的個數

In-place ：佔用常數內存，不佔用額外內存

Out-place ：佔用額外內存

穩定性：排序後2 個相等鍵值的順序和排序之前它們的順序相同

---

GitBook 內容大綱

1. 冒泡排序
2. 選擇排序
3. 插入排序
4. 希爾排序
5. 歸併排序
6. 快速排序
7. 堆排序
8. 計數排序
9. 桶排序
10. 基數排序

---

本書內容幾乎完全來自網路。

開源專案地址：https://github.com/hustcc/JS-Sorting-Algorithm，整理人hustcc。

GitBook 線上閱讀網址：https://sort.hust.cc/。

本專案使用lint-md 進行中文Markdown 檔案的格式檢查，務必在提交Pr 之前，請確保Markdown 格式正確。