---
# System prepended metadata

title: 排序 Sort
tags: [資料結構]

---

---
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

* 排序一個無序陣列，使用 **氣泡排序**，它的關鍵在於比較，**取一個數，與 ++相鄰數比較++ 並交換**；以下做一個 `升序排列`

    > ![](https://i.imgur.com/P6eUKDq.png)

    ```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));
        }
        ```
        > ![](https://i.imgur.com/ksXnZSa.png)

:::info
* **效能**：

    以比較次數來看，總比較次數為 `(N - 1) + ... + 1`，這等同於 `N * (N - 1) / 2`，可以說 BIG O 是 O(N^2^)
:::


### 選擇排序 - Selection sort

* 排序一個無序陣列，使用 **選擇排序**，它的關鍵在於比較 (**比出最小數 or 最大**)，**要拿當下的數來比較剩餘的所有數**；以下做一個 `升序排列`

    > 與氣泡排序類似，但比較的不是相鄰數
    > 
    > ![](https://i.imgur.com/s1Ktl57.png)

    ```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));
        }
        ```
        > ![](https://i.imgur.com/oSJom7O.png)

:::info
* **效能**：

    **同上 BIG O 是 O(N^2^)**
:::

### 插入排序 - Insertion sort

* 排序一個無序陣列，使用 **插入排序**，它的關鍵在 **拿當前數作為目標值 (最大 or 最小)，有新數後才在已排序的範圍內比較交換**；以下做一個 `升序排列`

    > ![](https://i.imgur.com/kcECvIf.png)

    ```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));
        }
        ```
        > ![](https://i.imgur.com/eJZgvWY.png)


:::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);
        }
    }
    ```
    > ![](https://i.imgur.com/0vmXuL1.png)



* 階乘 `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);
        }
    }
    ```
    > ![](https://i.imgur.com/FmhVCw9.png)

### 分治 - 分二法 找出最大數
* 上面有說到分治，分治就是分而治之，也就是 **將大問題拆小，直到問題成為原子性無法再拆分，再將問題解決**，而這個過程就可以用到遞迴技巧

    :::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);
        }

    }
    ```
    > ![](https://i.imgur.com/du9worr.png)

    * 分治法以上面範例來說，最終比較 (Stack 深度) 的次數為 13 次，而進入 if 條件的又只有 7 次，其中那多出的 6 次是遞迴 `Math.max` 結果的消耗

        > ![](https://i.imgur.com/HD7f941.png)


## O(N logN) 效能


### 合併排序 - Merge sort

* 合併排序使用到 遞迴、二分法 (分治)、**合併**，其中 **合併是這個排序的重點**
    
    1. 額外儲存空間：多出一個空間來儲存原 Array 的內容

        > ![](https://i.imgur.com/fwh2hyS.png)

    2. Merge 時兩個抽出數值比較，小的先移除放入 Result 對列 (同數則隨意取都可以)

       > ![](https://i.imgur.com/alFQwmy.png)

    3. 重複 `2.` 的動作
        
        > ![](https://i.imgur.com/gJKjKDX.png)

* 以下實作合併排序 (升序排列)
    
    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));
    }
    ```
    > ![](https://i.imgur.com/rZTbFQf.png)

    :::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

    > ![](https://i.imgur.com/va8wtml.png)

    * 這裡有個問題，如何才能知道 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` 輸出結果
        > 
        > ![](https://i.imgur.com/mdhIEDh.png)

* 完整的 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));
    }
    ```
    > ![](https://i.imgur.com/wEmyHZT.png)

    :::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);
        }
        ```
        > ![](https://i.imgur.com/MJbUOif.png)
        
        :::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 位置在哪)
        
        > ![](https://i.imgur.com/2JueIwy.png)

    2. 由於 dequeue 後，新值放置 Header，需要 sink (下沉) 重新 Heap 

        > ![](https://i.imgur.com/NqMhEyr.png)

    3. 不斷重複 `1.`、`2.` 步驟後，我們就可以得到一個重整過後的升序 Array

        > ![](https://i.imgur.com/QtRPOAC.png)

        :::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 中最大值
        > 
        > ![](https://i.imgur.com/eGLYGw2.png)

        
        ```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));
            }
        }
        ```
        > ![](https://i.imgur.com/ITfuKiM.png)

    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));
            }
        }
        ```
        > ![](https://i.imgur.com/x0oWfNe.png)


    :::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: `資料結構`
