---
title: '排序 Sort'
disqus: kyleAlien
---
排序 Sort
===
## OverView of Content
以下會說明
O(N^2^)：氣泡、插入、選擇排序
O(N log^N^)：合併、快速、堆疊排序
並且我們知道在無序陣列中，要搜尋某個數值最差表現為 `log(N)`；若在已排序的情況下使用二元樹搜尋最差表現為 `O(log N)`
[TOC]
## O(N^2^) 效能
### 氣泡排序 - Bubble sort
* 排序一個無序陣列，使用 **氣泡排序**，它的關鍵在於比較，**取一個數，與 ++相鄰數比較++ 並交換**；以下做一個 `升序排列`
> 
```java=
public class BubbleSort {
public void sort(int[] array) {
// 記錄比較次數
int compareTime = 0;
for (int i = 0; i < array.length; i++) {
// -1 的原因是因為要多取相鄰數
// -i 則是避免重複比較，已比較完成的數
for(int j = 0; j < array.length - 1 - i; j++) {
compareTime += 1;
// ! 與相鄰數 [j+1] 比較
if(array[j + 1] < array[j]) { // 把大數往右推
swap(array, j, j + 1);
}
}
}
System.out.println("Total compare time use: " + compareTime);
}
private void swap(int[] array, int source, int target) {
int tmp = array[source];
array[source] = array[target];
array[target] = tmp;
}
}
```
* 測試氣泡排序
```java=
public static void main(String[] args) {
int[] nonSort = {
15, 21 ,20, 2, 15 ,24, 5, 19
};
new BubbleSort().sort(nonSort);
System.out.println("After sort: " + Arrays.toString(nonSort));
}
```
> 
:::info
* **效能**：
以比較次數來看，總比較次數為 `(N - 1) + ... + 1`，這等同於 `N * (N - 1) / 2`，可以說 BIG O 是 O(N^2^)
:::
### 選擇排序 - Selection sort
* 排序一個無序陣列，使用 **選擇排序**，它的關鍵在於比較 (**比出最小數 or 最大**)，**要拿當下的數來比較剩餘的所有數**；以下做一個 `升序排列`
> 與氣泡排序類似，但比較的不是相鄰數
>
> 
```java=
public class SelectionSort {
public void sort(int[] array) {
// 記錄比較次數
int compareTime = 0;
for (int i = 0; i < array.length; i++) {
// 內部迴圈是從當前數的下一個，開始往後尋找最小的數
for(int j = i + 1; j < array.length; j++) {
compareTime += 1;
// 與氣泡排序的差異在這，比較的不是相鄰數，而是外圈的 [i]
if(array[i] > array[j]) {
// ! 找到較小的數，則進行交換
swap(array, i, j);
}
}
}
System.out.println("Total compare time use: " + compareTime);
}
private void swap(int[] array, int source, int target) {
int tmp = array[source];
array[source] = array[target];
array[target] = tmp;
}
}
```
* 測試選擇排序
```java=
public static void main(String[] args) {
int[] nonSort = {
15, 21 ,20, 2, 15 ,24, 5, 19
};
new SelectionSort().sort(nonSort);
System.out.println("After sort: " + Arrays.toString(nonSort));
}
```
> 
:::info
* **效能**：
**同上 BIG O 是 O(N^2^)**
:::
### 插入排序 - Insertion sort
* 排序一個無序陣列，使用 **插入排序**，它的關鍵在 **拿當前數作為目標值 (最大 or 最小)，有新數後才在已排序的範圍內比較交換**；以下做一個 `升序排列`
> 
```java=
public class InsertionSort {
public void sort(int[] array) {
// 記錄比較次數
int compareTime = 0;
for (int i = 0; i < array.length; i++) {
// 差異在內部的 for 迴圈條件
// 在範圍內 (i ~ 0) 再次比較，有需要則交換
for(int j = i; j > 0; j--) {
compareTime += 1;
if(array[j] < array[j - 1]) {
swap(array, j, j - 1);
}
}
}
System.out.println("Total compare time use: " + compareTime);
}
private void swap(int[] array, int source, int target) {
int tmp = array[source];
array[source] = array[target];
array[target] = tmp;
}
}
```
* 測試插入排序
```java=
public static void main(String[] args) {
int[] nonSort = {
15, 21 ,20, 2, 15 ,24, 5, 19
};
new SelectionSort().sort(nonSort);
System.out.println("After sort: " + Arrays.toString(nonSort));
}
```
> 
:::info
* **效能**：
同上 BIG O 是 O(N^2^)
:::warning
* 但實際比較起來，插入排序是 O(N^2^) 排序中最好的
:::
:::
## 遞迴 & 分治
**遞迴是一種手段**，**分治是一種概念**；可以用遞迴來實現分治
### 遞迴 recursion
:::warning
* 遞迴 (recursion) 的特色
* 是消耗 Stack 空間，而是否非常消耗時間 ? 則是有關於你是否有解決子問題重複
* 要特別注意 **收斂問題**，如果沒有收斂則會造成 StackOverflow 問題
:::
* 遞迴 (recursion) 就是函數呼叫自己，比較有名的是費式數列；遞迴 `(N - 1)` + `(N - 2)`，遞迴 (recursion) BIG O 是 **O(2^N^)**
> 分支^深度^
```java=
public class Fibonacci {
public int fibonacci(int val) {
if(val == 0) { // 收斂
return 0;
}
if(val == 2 || val == 1) { // 收斂
return 1;
}
return fibonacci(val - 1) + fibonacci(val - 2);
}
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
int result = fibonacci.fibonacci(5);
System.out.println("Fibonacci(5): " + result);
}
}
```
> 
* 階乘 `N!` 是所有小於或等於 N 之正整數的乘積，表達方式有如下
* `N!` = `N` * `(N - 1)` * `(N - 2)` * `(N - 2)` * ... * `1`
* `N!` = `N` * `(N - 1)!`
可用 **遞迴來實現階乘 `N!`**
```java=
public class Factorial {
public int factorial(int val) {
if(val == 1) { // 收斂
return 1;
}
return val * factorial(val - 1);
}
public static void main(String[] args) {
Factorial factorial = new Factorial();
int result = factorial.factorial(5);
System.out.println("5!: " + result);
}
}
```
> 
### 分治 - 分二法 找出最大數
* 上面有說到分治，分治就是分而治之，也就是 **將大問題拆小，直到問題成為原子性無法再拆分，再將問題解決**，而這個過程就可以用到遞迴技巧
:::info
* 分治 + 遞迴時每次都要改變傳入遞迴的 **入參**
:::
* 這邊使用二分法的分治方案，將每個要解決的問題拆分為 2，直到不能拆分
```java=
package standard.recursion;
public class FindMax {
public int findMax(int[] mixArray) {
return _findMax(mixArray, 0, mixArray.length - 1);
}
private int _findMax(int[] mixArray, int start, int end) {
// 分治的最終結果就是剩單一個數 (收斂)
if(start == end) {
// 直接回傳單數
return mixArray[start];
}
// 分治方案，取 array 的中間值
int mid = (start + end) / 2;
// 左遞迴
int left = _findMax(mixArray, start, mid);
// 右遞迴
int right = _findMax(mixArray, mid + 1, end);
// 取最大為解
return Math.max(left, right);
}
public static void main(String[] args) {
FindMax findMax = new FindMax();
int result = findMax.findMax(new int[] {
1, 3, 5, 2, 1, 9, 7,
});
System.out.println("Max Result: " + result);
}
}
```
> 
* 分治法以上面範例來說，最終比較 (Stack 深度) 的次數為 13 次，而進入 if 條件的又只有 7 次，其中那多出的 6 次是遞迴 `Math.max` 結果的消耗
> 
## O(N logN) 效能
### 合併排序 - Merge sort
* 合併排序使用到 遞迴、二分法 (分治)、**合併**，其中 **合併是這個排序的重點**
1. 額外儲存空間：多出一個空間來儲存原 Array 的內容
> 
2. Merge 時兩個抽出數值比較，小的先移除放入 Result 對列 (同數則隨意取都可以)
> 
3. 重複 `2.` 的動作
> 
* 以下實作合併排序 (升序排列)
1. **二分法 (分治)**
```java=
public class MergeSort {
public void mergeSort(int[] array) {
_mergeSort(array, 0, array.length - 1);
}
private void _mergeSort(int[] array, int start, int end) {
if(start == end) {
return;
}
// 二分法分治
int mid = (start + end) / 2;
_mergeSort(array, start, mid);
_mergeSort(array, mid + 1, end);
// 重點 merge
_merge(array, start, end, mid);
}
}
```
2. 在核心 merge 內有些要注意的重點
* **複製已排序的 Array** 為 `tmpArray`(暫存 Array)
* 內部 for 迴圈會取用 `tmpArray`(暫存 Array) 改變原來的 Array
* **if/else 判斷順序，必須先判斷是否越界**
```java=
public class MergeSort {
private void _merge(int[] array, int start, int end, int mid) {
int[] tmpArray = new int[array.length];
// 複製已排序的 Array
System.arraycopy(array, 0, tmpArray, 0, array.length);
int left = start;
int right = mid + 1;
for(int i = start; i < end + 1; i++) {
// if/else 判斷順序，必須先判斷是否越界
if(left > mid) { // 左邊越界
// 取右 ( 左邊已經沒有值可取
// 改變原 Array
array[i] = tmpArray[right];
right++;
} else if(right > end) { // 右邊越界
// 取左 ( 右邊已經沒有值可以取
// 改變原 Array
array[i] = tmpArray[left];
left++;
} else if(tmpArray[left] < tmpArray[right]) { // 由於是升序所以取小
// 改變原 Array
array[i] = tmpArray[left];
left++;
} else if(tmpArray[left] > tmpArray[right]) { // 由於是升序所以取小
// 改變原 Array
array[i] = tmpArray[right];
right++;
}
}
}
}
```
:::warning
* **要比較 `tmpArray` 不是 `array`**
:::
* 測試 MergeSort
```java=
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
int[] targetOrder = new int[] {
21, 2, 15, 20, 3
};
mergeSort.mergeSort(targetOrder);
System.out.println(Arrays.toString(targetOrder));
}
```
> 
:::info
* **合併排序效能為 O(N logN)**
1. `N`：其中比較的 **重點是在 merge 的 for 迴圈執行次數**，它的次數會是 (start ~ end)；也就是 merge 的完成時間與子問題的組合大小成正比
2. `log N`：由於使用二分法，可以將原陣列分割成 log(N) 層
:::success
**每層耗費時間為 N，層數為 logN，最終 BIG O 就是 O(N logN)**
> 假設有 7 個數，每層都比較 7 次，而有 log(7) 層， 7 * log(7) 就是 21
>
> - 16 個數用 Bubble Sort BIGO 需要 120 次
> - 16 個數用 Merge Sort BIGO 需要 64 次
:::
:::
### 快速排序 - Quick sort
* 從陣列中抓取一個數為基準值 (pivot value) p，將 p 插入正確位置，再分治為左右兩側，左側 <= p、右側 >= p
> 
* 這裡有個問題，如何才能知道 p 應該放置的位置呢 ? **其實 p 並沒有完全重新排列，而是 ++部分排列++**，這時就需要一個 **分割函數**
> 這個分割函數也是 QuickSort 的重點
該函數用來區分已 p 為標準的左右陣列，可以使用上面的 `SelectionSort` 技巧，選擇最小值接換 (升序排列) 直到碰到 `pivot`
```java=
// 升序排列 (部分
private void exchange(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
// 選擇排序
private int partitionBySelection(int[] array, int start, int end, int pivot) {
int pVal = array[pivot];
for(int i = start; i < end; i++) {
for (int j = i + 1; j < end; j++) {
if(array[i] > array[j]) {
exchange(array, i, j);
}
}
if(array[i] == pVal) { // 判斷到 pivot 即可
pivot = i;
break;
}
}
return pivot;
}
```
> 測試 `partitionBySelection` 輸出結果
>
> 
* 完整的 QuickSort 程式如下 (升序)
```java=
public class QuickSort {
public void quickSort(int[] array) {
_quickSort(array, 0, array.length);
}
private void _quickSort(int[] array, int start, int end) {
if(end <= start) {
return;
}
int pivot = start;
int location = partitionBySelection(array, start, end, pivot);
_quickSort(array, start, location - 1);
_quickSort(array, location + 1, end);
}
private int partitionBySelection(int[] array, int start, int end, int pivot) {
int pVal = array[pivot];
for(int i = start; i < end; i++) {
for (int j = i + 1; j < end; j++) {
if(array[i] > array[j]) {
exchange(array, i, j);
}
}
if(array[i] == pVal) {
pivot = i;
break;
}
}
return pivot;
}
private void exchange(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
}
```
* 測試 QuickSort
```java=
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] array = {
15, 21, 20, 2, 15, 24, 5, 19
};
quickSort.quickSort(array);
System.out.println(Arrays.toString(array));
}
```
> 
:::warning
* **QuickSort 效能 ?**
我們知道 QuickSort 的核心在於 `partition` 部分交換，但是如果是針對 **已排序的序列，`partition` 的消耗仍可能會到到 O(N^2^)**
為了避免這種問題，**在取 `pivot` 數值時，我們就會採用隨機值**
```java=
private void _quickSort(int[] array, int start, int end) {
if(end <= start) {
return;
}
// pivot 改成隨機數
int pivot = (int) (Math.random() * (end - start)) + start;
System.out.println("Pivot: " + pivot + ", start: " + start + ", end: " + end);
int location = partitionBySelection(array, start, end, pivot);
_quickSort(array, start, location - 1);
_quickSort(array, location + 1, end);
}
```
> 
:::success
* 儘管可能到達 O(N^2^) 但仍是多數人會選擇的排序，因為 QuickSort 的優點在於 **不需額外空間的分配**
:::
:::
### 堆積排序 - Heap sort
:::success
在看 HeapSort 之前請先看 [**Heap 數據結構**](https://hackmd.io/OyJmE385Q6CNCJ1VE5Zwyw#Heap-%E5%A0%86%E7%A9%8D)，會透過 Heap 數據結構來調整
:::
* 預計使用的方式：**已經排序好 Heap 結構** 的 Header (最前方 A[1]，我們知道該 Header 為最大值)，與其最後一個數值交換，最終就可以得到一個升序排列，詳細請看下面流程
1. Header 與 Tail 交換，交換完畢後要移動 N 的紀錄指標 (這樣才能知道下一個要交換的 Tail 位置在哪)
> 
2. 由於 dequeue 後，新值放置 Header，需要 sink (下沉) 重新 Heap
> 
3. 不斷重複 `1.`、`2.` 步驟後，我們就可以得到一個重整過後的升序 Array
> 
:::info
在接下來 HeapSort 的實現我們會優化結果，不讓 `A[0]` 為空
:::
* 在做 HeapSort 之前，我們要先整理出 Heap 的數據結構，最基礎的是一個一個入 Array 對列，讓 Heap 自己進行 enqueue 上浮作業，會耗費 O(N) 時間
> 這裡需要改善一個更好的方式，從下到重整 Array
1. **for 迴圈**：**從索引 `N/2` 開始，從下到上建構堆疊**；從尾端的數據開始建構
> e.g：假設尾端索引為 `10`、`9`，其父節點就是 `10/2`、`9/2` 也就是 4
2. **swap、less 調整**：讓最大值放置到 `Array[0]` (原本 Heap Array Header `Array[1]` 是最大)，所以在交換 `swap`、比較 `less` 時，需要將 index - 1
假設父節點為 `4`，左節點為 `8`、右節點為 `9`；都扣除 1 後，比較的結點變為，左節點為 `7`、右節點為 `8`，再開始比較
> 最終 `Array[0]` 會變成 Heap 中最大值
>
> 
```java=
public class HeapSort {
private final int[] array;
private int N;
public HeapSort(int[] array) {
this.array = array;
this.N = array.length;
// 從索引 `N/2` 開始，從下到上建構堆疊
for(int i = N; i < N /2; i++) {
sink(i);
}
}
private void sink(int index) {
while (index * 2 + 1 <= N) {
int c = index * 2; // 預設為左 index
if(less(c, c + 1)) { // 判斷右 index 是否比較大
c = c + 1;
}
if(less(c, index)) { // 最終判斷自結點是否更大
// 自身結點較大，不需要再下沉
break;
}
// 交換結點
swap(c, index);
index = c;
}
}
private void swap(int i, int j) {
// 調整 Heap 從 0 開始
i -= 1;
j -= 1;
// 交換 i & j 數值
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private boolean less(int i, int j) {
// 調整 Heap 從 0 開始
i -= 1;
j -= 1;
// 判斷 i 數值是否小於 j
return array[i] < array[j];
}
// 測試
public static void main(String[] args) {
int[] a = {15, 13, 14, 9, 11, 12, 14, 8, 2, 6};
HeapSort heapSort = new HeapSort(a);
System.out.println(Arrays.toString(heapSort.array));
}
}
```
> 
3. 上面調整完後，其實 sort 就簡單很多了，透過它類似 dequeue 的一個過程，**它的重點在 Heap Header 要與 Tail 交換數值**
```java=
public class HeapSort {
private final int[] array;
private int N;
... 省略建構函數、整理 Heap 的過程
public void sort() {
while (N > 1) {
swap(1, N); // 其實是交換 A[0] & A[N-1]
N -= 1; // 調整紀錄指針
sink(1); // 重整 Heap
}
}
private void swap(int i, int j) {
i -= 1;
j -= 1;
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void main(String[] args) {
// 打亂原本的順序，再排一次
int[] array = {
12, 13, 8, 2, 6 ,
15, 14, 14, 9, 11
};
HeapSort heapSort = new HeapSort(array);
heapSort.sort();
System.out.println(Arrays.toString(heapSort.array));
}
}
```
> 
:::info
* **Heap 排序效能 ?**
1. `less`：其中比較的 **重點是在 less 函數**，在重整 Heap (建構函數時)，時消耗 O(N)，sort 時也消耗 O(N)，所以總計 O(2N)
2. `log N`：由於使用二分法，可以將原陣列分割成 log(N) 層
:::success
**HeapSort 排序效能為 `O(2N logN)`，可以說是 `O(N logN)`**
:::
:::
## Appendix & FAQ
:::info
:::
###### tags: `資料結構`
Sign in with Wallet
Connect another wallet