分治思想

分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決。小的子問題解決了，大問題也就解決了。

分治和遞歸很像，分治算法一般都是用遞歸來實現(xiàn)的。

分治是一種解決問題的處理思想，遞歸是一種編程技巧。

歸并排序 Merge Sort

public class MergeSort {
    public static int[] assistArr;
    
    // 歸并排序
    public static void sort(int[] arr) {
        assistArr = new int[arr.length];
        assistSort(arr, 0, arr.length - 1);
    }

    // 遞歸過程
    private static void assistSort(int[] arr, int start, int end) {
        if (end - start < 1) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        assistSort(arr, start, mid);
        assistSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    // 合并數(shù)組
    private static void merge(int[] arr, int start, int mid, int end) {
        // 把范圍內(nèi)的arr復制到assistArr中
        if (end + 1 - start >= 0) {
            System.arraycopy(arr, start, assistArr, start, end + 1 - start);
        }
        int curr = start;
        int left = start;
        int right = mid + 1;
        while (left <= mid && right <= end) {
            if (assitArr[left] <= assitArr[right]) {
                nums[curr] = assitArr[left];
                left++;
            } else {
                nums[curr] = assitArr[right];
                right++;
            }
            curr++;
        }
        if (left <= mid) {
            for (; left <= mid; left++) {
                nums[curr] = assitArr[left];
                curr++;
            }
        }
        if (right <= end) {
            for (; right <= end; right++) {
                nums[curr] = assitArr[right];
                curr++;
            }
        }
    }

歸并排序分為分解和合并兩個過程。
分解是將待排序數(shù)組從中間分解為兩個數(shù)組，直到只剩一個元素無法分解。
合并是將兩個數(shù)組合成一個有序數(shù)組。

歸并排序是否是穩(wěn)定排序，取決于merge合并函數(shù)的寫法。只要在merge過程中不改變相對位置，歸并排序就是穩(wěn)定的排序算法。

歸并排序的時間復雜度在任何情況下都是 O(nlogn)，但它在排序過程中需要使用輔助數(shù)組，所以它不是原地排序算法。這是歸并排序的致命弱點。

時間復雜度：O(nlogn)
空間復雜度：O(n)

快速排序 Quick Sort

分區(qū)

public class QuickSort {

    public static void sort(int[] arr) {
        recursionSort(arr, 0, arr.length - 1);
    }

    // 遞歸函數(shù)
    private static void recursionSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(arr, start, end);
        recursionSort(arr, start, pivot - 1);
        recursionSort(arr, pivot + 1, end);
    }

    // 原地分區(qū)函數(shù)
    private static int partition(int[] arr, int start, int end) {
        int pivot = arr[end];
        int i = start;
        for (int j = start; j < end; j++) {
            if (arr[j] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        arr[end] = arr[i];
        arr[i] = pivot;
        return i;
    }
}

快速排序利用了分治和遞歸思想，選擇一個分區(qū)點，將小于它的數(shù)放在它前面，將大于它的數(shù)放在它后面。按照這個過程層層遞歸。

原地分區(qū)算法

快排的核心在于原地分區(qū)算法：
通過兩個游標 i 和 j ，將 A[p...r-1] 分為三個部分：
(1) A[p...i-1] 的元素小于pivot分區(qū)點
(2) A[i...j-1] 的元素大于分區(qū)點
(3) A[j...r] 是未處理區(qū)域。

最差 / 平均 / 最好 時間復雜度：O(n²) / O(nlogn) / O(nlogn)
空間復雜度：O(1)

歸并排序 和 快速排序

歸并排序 和 快速排序

歸并排序和快速排序都用到了分治和遞歸思想，它們的區(qū)別在于：
(1) 歸并排序是由下到上的，先處理子問題，再進行合并；歸并排序時間復雜度恒為 O(nlogn)，但是需要額外空間。
(2) 快速排序是由上到下的，先進行分區(qū)，再處理子問題；快速排序使用了原地分區(qū)算法，避免使用額外空間。