算法母题30道（第6篇）：搜索与排序（26-30）

系列说明：本系列共6篇文章，涵盖30道经典算法母题，使用Java实现
适用场景：算法学习、面试准备、编程能力提升

---

📋 30道算法母题总览

第1篇：数组与字符串基础（1-5）

1. 两数之和
2. 三数之和
3. 盛最多水的容器
4. 接雨水
5. 最长无重复字符子串

第2篇：链表操作（6-10）

6. 反转链表
7. 合并两个有序链表
8. 链表中倒数第k个节点
9. 判断链表是否有环
10. 合并K个有序链表

第3篇：栈与队列（11-15）

11. 有效的括号
12. 用栈实现队列
13. 最小栈
14. 滑动窗口最大值
15. 每日温度

第4篇：二叉树遍历（16-20）

16. 二叉树的前序遍历
17. 二叉树的中序遍历
18. 二叉树的后序遍历
19. 二叉树的层序遍历
20. 二叉树的最大深度

第5篇：动态规划（21-25）

21. 爬楼梯
22. 最长递增子序列
23. 最长公共子序列
24. 背包问题（0-1背包）
25. 编辑距离

第6篇：搜索与排序（26-30）⭐ 本篇

26. 二分查找
27. 快速排序
28. 归并排序
29. 岛屿数量（DFS/BFS）
30. 全排列（回溯）

---

第26题：二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

💡 解题思路

二分查找：

1. 初始化左边界 left = 0，右边界 right = n - 1
2. 当 left <= right 时循环
3. 计算中间位置 mid = left + (right - left) / 2
4. 比较 nums[mid] 与 target，调整边界

日常应用

• 字典查找
• 数据库索引查询
• Git bisect 定位 bug
• 游戏数值范围查询

💻 Java实现代码

public class BinarySearch {
    
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

️ 复杂度分析

• 时间复杂度：O(log n) - 每次将搜索范围减半
• 空间复杂度：O(1) - 只使用常数额外空间

---

第27题：快速排序

题目描述

给你一个整数数组 nums，请你将该数组升序排列。

示例：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

💡 解题思路

快速排序：

1. 选择基准（Pivot）：通常选择最后一个元素
2. 分区：小于基准的放左边，大于基准的放右边
3. 递归排序：对左右两部分递归执行快速排序

🎯 日常应用

• 数据库排序
• 搜索引擎结果排序
• 文件系统文件列表排序
• 数据分析预处理

💻 Java实现代码

public class QuickSort {
    
    public void sort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        quickSort(nums, 0, nums.length - 1);
    }
    
    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(nums, left, right);
            quickSort(nums, left, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, right);
        }
    }
    
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left - 1;
        
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                i++;
                swap(nums, i, j);
            }
        }
        
        swap(nums, i + 1, right);
        return i + 1;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

⏱️ 复杂度分析

• 时间复杂度：平均 O(n log n)，最坏 O(n²)
• 空间复杂度：O(log n) - 递归调用栈
• 优化：随机化基准选择避免最坏情况

---

第28题：归并排序

📝 题目描述

给你一个整数数组 nums，请你将该数组升序排列。

示例：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

💡 解题思路

归并排序：

1. 分解：将数组从中间分成两半
2. 解决：递归地对两半分别排序
3. 合并：将两个有序数组合并成一个有序数组

日常应用

• 外部排序（大文件）
• 链表排序
• 逆序对计算
• 需要稳定排序的场景

💻 Java实现代码

public class MergeSort {
    
    public void sort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        mergeSort(nums, 0, nums.length - 1);
    }
    
    private void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
    
    private void merge(int[] nums, 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) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        
        for (int p = 0; p < temp.length; p++) {
            nums[left + p] = temp[p];
        }
    }
}

️ 复杂度分析

• 时间复杂度：O(n log n) - 最坏、平均、最好都是
• 空间复杂度：O(n) - 需要临时数组
• 特点：稳定排序

---

第29题：岛屿数量

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

示例：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

💡 解题思路

DFS/BFS：

