Java算法
2025/8/27大约 4 分钟
Java算法
原文链接：https://www.yuque.com/yopai/pp6bv5/xqfzn5tio8k1nnvg
查找算法
基本查找
顺序遍历，最简单但效率低：
int[] arr = {5, 2, 8, 1, 9, 3};
int target = 8;
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
index = i;
break;
}
}
System.out.println("索引：" + index); // 2二分查找
适用于有序数组，效率高：
┌─────────────────────────────────────────────────────────────┐
│ 二分查找执行流程 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 数组：[1, 3, 5, 7, 9, 11, 13] 查找 7 │
│ │
│ 第1轮：min=0, max=6, mid=3 → arr[3]=7 == 7 → 找到！ │
│ │
│ 如果 arr[mid] > target → max = mid - 1（向左找） │
│ 如果 arr[mid] < target → min = mid + 1（向右找） │
│ │
└─────────────────────────────────────────────────────────────┘int[] arr = {1, 3, 5, 7, 9, 11, 13};
int target = 7;
int min = 0, max = arr.length - 1, index = -1;
while (min <= max) {
int mid = (min + max) / 2;
if (arr[mid] == target) {
index = mid;
break;
} else if (arr[mid] > target) {
max = mid - 1;
} else {
min = mid + 1;
}
}
System.out.println("索引：" + index); // 3Hash 查找
利用 HashMap 实现 O(1) 查找：
int[] arr = {5, 12, 8, 3, 9, 20};
HashMap<Integer, Integer> map = new HashMap<>();
// 建立映射：值 → 索引
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
// O(1) 查找
int target = 8;
if (map.containsKey(target)) {
System.out.println("索引：" + map.get(target));
} else {
System.out.println("未找到");
}排序算法
冒泡排序
相邻比较，大的往后放：
┌─────────────────────────────────────────────────────────────┐
│ 冒泡排序原理 │
├─────────────────────────────────────────────────────────────┤
│ │
│ [5, 3, 8, 1, 2] │
│ │
│ 第1轮：5>3✓交换 → [3, 5, 8, 1, 2] │
│ 5<8不换 → [3, 5, 8, 1, 2] │
│ 8>1✓交换 → [3, 5, 1, 8, 2] │
│ 8>2✓交换 → [3, 5, 1, 2, 8] ← 最大值到末尾 │
│ │
│ 第2轮：[3, 5, 1, 2, 8] → [3, 1, 5, 2, 8] │
│ 第3轮：[3, 1, 5, 2, 8] → [3, 1, 2, 5, 8] │
│ 第4轮：[3, 1, 2, 5, 8] → [1, 2, 3, 5, 8] │
│ │
└─────────────────────────────────────────────────────────────┘int[] arr = {5, 3, 8, 1, 2};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]选择排序
每轮选最小，放到前面：
┌─────────────────────────────────────────────────────────────┐
│ 选择排序原理 │
├─────────────────────────────────────────────────────────────┤
│ │
│ [5, 3, 8, 1, 2] │
│ │
│ 第1轮：最小值 1，和位置0交换 → [1, 3, 8, 5, 2] │
│ 第2轮：最小值 2，和位置1交换 → [1, 2, 8, 5, 3] │
│ 第3轮：最小值 3，和位置2交换 → [1, 2, 3, 5, 8] │
│ 第4轮：最小值 5，位置不变 → [1, 2, 3, 5, 8] │
│ │
└─────────────────────────────────────────────────────────────┘int[] arr = {5, 3, 8, 1, 2};
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]插入排序
像整理扑克牌一样，把元素插入到已排序部分：
┌─────────────────────────────────────────────────────────────┐
│ 插入排序原理 │
├─────────────────────────────────────────────────────────────┤
│ │
│ [5, 3, 8, 1, 2] 已排序：[5] │
│ │
│ 第1轮：取出3，插入[5] → [3, 5, 8, 1, 2] │
│ 第2轮：取出8，插入[3,5] → [3, 5, 8, 1, 2] │
│ 第3轮：取出1，插入[3,5,8] → [1, 3, 5, 8, 2] │
│ 第4轮：取出2，插入[1,3,5,8] → [1, 2, 3, 5, 8] │
│ │
└─────────────────────────────────────────────────────────────┘int[] arr = {5, 3, 8, 1, 2};
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]快速排序
选基准，分左右，递归处理：
┌─────────────────────────────────────────────────────────────┐
│ 快速排序原理 │
├─────────────────────────────────────────────────────────────┤
│ │
│ [5, 3, 8, 1, 2] 选基准 5 │
│ │
│ 第一轮分区： │
│ 从右找比5小的：2 < 5 → arr[0]=2 │
│ 从左找比5大的：3不满足，8>5 → arr[2]=8 │
│ 交换：[2, 3, 8, 1, 5] │
│ 继续...最终 arr[2]=5 归位 │
│ 左：[2, 3] 右：[1] │
│ │
│ 递归处理左右两部分 │
│ │
└─────────────────────────────────────────────────────────────┘public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
// 调用
int[] arr = {5, 3, 8, 1, 2};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]递归
方法调用自己，必须有收敛条件：
┌─────────────────────────────────────────────────────────────┐
│ 递归执行流程 │
├─────────────────────────────────────────────────────────────┤
│ │
│ factorial(5) = 5 * factorial(4) │
│ = 5 * 4 * factorial(3) │
│ = 5 * 4 * 3 * factorial(2) │
│ = 5 * 4 * 3 * 2 * factorial(1) │
│ = 5 * 4 * 3 * 2 * 1 = 120 │
│ │
│ 收敛条件：n == 1 时返回 1 │
│ 如果没有收敛条件，会栈溢出（StackOverflowError） │
│ │
└─────────────────────────────────────────────────────────────┘阶乘
public static int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}斐波那契数列
// 1, 1, 2, 3, 5, 8, 13, 21...
public static int fibonacci(int n) {
if (n <= 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}求数组最大值
public static int getMax(int[] arr, int left, int right) {
if (left == right) return arr[left];
int mid = (left + right) / 2;
int leftMax = getMax(arr, left, mid);
int rightMax = getMax(arr, mid + 1, right);
return Math.max(leftMax, rightMax);
}算法复杂度
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 基本查找 | O(n) | O(1) | - |
| 二分查找 | O(log n) | O(1) | - |
| 冒泡排序 | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 |
┌─────────────────────────────────────────────────────────────┐
│ 时间复杂度对比 │
├─────────────────────────────────────────────────────────────┤
│ │
│ O(1) 常数 ────── 最高效 │
│ O(log n) 对数 │
│ O(n) 线性 │
│ O(n log n) 线性对数 │
│ O(n²) 平方 ────── 最低效 │
│ │
│ n=1000 时的比较： │
│ O(1) = 1 次 │
│ O(log n) ≈ 10 次 │
│ O(n) = 1000 次 │
│ O(n log n) ≈ 10000 次 │
│ O(n²) = 1000000 次 │
│ │
└─────────────────────────────────────────────────────────────┘总结
┌─────────────────────────────────────────────────────────────┐
│ Java 算法核心要点 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 查找算法： │
│ - 基本查找：顺序遍历 O(n) │
│ - 二分查找：有序数组 O(log n) │
│ - Hash 查找：HashMap O(1) │
│ │
│ 排序算法： │
│ - 冒泡/选择/插入：O(n²)，适合小数据 │
│ - 快速排序：O(n log n)，大数据常用 │
│ │
│ 递归：方法调用自己，必须有收敛条件 │
│ │
│ 复杂度：时间复杂度从低到高 │
│ O(1) < O(log n) < O(n) < O(n log n) < O(n²) │
│ │
└─────────────────────────────────────────────────────────────┘