🔥 常见算法分类 + Java实现

1. 排序算法 (Sorting)

1.1 冒泡排序 (Bubble Sort)

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr) {
    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 tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

1.2 选择排序 (Selection Sort)

1
2
3
4
5
6
7
8
9
public static void selectionSort(int[] arr) {
    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 tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp;
    }
}

1.3 插入排序 (Insertion Sort)

1
2
3
4
5
6
7
8
9
10
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

1.4 归并排序 (Merge Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void mergeSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

private static void merge(int[] arr, int l, int mid, int r) {
    int[] tmp = new int[r - l + 1];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];
    for (i = 0; i < tmp.length; i++) arr[l + i] = tmp[i];
}

1.5 快速排序 (Quick Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void quickSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}

private static int partition(int[] arr, int l, int r) {
    int pivot = arr[r], i = l - 1;
    for (int j = l; j < r; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i+1]; arr[i+1] = arr[r]; arr[r] = tmp;
    return i + 1;
}

2. 查找算法 (Searching)

1
2
3
4
5
6
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

2.2 二分查找 (Binary Search)（数组有序）

1
2
3
4
5
6
7
8
9
10
public static int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

3. 双指针算法 (Two Pointers)

3.1 反转数组

1
2
3
4
5
6
7
public static void reverse(int[] arr) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp;
        l++; r--;
    }
}

3.2 三数之和 (LeetCode 15)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i+1, r = nums.length-1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    return res;
}

4. 动态规划 (Dynamic Programming)

4.1 斐波那契数列

1
2
3
4
5
6
7
public static int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

4.2 爬楼梯 (LeetCode 70)

1
2
3
4
5
6
7
8
9
public static int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = a + b;
        a = b; b = tmp;
    }
    return b;
}

4.3 最长公共子序列 (LCS)

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

5. 贪心算法 (Greedy)

5.1 跳跃游戏 (LeetCode 55)

1
2
3
4
5
6
7
8
public static boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}

6. 分治算法 (Divide & Conquer)

6.1 归并排序 (见上)

6.2 快速排序 (见上)

7. 回溯算法 (Backtracking)

7.1 全排列 (LeetCode 46)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

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

8. 图算法 (Graph Algorithms)

8.1 BFS（最短路径）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    q.add(start); visited.add(start);
    while (!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");
        for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(nei)) {
                visited.add(nei);
                q.add(nei);
            }
        }
    }
}

8.2 DFS

1
2
3
4
5
6
7
8
public static void dfs(Map<Integer, List<Integer>> graph, int start, Set<Integer> visited) {
    if (visited.contains(start)) return;
    visited.add(start);
    System.out.print(start + " ");
    for (int nei : graph.getOrDefault(start, new ArrayList<>())) {
        dfs(graph, nei, visited);
    }
}

8.3 Dijkstra 最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] dijkstra(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    boolean[] visited = new boolean[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
        }
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist;
}