# 排序法小結與複雜度比較

再次複習相關術語解釋：

* 穩定(Stable)：相同鍵值的資料，排序後順序和排序前一樣；
* 不穩定(Unstable)：相同鍵值的資料，排序後順序不一定和排序前一樣；
* 內部排序(Internal Sort)：所有排序操作都在內部記憶體中完成；
* 外部排序(External Sort)：由於數據太大，因此把數據放在外部記憶體中，而排序通過外部記憶體的數據傳輸才能進行；
* 時間複雜度(Time Complexity)：一個演算法執行所耗費的時間。
* 空間複雜度(Space Complexity)：運行完一個程式所需記憶體的大小。
* 原地置換(In-place)：使用資料原來的資料結構(陣列)進行排序，不需使用暫存的輔助資料結構，不佔用額外記憶體。
* 非原地置換(Out-place)：需使用暫存的輔助資料結構，佔用額外記憶體。

## 常見排序法重點整理

* 以下假設由小到大排序。
* 陣列長度設為 `arr.length = n`
* 速度測試同為八萬筆隨機產生數據，執行時間依本人電腦為主。

### 泡沫排序法
相鄰元素兩兩比較，若右邊的數比左數大就交換，否則不動。
* 需排序 `n - 1` 輪
* 時間複雜度為 O(n^2^)
* 速度測試為 7 秒


### 選擇排序法
從未排序的元素中找到最小值將之與前面的值做交換。
* 需排序 `n - 1` 輪
* 時間複雜度為 O(n^2^)
* 速度測試為 1 秒


### 插入排序法
將待排序元素看作一個有序表和一個無序表，開始時有序表只包含一個元素(設為`arr[0]`)，無序表中包含 `n-1`個元素，排序過程中每次從無序表中取出第一個元素，把它依次與有序表元素進行比較，將它插入到有序表中的適當位置。
* 需排序 `n - 1` 輪
* 第 n 輪需比較 n 個數
* 時間複雜度為 O(n^2^)
* 速度測試為 1400 ms => 1.4 s 秒


### 希爾排序法
是插入排序的一種更高效的改進版本。
步長設為陣列長度除以2，且每輪步長都會再除以2，直至以1為步長進行排序。
假設 n 長度為 10，第一輪排序步長為 5，則依次比較 arr[0] arr[5] , arr[1] arr[6] ...
* 時間複雜度為 O(n^1.3^)
* 速度測試為14 ms

### 快速排序
是對泡沫排序的一種改進。
先從陣列中找出一個基準值，將比基準值小的數值置於基準值的左邊，比基準值大的數值放在基準值的右邊，再對左右子序列重複以上步驟。
動畫理解：https://www.bilibili.com/video/BV1at411T75o
* 時間複雜度為`O(nlogn)`
* 速度測試為20 ms


### 合併排序
採用經典的分治策略(Divide and Conquer)
會先將陣列每次拆分成兩組同大小的子陣列，直到每組都只有一個元素再進行排序後合併。

會需要三個索引：

mid = (left + right) / 2
i = 0 // 左子序列第一個元素
j = mid + 1 // 右子序列第一個元素

和一個中轉陣列 `temp`

i,j 比較，誰比較小就放入 temp，直到左或右某一子序列遍歷結束，則將沒遍歷結束的子序列剩下元素全部放進 temp 陣列中，最後將 temp 陣列 copy 回 arr 陣列。

* 時間複雜度為`O(nlogn)`
* 速度測試為10~11 ms


### 基數排序
又稱 **桶排序(Bucket Sort)**，將整數按位數切割成不同的數字，然後按每個位數分別比較。
* 屬於穩定性的排序。
* 基數排序是經典的空間換時間的方式，佔用記憶體很大，當對海量數據排序時容易造成OutOfMemoryError。
* 時間複雜度為`O(n*k)`
k 為 key 的範圍，以 10 為基數，就是 0-9 之間 k=10
* 速度測試為15 ms


## 時間複雜度

* n：數據規模。
* k："桶"的個數。

## 排序耗時

同樣**八萬筆**隨機產生資料，以本人電腦為主，各測試3-5次取平均值，目前測試的結果是：
* 堆積排序：7.6 ms
* 合併排序：10~11 ms
* 希爾排序(移動)：14 ms
* 基數排序：15 ms
* 快速排序：20 ms
* 選擇排序：634 ms => 0.6 s
* 插入排序：1400 ms => 1.4 s
* 泡沫排序：7 s

在本人電腦執行八萬筆亂數資料排序，所耗費時間順序為：
:::warning
堆積(7.6 ms) < 合併(10 ms) < 希爾(14 ms) < 基數(15 ms) < 快速(20 ms) < 選擇(634 ms) < 插入(1400 ms) < 泡沫(7s)
:::