Sorting

摘要：是稳定的排序，但是它需要额外的空间，时间复杂度为程序这个同上也是两个步骤，。最坏情况的时间复杂度为但是在实际情况中，通常是排序的最佳选择。就是有序的完全二叉树，所有我们要先根据已有的数组来建立一个。最后由后往前形成一个有序数组。

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 + " ");
        }
    }
}