1. 遍历网格中的每个格子
2. 如果遇到陆地（‘1’），岛屿数量 +1
3. 使用 DFS 或 BFS 将相连的陆地标记为已访问（改为 ‘0’）
4. 继续遍历，直到所有格子都访问过

🎯 日常应用

• 图像处理：连通区域检测
• 地图分析：地理区域划分
• 游戏开发：地图生成
• 社交网络：连通分量分析

💻 Java实现代码

public class NumberOfIslands {
    
    // DFS 解法
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || 
            col < 0 || col >= grid[0].length || 
            grid[row][col] == '0') {
            return;
        }
        
        grid[row][col] = '0';
        
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(m × n) - 每个格子最多访问一次
• 空间复杂度：O(m × n) - 递归调用栈的最坏情况

---

第30题：全排列

题目描述

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

示例：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

💡 解题思路

回溯法：

1. 维护一个路径列表 path
2. 使用 used 数组标记已使用的数字
3. 遍历选择列表，做出选择，递归，撤销选择（回溯）

日常应用

• 密码破解：穷举所有可能的密码
• 组合优化：任务调度、路径规划
• 游戏AI：搜索所有可能的走法
• 测试用例：生成所有测试组合

Java实现代码

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), used, result);
        return result;
    }
    
    private void backtrack(int[] nums, List<Integer> path, 
                          boolean[] used, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            
            path.add(nums[i]);
            used[i] = true;
            
            backtrack(nums, path, used, result);
            
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

️ 复杂度分析

• 时间复杂度：O(n × n!) - 共有 n! 个排列
• 空间复杂度：O(n) - 递归调用栈和辅助数组

---

系列总结

30道算法母题知识体系

算法母题30道
── 数组与字符串（1-5）
│   ├── 哈希表技巧（两数之和）
│   ├── 双指针技巧（三数之和、盛水容器）
│   └── 滑动窗口（最长无重复子串）
│
├── 链表操作（6-10）
│   ├── 指针操作（反转、合并）
│   ├── 快慢指针（倒数第k个、判环）
│   └── 优先队列（合并K个链表）
│
├── 栈与队列（11-15）
│   ├── 栈的应用（括号匹配、最小栈）
│   ├── 单调栈/队列（滑动窗口、每日温度）
│   └── 数据结构设计（栈实现队列）
│
├── 二叉树遍历（16-20）
│   ├── DFS遍历（前序、中序、后序）
│   ├── BFS遍历（层序遍历）
│   └── 树的高度计算
│
├── 动态规划（21-25）
│   ├── 一维DP（爬楼梯、LIS）
│   ├── 二维DP（LCS、编辑距离）
│   └── 背包问题（0-1背包）
│
└── 搜索与排序（26-30）
    ├── 二分查找
    ├── 分治排序（快排、归并）
    ├── 图遍历（DFS/BFS）
    └── 回溯算法（全排列）

核心算法技巧总结

技巧	适用场景	代表题目
哈希表	快速查找、去重	两数之和
双指针	数组、链表遍历	三数之和、盛水容器
滑动窗口	连续子数组/子串	最长无重复子串、滑动窗口最大值
快慢指针	链表操作	倒数第k个、判环
单调栈/队列	最值问题	每日温度、滑动窗口最大值
DFS/BFS	树、图遍历	二叉树遍历、岛屿数量
动态规划	最优化问题	爬楼梯、背包问题
回溯	排列组合	全排列
分治	排序、查找	快速排序、归并排序

学习建议

1. 循序渐进：从简单到复杂，逐步掌握
2. 动手实践：每道题都要自己实现
3. 总结模板：提炼通用解题框架
4. 反复复习：定期回顾巩固
5. 拓展应用：思考实际应用场景

---

🎉 系列完结

恭喜您完成了30道经典算法母题的学习！

这30道题涵盖了算法面试中最核心的知识点，掌握了这些母题，您就能应对大部分的算法面试题。

如果觉得这个系列对您有帮助，欢迎：

• 👍 点赞支持
• 💬 留言讨论
• ⭐ 收藏备用
• 📢 分享给需要的朋友

有任何算法问题，欢迎在评论区交流！