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

这一课你将能做到

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

稳定 O(n log n)，需要 O(n) 额外空间。适合链表排序。

步骤 3：堆排序

public class Main {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 逐个取堆顶
        for (int i = n - 1; i > 0; i--) {
            int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
            heapify(arr, n, largest);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        heapSort(arr);
        for (int x : arr) System.out.print(x + " ");
    }
}

O(n log n)，原地排序，不稳定。适合 Top K 问题。

步骤 4：计数排序（非比较排序）

public class Main {
    public static void countingSort(int[] arr, int maxVal) {
        int[] count = new int[maxVal + 1];
        for (int num : arr) count[num]++;
        
        int idx = 0;
        for (int i = 0; i <= maxVal; i++) {
            while (count[i]-- > 0) {
                arr[idx++] = i;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr, 8);
        for (int x : arr) System.out.print(x + " "); // 1 2 2 3 3 4 8
    }
}

O(n + k)，k 是数值范围。适合范围小、重复多的数据，如年龄排序、分数统计。

步骤 5：Java 内置排序

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        // 基本类型：双轴快排（Dual-Pivot Quicksort）
        int[] arr1 = {5, 2, 8, 1, 9};
        Arrays.sort(arr1);
        
        // 对象类型：TimSort（归并+插入）
        Integer[] arr2 = {5, 2, 8, 1, 9};
        Arrays.sort(arr2, Comparator.reverseOrder()); // 降序
        
        // 自定义排序
        String[] words = {"apple", "banana", "kiwi"};
        Arrays.sort(words, (a, b) -> a.length() - b.length()); // 按长度
    }
}

讲清楚要点

1. 稳定性：归并稳定，快排和堆排不稳定。稳定性指相等元素的相对顺序是否保持。
2. 复杂度对比：快排平均 O(n log n) 最坏 O(n²)；归并稳定 O(n log n)；堆排稳定 O(n log n)。
3. 空间复杂度：快排 O(log n)（递归栈）；归并 O(n)（临时数组）；堆排 O(1)（原地）。
4. 实际选择：基本类型用 Arrays.sort()；对象类型用 Arrays.sort() 或 Collections.sort()；Top K 用堆；链表排序用归并。

你可能会懵的地方

• 快排最坏情况怎么避免？ 随机选基准，或三数取中。Java 的双轴快排做了大量优化，实际很难触发最坏情况。

• 归并排序为什么稳定？ 合并时 arr[i] <= arr[j]，相等时先取左边的，保持原顺序。

• 堆排为什么实际用得少？ 虽然 O(n log n) 且原地，但缓存不友好（跳跃访问），实际比快排慢 2-3 倍。

• TimSort 是什么？ Java/Python 默认对象排序算法。检测已有序的「run」，用归并合并，再插入小片段。实际数据越有序越快。

• 排序能并行吗？ Java 8+ 的 Arrays.parallelSort() 用 Fork/Join 框架并行归并，大数据量（>10^5）时更快。

错法对照

错法	问题	正解
快排基准选第一个元素	已排序数组退化成 O(n²)	随机选或三数取中
归并合并时 arr[i] < arr[j]	相等元素顺序颠倒，不稳定	用 <= 保持稳定性
堆排建堆从 0 开始	遗漏非叶子节点	从 n/2-1 倒序建堆
递归排序不处理边界	栈溢出或死循环	加 if (left >= right) return;
在快排中用大量额外空间	失去原地排序优势	用指针交换，不新开数组

卡点急救

1. 快排死循环：检查分区后 i 和 j 是否都移动了，确保 i <= j 时才交换。
2. 归并结果不对：检查 System.arraycopy 的偏移量，应该是 left 不是 0。
3. 堆排输出乱序：检查 heapify 的递归调用，确保 largest != i 时才交换并继续调整。

面试常问

• 快排和归并的区别？ 快排是「分而治之」，原地排序但不稳定；归并是「分而治之+合并」，稳定但需要 O(n) 空间。快排平均更快，归并适合链表和外部排序。

• 堆排为什么是 O(n log n)？ 建堆 O(n)，每次取堆顶调整 O(log n)，共 n 次，总 O(n log n)。建堆是 O(n) 不是 O(n log n)，因为大部分节点高度很小。

• Java 的 Arrays.sort() 用什么算法？ 基本类型用双轴快排（Dual-Pivot Quicksort）；对象类型用 TimSort（归并+插入）。都是高度优化的工程实现。

自测三问

1. 快排的最坏时间复杂度是什么？如何避免？
2. 归并排序为什么是稳定的？
3. 堆排序的空间复杂度是多少？为什么？

小结一句话

快排、归并、堆排是三大经典排序，各有优劣；理解它们的原理和适用场景，才能在面试和实战中游刃有余。

延伸

• Java 官方文档：Arrays.sort
• 下一课：搜索算法——二分查找与深度/广度优先搜索。