以下是 Java 中常见的五大算法：

1. 排序算法 - 快速排序(Quick Sort)

  • 基本原理：
  • 快速排序是一种分治的排序算法。它的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小。然后分别对这两部分继续进行排序，以达到整个序列有序。
  • 具体来说，它选择一个基准元素(pivot)，通常是数组的第一个、最后一个或者中间位置的元素。然后通过两个指针，一个从数组的开头(left)，一个从数组的末尾(right)，开始扫描数组。从左往右找比基准元素大的元素，从右往左找比基准元素小的元素，然后交换这两个元素。当两个指针相遇时，将基准元素与相遇位置的元素交换。这样，基准元素左边的元素都比它小，右边的元素都比它大。
  • 接着对基准元素左右两边的子数组重复上述过程，直到子数组的长度为 1 或者 0，此时整个数组就有序了。
  • 代码示例：
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;
        while (true) {
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            if (i > j) {
                break;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[low] = arr[j];
        arr[j] = pivot;
        return j;
    }
}
  • 时间复杂度：平均情况下为 ，最坏情况下为 ，不过通过一些优化可以尽量避免最坏情况的出现。
  • 空间复杂度： 最好情况下为 ，最坏情况下为 。

2. 查找算法 - 二分查找(Binary Search)

  • 基本原理：
  • 二分查找适用于已经排好序的数组。它的基本思想是每次比较中间元素与目标元素的值。如果中间元素等于目标元素，则查找成功；如果中间元素大于目标元素，则在中间元素的左边继续查找；如果中间元素小于目标元素，则在中间元素的右边继续查找。不断重复这个过程，直到找到目标元素或者确定目标元素不存在为止。
  • 代码示例：
public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
  • 时间复杂度：，每次查找都能将搜索区间缩小一半。
  • 空间复杂度：，因为只需要几个指针变量来进行操作，不需要额外的数据结构来存储大量的数据。

3. 图算法 - 广度优先搜索(Breadth - First Search，BFS)

  • 基本原理：
  • BFS 是一种用于遍历或搜索图(或树)的算法。它从给定的起始顶点开始，首先访问起始顶点的所有相邻顶点，然后再依次访问这些相邻顶点的相邻顶点，一层一层地向外扩展，直到遍历完整个图或者找到目标顶点。
  • 通常使用队列(Queue)来实现。将起始顶点放入队列，然后不断取出队列头部的顶点，访问它的相邻顶点，并将未访问过的相邻顶点放入队列尾部，直到队列为空。
  • 代码示例(以简单的无向图为例)：
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.List;

class Graph {
    private int V;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        V = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int v, int w) {
        adjList.get(v).add(w);
        adjList.get(w).add(v);
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            List<Integer> neighbors = adjList.get(vertex);
            for (int neighbor : neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}
  • 时间复杂度：对于一个有  个顶点和  条边的图，时间复杂度为 ，因为在最坏情况下，需要访问所有的顶点和边。
  • 空间复杂度：，因为在最坏情况下，需要使用一个布尔数组来记录每个顶点是否被访问，以及一个队列来存储待访问的顶点。

4. 动态规划 - 斐波那契数列(Fibonacci Sequence)计算(使用动态规划优化)

  • 基本原理：
  • 斐波那契数列的定义是：，其中 ，。简单的递归计算斐波那契数列会有大量的重复计算，导致时间复杂度呈指数级增长。
  • 动态规划的思想是通过存储已经计算过的子问题的解，避免重复计算。可以使用一个数组来存储斐波那契数列的值，从最小的子问题(和 )开始逐步计算，直到得到需要的 。
  • 代码示例：
public class FibonacciDP {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        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];
    }
}
  • 时间复杂度：，只需要一次遍历计算数组中的每个元素。
  • 空间复杂度：，因为需要一个长度为  的数组来存储中间结果。不过可以通过优化，只使用两个变量来存储前两个斐波那契数，将空间复杂度降低到 。

5. 字符串匹配算法 - KMP 算法(Knuth - Morris - Pratt)

  • 基本原理：
  • KMP 算法主要用于在一个主字符串中查找一个模式字符串的出现位置。它的核心是利用已经匹配过的部分信息，通过一个前缀函数(也叫 next 数组)来避免不必要的字符比较。
  • 前缀函数(next 数组)记录了模式字符串中每个位置之前的最长公共前缀和后缀的长度。在匹配过程中，当出现不匹配的字符时，不是像简单的暴力匹配算法那样将模式字符串整体后移一位，而是根据 next 数组的值，将模式字符串向右移动合适的位数，从而跳过一些肯定不会匹配的位置，提高匹配效率。
  • 代码示例(计算 next 数组部分)：
public class KMP {
    public static int[] computeNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        int k = -1;
        next[0] = k;
        for (int i = 1; i < m; i++) {
            while (k > -1 && pattern.charAt(k + 1)!= pattern.charAt(i)) {
                k = next[k];
            }
            if (pattern.charAt(k + 1) == pattern.charAt(i)) {
                k++;
            }
            next[i] = k;
        }
        return next;
    }
}
  • 时间复杂度：计算 next 数组的时间复杂度为 ，其中  是模式字符串的长度。在主字符串中进行匹配的时间复杂度为 ，其中  是主字符串的长度。所以总的时间复杂度为 。
  • 空间复杂度：，因为需要一个长度为  的数组来存储 next 数组。