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

Bubble Sort就不說了，下面簡單總結(jié)一個(gè)Selection Sort, Insertion Sort, Merge Sort和Quick Sort:

1.Selection Sort:
其實(shí)就是每次選出數(shù)組中的最小值放在當(dāng)前位置，然后往后掃，
舉例：
(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)
最差情況下的時(shí)間復(fù)雜度是Ｏ(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:
其實(shí)就是把每次掃到的這個(gè)數(shù)，插到前面已經(jīng)sorted好的數(shù)組中去：
舉例：
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)
時(shí)間復(fù)雜度是Ｏ(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:
這個(gè)sort分兩個(gè)步驟，divide & merge。我們首先要把這個(gè)list分成兩個(gè)部分，然后對(duì)這兩個(gè)部分sort，然后把sort后的結(jié)果merge起來，只要操作就在于merge，最后就得到最終的結(jié)果了。Merge sort是穩(wěn)定的排序，但是它需要額外的空間，時(shí)間復(fù)雜度為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:
這個(gè)sort同上也是兩個(gè)步驟，divide & merge。不同的是，這個(gè)在divide的時(shí)候做了有用的操作，把所有小于當(dāng)前值的數(shù)放到左邊，所有大于當(dāng)前值的數(shù)放到右邊，然后merge這兩個(gè)部分。Quick Sort最壞情況的時(shí)間復(fù)雜度為O(n2).但是在實(shí)際情況中，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
這個(gè)排序看似復(fù)雜，其實(shí)只要把內(nèi)部原理弄清楚就一點(diǎn)也不難了。heap就是有序的完全二叉樹，所有我們要先根據(jù)已有的數(shù)組來建立一個(gè)heap。我們知道完全樹的根結(jié)點(diǎn)，左子樹，右子樹滿足這樣的特點(diǎn)：left = 2 i(root), right = 2 i + 1。所以我們可以利用這一點(diǎn)，將i, left, right這三個(gè)點(diǎn)比較大小，取最大的值作為根結(jié)點(diǎn)。如果這個(gè)最大值原來就是root，那么我們不需要有任何的改動(dòng)；如果這個(gè)最大值原來是子結(jié)點(diǎn)，那么從這個(gè)子結(jié)點(diǎn)往下，我們還需要逐一比較這個(gè)子結(jié)點(diǎn)的子結(jié)點(diǎn)，找到最大值放在這個(gè)子結(jié)點(diǎn)的位置，依次類推。
建完樹之后就是要取點(diǎn)了，最大值我們已經(jīng)確定在index為0的位置，但是對(duì)于left,right我們并不知道哪個(gè)大哪個(gè)小。所以可以先把這個(gè)root所在的最大值與最后一個(gè)數(shù)交換（將最大值存到最后去），然后再比較開先鋒們的大小，大的那個(gè)放在根結(jié)點(diǎn)處，為當(dāng)前最大數(shù)，依次類推。最后由后往前形成一個(gè)有序數(shù)組。
程序：

public class HeapSort {
    public static int N;
    //Build a heap
    public static void heapify(int[] arr) {
        N = arr.length - 1;
        //Bottom up, 也只能bottomup，由上往下的話，根結(jié)點(diǎn)有時(shí)候會(huì)不是最優(yōu)解
        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 + " ");
        }
    }
}