算法面试突击手册 —— 排序（含快排/归并思想）

一、概念与特点

大白话 + 类比

排序 = 军训按身高排队

教官让全班同学按身高从矮到高排成一列。方式很多：

快速排序：随便抽一个人（pivot），比他矮的站左边，比他高的站右边。左右两边再各自重复这个过程。

归并排序：把队伍不断拆成两半，直到每组只有一个人。然后两组合并时，谁的个子矮谁先出列。

堆排序：所有人先站成一个”优先队列”（大根堆），然后每次弹出最高的放在最后。

Hot 100 不要求手写基础排序，但大量题目用到排序的思想（快速选择、归并、区间合并）。

核心特征（什么时候该想到用它）

特征	说明
第 K 大 / 第 K 小	快速选择 / 堆
合并区间	按起点排序
排序链表	归并排序（O(nlogn), O(1) 空间）
前 K 个高频	桶排序 / 堆
下一个排列	找规律 + 排序尾部

识别信号词

“第 K 个最大”、“前 K 个” → 快速选择 / 堆
“合并”、“区间重叠” → 排序 + 遍历
“排序链表” → 归并
“下一个排列” → 字典序规律
“O(n log n)” → 排序算法

二、应用场景

快速选择模板（找第 K 大）

// 快速选择：平均 O(n)，最坏 O(n²)
int quickSelect(int[] nums, int left, int right, int k) {
    int pivot = nums[left];
    int i = left + 1, j = right;
    while (i <= j) {
        while (i <= j && nums[i] >= pivot) i++; // 大的放左边
        while (i <= j && nums[j] < pivot) j--;
        if (i < j) swap(nums, i, j);
    }
    swap(nums, left, j); // pivot 归位
    if (j == k) return nums[j];
    else if (j < k) return quickSelect(nums, j + 1, right, k);
    else return quickSelect(nums, left, j - 1, k);
}

三、Hot 100 精讲题目

215. Kth Largest Element in an Array 数组中的第K个最大元素

📌 找出数组中第 K 个最大的元素（非排序后的第 K 个）。如 [3,2,1,5,6,4], k=2 → 5

🔍 解题分析

方法一：快速选择

类似快排的分区思想，但不需完全排序。每次 partition 后 pivot 落在其最终位置。
如果 pivot 下标 == n-k（第 K 大 = 第 n-k 小），找到答案。
否则根据大小关系只递归一半。

方法二：小根堆

维护大小为 K 的小根堆，堆顶就是第 K 大。见 14-堆。

✅ 完整 Java 实现

public int findKthLargest(int[] nums, int k) {
    // 第 K 大 = 排序后下标为 n - k 的元素
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

private int quickSelect(int[] nums, int left, int right, int targetIdx) {
    int pivot = nums[left]; // 选最左元素作为 pivot
    int i = left + 1;       // 从左向右扫描
    int j = right;          // 从右向左扫描

    while (i <= j) {
        // 小于等于 pivot 的跳过（放左边）
        while (i <= j && nums[i] <= pivot) i++;
        // 大于 pivot 的跳过（放右边）
        while (i <= j && nums[j] > pivot) j--;

        if (i < j) {
            swap(nums, i, j); // 交换错位的
        }
    }

    // pivot 归位到 j
    swap(nums, left, j);

    if (j == targetIdx) {
        return nums[j];
    } else if (j < targetIdx) {
        return quickSelect(nums, j + 1, right, targetIdx);
    } else {
        return quickSelect(nums, left, j - 1, targetIdx);
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

⏱ 复杂度分析

时间复杂度：平均 O(n)，最坏 O(n²)（可通过随机选 pivot 优化）
空间复杂度：O(log n)（递归栈深度）

💡 记忆口诀

“快排分区不排完，pivot 归位判断往哪追”

56. Merge Intervals 合并区间

📌 合并所有重叠的区间。如 [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

🔍 解题分析

核心思路：

按区间起点排序
遍历，维护当前合并区间的 [start, end]
如果新区间起点 ≤ 当前 end，合并（end 取 max）；否则当前区间写入结果，重置 start/end

类比：就像把一堆时间段的会议排成时间线，重叠的就合并成一个大会议。

✅ 完整 Java 实现

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;

    // 按区间起点升序排序
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

    List<int[]> result = new ArrayList<>();
    int curStart = intervals[0][0];
    int curEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= curEnd) {
            // 重叠：扩展当前区间的右边界
            curEnd = Math.max(curEnd, intervals[i][1]);
        } else {
            // 不重叠：当前区间定型，开始新区间
            result.add(new int[]{curStart, curEnd});
            curStart = intervals[i][0];
            curEnd = intervals[i][1];
        }
    }

    // 别忘了最后一个区间
    result.add(new int[]{curStart, curEnd});

    return result.toArray(new int[result.size()][]);
}

⏱ 复杂度分析

时间复杂度：O(n log n)，排序占主导
空间复杂度：O(n)，结果数组

💡 记忆口诀

“按起点排好队，有重叠就延伸，不重叠就换人”

347. Top K Frequent Elements 前 K 个高频元素

📌 找出出现频率前 K 高的元素。如 [1,1,1,2,2,3], k=2 → [1,2]

🔍 解题分析

三种解法：

堆：HashMap 计数 + 大小为 K 的小根堆，O(nlogk)
桶排序：HashMap 计数 + 以频率为下标的桶数组，O(n)
快速选择：对频率进行 partition

这里展示桶排序（最优 O(n)）和堆见 14-堆。

桶排序思路：频率最大不超过 n，建立 bucket[freq] 存频率为 freq 的元素列表。从高频率往低收集。

✅ 完整 Java 实现

// 桶排序：时间复杂度 O(n)
public int[] topKFrequent(int[] nums, int k) {
    // 1. 统计频率
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }

    // 2. 桶数组：bucket[i] 存频率为 i 的元素
    List<Integer>[] bucket = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        int freq = entry.getValue();
        if (bucket[freq] == null) {
            bucket[freq] = new ArrayList<>();
        }
        bucket[freq].add(entry.getKey());
    }

    // 3. 从高频率往低收集 K 个
    int[] result = new int[k];
    int idx = 0;
    for (int freq = bucket.length - 1; freq >= 0; freq--) {
        if (bucket[freq] != null) {
            for (int num : bucket[freq]) {
                result[idx++] = num;
                if (idx == k) return result;
            }
        }
    }

    return result;
}

