2_排序算法（归并、快速）

分治思想

分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

分治和递归很像，分治算法一般都是用递归来实现的。

分治是一种解决问题的处理思想，递归是一种编程技巧。

归并排序 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);
    }

    // 合并数组
    private static void merge(int[] arr, int start, int mid, int end) {
        // 把范围内的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++;
            }
        }
    }

归并排序分为分解和合并两个过程。
分解是将待排序数组从中间分解为两个数组，直到只剩一个元素无法分解。
合并是将两个数组合成一个有序数组。

归并排序是否是稳定排序，取决于merge合并函数的写法。只要在merge过程中不改变相对位置，归并排序就是稳定的排序算法。

归并排序的时间复杂度在任何情况下都是 O(nlogn)，但它在排序过程中需要使用辅助数组，所以它不是原地排序算法。这是归并排序的致命弱点。

时间复杂度：O(nlogn)
空间复杂度：O(n)

快速排序 Quick Sort

分区

public class QuickSort {

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

    // 递归函数
    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);
    }

    // 原地分区函数
    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;
    }
}

快速排序利用了分治和递归思想，选择一个分区点，将小于它的数放在它前面，将大于它的数放在它后面。按照这个过程层层递归。

原地分区算法

快排的核心在于原地分区算法：
通过两个游标 i 和 j ，将 A[p...r-1] 分为三个部分：
(1) A[p...i-1] 的元素小于pivot分区点
(2) A[i...j-1] 的元素大于分区点
(3) A[j...r] 是未处理区域。

最差 / 平均 / 最好时间复杂度：O(n²) / O(nlogn) / O(nlogn)
空间复杂度：O(1)

归并排序和快速排序

归并排序和快速排序都用到了分治和递归思想，它们的区别在于：
(1) 归并排序是由下到上的，先处理子问题，再进行合并；归并排序时间复杂度恒为 O(nlogn)，但是需要额外空间。
(2) 快速排序是由上到下的，先进行分区，再处理子问题；快速排序使用了原地分区算法，避免使用额外空间。