摘要：是穩定的排序，但是它需要額外的空間，時間復雜度為程序這個同上也是兩個步驟，。最壞情況的時間復雜度為但是在實際情況中，通常是排序的最佳選擇。就是有序的完全二叉樹，所有我們要先根據已有的數組來建立一個。最后由后往前形成一個有序數組。

Bubble Sort就不說了，下面簡單總結一個Selection Sort, Insertion Sort, Merge Sort和Quick Sort:

1.Selection Sort:
其實就是每次選出數組中的最小值放在當前位置，然后往后掃，
舉例：
(29, 64, 73, 34, 20)
20, (64, 73, 34, 29)
20, 29, (73, 34, 64)
20, 29, 34, (73, 64)
20, 29, 34, 64, (73)
最差情況下的時間復雜度是Ｏ(n2).
程序：

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                min = arr[j] < arr[min] ? j : min;
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 32, 23, 5, 6, 8, 44};
        selectionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

2.Insertion Sort:
其實就是把每次掃到的這個數，插到前面已經sorted好的數組中去：
舉例：
29, 20, 73, 34, 64
(29), 20, 73, 34, 64
(20, 29), 73, 34, 64
(20, 29, 73), 34, 64
(20, 29, 34, 73), 64
(20, 29, 34, 64, 73)
時間復雜度是Ｏ(n2).
程序：

public class InsertionSort {
    public static void InsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int index = arr[i], j = i;
            while (j > 0 && arr[j - 1] > index) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = index;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 32, 23, 5, 6, 8, 44};
        InsertionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3.Merge Sort:
這個sort分兩個步驟，divide & merge。我們首先要把這個list分成兩個部分，然后對這兩個部分sort，然后把sort后的結果merge起來，只要操作就在于merge，最后就得到最終的結果了。Merge sort是穩定的排序，但是它需要額外的空間，時間復雜度為O(nlogn).
程序：

public class MergeSort {
    public static int[] mergeSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) return arr;
        int mid = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));

        
        return merge(left, right);
        
    }
    
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 32, 23, 5, 6, 8, 44};
        int[] result = mergeSort(arr);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

4.Quick Sort:
這個sort同上也是兩個步驟，divide & merge。不同的是，這個在divide的時候做了有用的操作，把所有小于當前值的數放到左邊，所有大于當前值的數放到右邊，然后merge這兩個部分。Quick Sort最壞情況的時間復雜度為O(n2).但是在實際情況中，quick sort通常是排序的最佳選擇。
程序：

public class QuickSort {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    } 
    
    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) return;
        if (low >= high) return;
        
        int mid = low + (high - low) / 2;
        int pivot = arr[mid];
        
        int i = low, j = high - 1;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if (low < j) {
            quickSort(arr, low, j);
        }
        if (i < high) {
            quickSort(arr, i, high);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 32, 23, 5, 6, 8, 44};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

5.Heap Sort
這個排序看似復雜，其實只要把內部原理弄清楚就一點也不難了。heap就是有序的完全二叉樹，所有我們要先根據已有的數組來建立一個heap。我們知道完全樹的根結點，左子樹，右子樹滿足這樣的特點：left = 2 i(root), right = 2 i + 1。所以我們可以利用這一點，將i, left, right這三個點比較大小，取最大的值作為根結點。如果這個最大值原來就是root，那么我們不需要有任何的改動；如果這個最大值原來是子結點，那么從這個子結點往下，我們還需要逐一比較這個子結點的子結點，找到最大值放在這個子結點的位置，依次類推。
建完樹之后就是要取點了，最大值我們已經確定在index為0的位置，但是對于left,right我們并不知道哪個大哪個小。所以可以先把這個root所在的最大值與最后一個數交換（將最大值存到最后去），然后再比較開先鋒們的大小，大的那個放在根結點處，為當前最大數，依次類推。最后由后往前形成一個有序數組。
程序：

public class HeapSort {
    public static int N;
    //Build a heap
    public static void heapify(int[] arr) {
        N = arr.length - 1;
        //Bottom up, 也只能bottomup，由上往下的話，根結點有時候會不是最優解
        for (int i = N / 2; i >= 0; i--) {
            maxHeap(arr, i);
        }
    }
    //swap the largest element to root
    public static void maxHeap(int[] arr, int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int max = i;
        if (left <= N && arr[left] > arr[i]) {
            max = left;
        }
        if (right <= N && arr[right] > arr[max]) {
            max = right;
        }
        if (max != i) {
            swap(arr, i, max);
            maxHeap(arr, max);
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void heapSort(int[] arr) {
        heapify(arr);
        for (int i = N; i > 0; i--) {
            swap(arr, 0, i);
            N = N - 1;
            maxHeap(arr, 0);
        }
        
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 32, 23, 5, 6, 8, 44};
        heapSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}