排序算法：快排、归并、堆排

这一课你将能做到

1. 手写快速排序、归并排序、堆排序
2. 说出三种排序的稳定性、复杂度和适用场景
3. 在判题中根据数据特点选择最优排序

为什么要学

排序是算法面试的「必考题」，也是实际开发中最常用的操作。Java 的 Arrays.sort() 底层就是快排（基本类型）和归并（对象类型）。不会手写排序，面试官会觉得你基础不牢。

人话：排序就像整理扑克牌。快排是「挑个基准，大的放右边，小的放左边，递归整理」；归并是「分成两堆，分别理好，再合并」；堆排是「建个大顶堆，每次取最大的放最后」。

先建立图像

快排:  [3,6,1,8,2,9,4]
        基准=3
        [1,2] 3 [6,8,9,4]   ← 分区
        递归左右

归并:  [3,6,1,8] [2,9,4]
        [3,6] [1,8] [2,9] [4]
        [3,6] [1,8] [2,4,9]
        [1,3,6,8] [2,4,9]
        [1,2,3,4,6,8,9]

堆排:      9
          / \
         6   8
        / \ /
       3  2 1
       每次取堆顶(9)，调整堆

跟着做

步骤 1：快速排序

public class Main {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[left + (right - left) / 2]; // 中点作基准
        int i = left, j = right;
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            if (i <= j) {
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
                i++; j--;
            }
        }
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        quickSort(arr, 0, arr.length - 1);
        for (int x : arr) System.out.print(x + " "); // 1 2 3 5 8 9
    }
}

平均 O(n log n)，最坏 O(n²)（已排序数组选第一个元素作基准）。不稳定。

步骤 2：归并排序

public class Main {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, temp.length);
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        mergeSort(arr, 0, arr.length - 1);
        for (int x : arr) System.out.print(x + " ");
    }
}