⏱ 复杂度分析

时间复杂度：O(n)，桶排序
空间复杂度：O(n)

💡 记忆口诀

“频率做下标倒着取，桶里舀出前 K 个”

148. Sort List 排序链表

📌 对链表进行升序排序，要求 O(n log n) 时间，O(1) 空间。

🔍 解题分析

为什么用归并排序：链表不支持随机访问，快排难实现。归并排序天然适合链表（拆分/合并都是 O(1)）。

核心思路（自底向上归并，O(1) 空间）：

用快慢指针找中点，将链表拆成两半
递归排序两半
合并两个有序链表

这里给出递归归并（O(log n) 递归栈空间），实际面试一般接受这个版本。

✅ 完整 Java 实现

public ListNode sortList(ListNode head) {
    // 递归终止条件
    if (head == null || head.next == null) return head;

    // 1. 快慢指针找中点
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. 从中间断开
    ListNode mid = slow.next;
    slow.next = null;

    // 3. 递归排序左右两半
    ListNode left = sortList(head);
    ListNode right = sortList(mid);

    // 4. 合并两个有序链表
    return merge(left, right);
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    cur.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

⏱ 复杂度分析

时间复杂度：O(n log n)
空间复杂度：O(log n)（递归栈），O(1)（如果用迭代归并）

💡 记忆口诀

“快慢指针拆两半，递归排序再合并”

31. Next Permutation 下一个排列

📌 将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在（已是最大），则重排成最小排列。必须原地修改。如 [1,2,3] → [1,3,2]

🔍 解题分析

核心思路（找规律）：

从右向左找第一对相邻的升序对 nums[i] < nums[i+1]，i 就是”交换位”
在 i 右边找最小但大于 nums[i] 的元素 j
交换 nums[i] 和 nums[j]
将 i 右边的部分反转（从降序变升序，即最小化）

类比：就像翻字典找下一个词。“12354” 的下一个是 “12435”：从右找第一个能变大的位置（3），和右边最小的比它大的数（4）交换，然后把右边排成最小序。

易错点：步骤 4 用反转而不是排序，因为交换后 i 右边肯定是降序的，反转 O(n) 比排序 O(nlogn) 快。

✅ 完整 Java 实现

public void nextPermutation(int[] nums) {
    int n = nums.length;

    // 1. 从右向左找第一个 nums[i] < nums[i+1] 的位置
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    // 2. 如果找到了（不是完全降序）
    if (i >= 0) {
        // 在 i 右边找最小但大于 nums[i] 的数
        int j = n - 1;
        while (j > i && nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
    }

    // 3. 反转 i 右边的部分（降序变升序）
    reverse(nums, i + 1, n - 1);
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        swap(nums, start, end);
        start++;
        end--;
    }
}

⏱ 复杂度分析

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

💡 记忆口诀

“从右找第一个能变大的位，交换后右边反转最小化”

🔜 上一章：06-二分查找 | 下一章：08-链表

算法手册 07 排序

算法面试突击手册 —— 排序（含快排/归并思想）

一、概念与特点

大白话 + 类比

核心特征（什么时候该想到用它）

识别信号词

二、应用场景

快速选择模板（找第 K 大）

三、Hot 100 精讲题目

215. Kth Largest Element in an Array 数组中的第K个最大元素

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

56. Merge Intervals 合并区间

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

347. Top K Frequent Elements 前 K 个高频元素

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

148. Sort List 排序链表

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

31. Next Permutation 下一个排列

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