什么是算法

算法是解决特定问题的一系列步骤，是计算机科学的核心。好的算法应该具有正确性、可读性、健壮性和高效性。

算法特性

• 正确性：能够正确解决问题
• 可读性：代码清晰易懂
• 健壮性：能够处理异常情况
• 高效性：时间和空间复杂度合理

复杂度分析

• 时间复杂度：算法执行时间随输入规模增长的变化
• 空间复杂度：算法执行过程中所需存储空间

排序算法

1. 冒泡排序（Bubble Sort）

基本思想

• 相邻元素比较，大的向后移动
• 每一轮将最大值"冒泡"到末尾
• 重复n-1轮完成排序

Java实现

public class BubbleSort {
    
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // 如果没有交换，说明已经有序
            if (!swapped) {
                break;
            }
        }
    }
    
    // 优化版本：记录最后一次交换位置
    public static void bubbleSortOptimized(int[] arr) {
        int n = arr.length;
        int lastExchangeIndex = 0;
        int sortBorder = n - 1;
        
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            
            for (int j = 0; j < sortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                    lastExchangeIndex = j;
                }
            }
            
            sortBorder = lastExchangeIndex;
            if (!swapped) {
                break;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        bubbleSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

时间复杂度

• 最好情况：O(n) - 已经有序
• 最坏情况：O(n²) - 完全逆序
• 平均情况：O(n²)

空间复杂度

• O(1) - 只需要常数个额外空间

2. 选择排序（Selection Sort）

基本思想

• 每次选择未排序部分的最小值
• 与未排序部分的第一个元素交换
• 重复n-1次完成排序

Java实现

public class SelectionSort {
    
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            // 找到未排序部分的最小值
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 交换最小值到正确位置
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        selectionSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

时间复杂度

• 最好情况：O(n²)
• 最坏情况：O(n²)
• 平均情况：O(n²)

空间复杂度

• O(1)

3. 插入排序（Insertion Sort）

基本思想

• 将数组分为已排序和未排序两部分
• 从未排序部分取一个元素插入到已排序部分的正确位置
• 重复直到所有元素都排序完成

Java实现

public class InsertionSort {
    
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // 将比key大的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            arr[j + 1] = key;
        }
    }
    
    // 二分查找优化版本
    public static void insertionSortWithBinarySearch(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int insertPos = binarySearch(arr, 0, i - 1, key);
            
            // 移动元素
            for (int j = i; j > insertPos; j--) {
                arr[j] = arr[j - 1];
            }
            
            arr[insertPos] = key;
        }
    }
    
    private static int binarySearch(int[] arr, int left, int right, int key) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] <= key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        insertionSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

时间复杂度

• 最好情况：O(n) - 已经有序
• 最坏情况：O(n²) - 完全逆序
• 平均情况：O(n²)

空间复杂度

• O(1)

4. 快速排序（Quick Sort）

基本思想

• 选择基准元素（pivot）
• 将小于基准的元素放在左边，大于基准的元素放在右边
• 递归对左右两部分进行排序

Java实现

public class QuickSort {
    
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    private 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[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    // 三数取中法选择基准
    private static int partitionOptimized(int[] arr, int low, int high) {
        // 选择中间元素作为基准
        int mid = low + (high - low) / 2;
        swap(arr, mid, high);
        
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 随机选择基准
    private static int partitionRandom(int[] arr, int low, int high) {
        int randomIndex = low + (int) (Math.random() * (high - low + 1));
        swap(arr, randomIndex, high);
        
        return partition(arr, low, high);
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        quickSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

时间复杂度

• 最好情况：O(n log n)
• 最坏情况：O(n²) - 已经有序或逆序
• 平均情况：O(n log n)

空间复杂度

• O(log n) - 递归调用栈深度

5. 归并排序（Merge Sort）

基本思想

• 将数组分成两半，递归排序
• 将两个有序数组合并成一个有序数组
• 分治思想的典型应用

Java实现

public class MergeSort {
    
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }
    
    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            // 递归排序左半部分
            mergeSort(arr, left, mid);
            // 递归排序右半部分
            mergeSort(arr, mid + 1, right);
            
            // 合并两个有序数组
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        // 创建临时数组
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        // 复制数据到临时数组
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }
        
        // 合并两个有序数组
        int i = 0, j = 0, k = left;
        
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        
        // 复制剩余元素
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    
    // 自底向上的归并排序（迭代版本）
    public static void mergeSortIterative(int[] arr) {
        int n = arr.length;
        
        for (int size = 1; size < n; size = size * 2) {
            for (int left = 0; left < n - size; left += size * 2) {
                int mid = left + size - 1;
                int right = Math.min(left + size * 2 - 1, n - 1);
                merge(arr, left, mid, right);
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        mergeSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

时间复杂度

• 最好情况：O(n log n)
• 最坏情况：O(n log n)
• 平均情况：O(n log n)

空间复杂度

• O(n) - 需要额外的数组空间

6. 堆排序（Heap Sort）

基本思想

• 构建最大堆
• 依次取出堆顶元素（最大值）
• 重新调整堆结构

Java实现

public class HeapSort {
    
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 依次取出堆顶元素
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶元素到末尾
            swap(arr, 0, i);
            
            // 重新调整堆
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        // 如果左子节点大于根节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // 如果右子节点大于最大值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // 如果最大值不是根节点
        if (largest != i) {
            swap(arr, i, largest);
            
            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        heapSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

时间复杂度

• 最好情况：O(n log n)
• 最坏情况：O(n log n)
• 平均情况：O(n log n)

空间复杂度

• O(1) - 原地排序

查找算法

1. 二分查找（Binary Search）

基本思想

• 在有序数组中查找目标值
• 每次比较中间元素，缩小搜索范围
• 时间复杂度O(log n)

Java实现

public class BinarySearch {
    
    // 迭代版本
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; // 未找到
    }
    
    // 递归版本
    public static int binarySearchRecursive(int[] arr, int target) {
        return binarySearchRecursive(arr, target, 0, arr.length - 1);
    }
    
    private static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right);
        } else {
            return binarySearchRecursive(arr, target, left, mid - 1);
        }
    }
    
    // 查找第一个等于目标值的元素
    public static int binarySearchFirst(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1; // 继续向左查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    // 查找最后一个等于目标值的元素
    public static int binarySearchLast(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1; // 继续向右查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;
        
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("找到目标值 " + target + " 在索引 " + index);
        } else {
            System.out.println("未找到目标值 " + target);
        }
    }
}

时间复杂度

• O(log n)

空间复杂度

• 迭代版本：O(1)
• 递归版本：O(log n) - 递归调用栈深度

2. 深度优先搜索（DFS）

基本思想

• 沿着树的深度遍历节点
• 尽可能深地搜索树的分支
• 使用栈或递归实现

Java实现

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjacencyList;
    
    public Graph() {
        this.adjacencyList = new HashMap<>();
    }
    
    public void addEdge(int source, int destination) {
        adjacencyList.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
        adjacencyList.computeIfAbsent(destination, k -> new ArrayList<>()).add(source);
    }
    
    // 递归实现DFS
    public void dfsRecursive(int startVertex) {
        Set<Integer> visited = new HashSet<>();
        dfsRecursive(startVertex, visited);
    }
    
    private void dfsRecursive(int vertex, Set<Integer> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        
        List<Integer> neighbors = adjacencyList.get(vertex);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    dfsRecursive(neighbor, visited);
                }
            }
        }
    }
    
    // 迭代实现DFS
    public void dfsIterative(int startVertex) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        
        stack.push(startVertex);
        
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                System.out.print(vertex + " ");
                
                List<Integer> neighbors = adjacencyList.get(vertex);
                if (neighbors != null) {
                    // 将邻居节点按相反顺序入栈，保持遍历顺序
                    for (int i = neighbors.size() - 1; i >= 0; i--) {
                        int neighbor = neighbors.get(i);
                        if (!visited.contains(neighbor)) {
                            stack.push(neighbor);
                        }
                    }
                }
            }
        }
    }
    
    // 查找路径
    public List<Integer> findPath(int start, int end) {
        Set<Integer> visited = new HashSet<>();
        Map<Integer, Integer> parent = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        
        stack.push(start);
        visited.add(start);
        
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            
            if (vertex == end) {
                return reconstructPath(parent, start, end);
            }
            
            List<Integer> neighbors = adjacencyList.get(vertex);
            if (neighbors != null) {
                for (int neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        parent.put(neighbor, vertex);
                        stack.push(neighbor);
                    }
                }
            }
        }
        
        return null; // 没有找到路径
    }
    
    private List<Integer> reconstructPath(Map<Integer, Integer> parent, int start, int end) {
        List<Integer> path = new ArrayList<>();
        int current = end;
        
        while (current != start) {
            path.add(current);
            current = parent.get(current);
        }
        path.add(start);
        
        Collections.reverse(path);
        return path;
    }
}

3. 广度优先搜索（BFS）

基本思想

• 逐层遍历树的节点
• 先访问所有邻居节点，再访问邻居的邻居
• 使用队列实现

Java实现

public class BreadthFirstSearch {
    
    // 基本BFS
    public static void bfs(Graph graph, int startVertex) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(startVertex);
        queue.offer(startVertex);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            List<Integer> neighbors = graph.getNeighbors(vertex);
            if (neighbors != null) {
                for (int neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
        }
    }
    
    // 层序遍历
    public static void levelOrderTraversal(Graph graph, int startVertex) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(startVertex);
        queue.offer(startVertex);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            System.out.print("层级: ");
            
            for (int i = 0; i < levelSize; i++) {
                int vertex = queue.poll();
                System.out.print(vertex + " ");
                
                List<Integer> neighbors = graph.getNeighbors(vertex);
                if (neighbors != null) {
                    for (int neighbor : neighbors) {
                        if (!visited.contains(neighbor)) {
                            visited.add(neighbor);
                            queue.offer(neighbor);
                        }
                    }
                }
            }
            System.out.println();
        }
    }
    
    // 最短路径（无权图）
    public static Map<Integer, Integer> shortestPath(Graph graph, int startVertex) {
        Map<Integer, Integer> distances = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        
        distances.put(startVertex, 0);
        queue.offer(startVertex);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            int currentDistance = distances.get(vertex);
            
            List<Integer> neighbors = graph.getNeighbors(vertex);
            if (neighbors != null) {
                for (int neighbor : neighbors) {
                    if (!distances.containsKey(neighbor)) {
                        distances.put(neighbor, currentDistance + 1);
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return distances;
    }
}

动态规划

1. 斐波那契数列

基本思想

• 将大问题分解为小问题
• 存储已计算的结果，避免重复计算
• 自底向上或自顶向下的方法

Java实现

public class Fibonacci {
    
    // 递归版本（不推荐，时间复杂度O(2^n)）
    public static long fibonacciRecursive(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }
    
    // 动态规划版本（自底向上）
    public static long fibonacciDP(int n) {
        if (n <= 1) {
            return n;
        }
        
        long[] dp = new long[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];
    }
    
    // 空间优化版本
    public static long fibonacciOptimized(int n) {
        if (n <= 1) {
            return n;
        }
        
        long prev = 0;
        long current = 1;
        
        for (int i = 2; i <= n; i++) {
            long next = prev + current;
            prev = current;
            current = next;
        }
        
        return current;
    }
    
    // 矩阵快速幂版本（时间复杂度O(log n)）
    public static long fibonacciMatrix(int n) {
        if (n <= 1) {
            return n;
        }
        
        long[][] matrix = {{1, 1}, {1, 0}};
        matrix = matrixPower(matrix, n - 1);
        
        return matrix[0][0];
    }
    
    private static long[][] matrixPower(long[][] matrix, int n) {
        if (n == 0) {
            return new long[][]{{1, 0}, {0, 1}};
        }
        
        if (n == 1) {
            return matrix;
        }
        
        long[][] half = matrixPower(matrix, n / 2);
        long[][] result = matrixMultiply(half, half);
        
        if (n % 2 == 1) {
            result = matrixMultiply(result, matrix);
        }
        
        return result;
    }
    
    private static long[][] matrixMultiply(long[][] a, long[][] b) {
        long[][] result = new long[2][2];
        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    result[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int n = 45;
        
        long startTime = System.currentTimeMillis();
        long result = fibonacciOptimized(n);
        long endTime = System.currentTimeMillis();
        
        System.out.println("斐波那契数列第" + n + "项: " + result);
        System.out.println("计算时间: " + (endTime - startTime) + "ms");
    }
}

2. 背包问题

基本思想

• 在有限容量内选择物品，使价值最大
• 每个物品可以选择或不选择
• 使用二维数组存储子问题解

Java实现

public class Knapsack {
    
    // 0-1背包问题
    public static int knapsack01(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    // 可以选择当前物品
                    dp[i][w] = Math.max(dp[i - 1][w], 
                                       dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    // 不能选择当前物品
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    // 空间优化版本
    public static int knapsack01Optimized(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        
        for (int i = 0; i < n; i++) {
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        
        return dp[capacity];
    }
    
    // 完全背包问题（每个物品可以选择多次）
    public static int knapsackUnbounded(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        
        for (int w = 0; w <= capacity; w++) {
            for (int i = 0; i < n; i++) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }
        
        return dp[capacity];
    }
    
    // 多重背包问题（每个物品有数量限制）
    public static int knapsackMultiple(int[] weights, int[] values, int[] counts, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        
        for (int i = 0; i < n; i++) {
            for (int w = capacity; w >= weights[i]; w--) {
                for (int k = 1; k <= counts[i] && k * weights[i] <= w; k++) {
                    dp[w] = Math.max(dp[w], dp[w - k * weights[i]] + k * values[i]);
                }
            }
        }
        
        return dp[capacity];
    }
    
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 10;
        
        int maxValue = knapsack01Optimized(weights, values, capacity);
        System.out.println("背包最大价值: " + maxValue);
    }
}

贪心算法

1. 活动选择问题

基本思想

• 每次选择结束时间最早的活动
• 确保选择的活动数量最多
• 贪心选择性质

Java实现

public class ActivitySelection {
    
    static class Activity {
        int start;
        int end;
        
        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
        
        @Override
        public String toString() {
            return "(" + start + ", " + end + ")";
        }
    }
    
    // 贪心算法选择活动
    public static List<Activity> selectActivities(List<Activity> activities) {
        if (activities.isEmpty()) {
            return new ArrayList<>();
        }
        
        // 按结束时间排序
        activities.sort((a, b) -> Integer.compare(a.end, b.end));
        
        List<Activity> selected = new ArrayList<>();
        selected.add(activities.get(0));
        
        int lastEnd = activities.get(0).end;
        
        for (int i = 1; i < activities.size(); i++) {
            Activity current = activities.get(i);
            
            if (current.start >= lastEnd) {
                selected.add(current);
                lastEnd = current.end;
            }
        }
        
        return selected;
    }
    
    // 区间调度问题（最多不重叠区间）
    public static int maxNonOverlappingIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        // 按结束时间排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        int count = 1;
        int lastEnd = intervals[0][1];
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= lastEnd) {
                count++;
                lastEnd = intervals[i][1];
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        List<Activity> activities = Arrays.asList(
            new Activity(1, 4),
            new Activity(3, 5),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(3, 8),
            new Activity(5, 9),
            new Activity(6, 10),
            new Activity(8, 11),
            new Activity(8, 12),
            new Activity(2, 13),
            new Activity(12, 14)
        );
        
        List<Activity> selected = selectActivities(activities);
        System.out.println("选择的活动数量: " + selected.size());
        System.out.println("选择的活动: " + selected);
    }
}

2. 霍夫曼编码

基本思想

• 根据字符频率构建最优二叉树
• 频率高的字符使用短编码
• 频率低的字符使用长编码

Java实现

import java.util.*;

public class HuffmanCoding {
    
    static class HuffmanNode implements Comparable<HuffmanNode> {
        char character;
        int frequency;
        HuffmanNode left, right;
        
        HuffmanNode(char character, int frequency) {
            this.character = character;
            this.frequency = frequency;
            this.left = this.right = null;
        }
        
        @Override
        public int compareTo(HuffmanNode other) {
            return this.frequency - other.frequency;
        }
    }
    
    // 构建霍夫曼树
    public static HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencies) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
        
        // 创建叶子节点
        for (Map.Entry<Character, Integer> entry : frequencies.entrySet()) {
            pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }
        
        // 构建树
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            
            HuffmanNode parent = new HuffmanNode('\0', left.frequency + right.frequency);
            parent.left = left;
            parent.right = right;
            
            pq.offer(parent);
        }
        
        return pq.poll();
    }
    
    // 生成霍夫曼编码
    public static Map<Character, String> generateHuffmanCodes(HuffmanNode root) {
        Map<Character, String> codes = new HashMap<>();
        generateCodesRecursive(root, "", codes);
        return codes;
    }
    
    private static void generateCodesRecursive(HuffmanNode node, String code, Map<Character, String> codes) {
        if (node == null) {
            return;
        }
        
        // 叶子节点
        if (node.left == null && node.right == null) {
            codes.put(node.character, code);
            return;
        }
        
        // 递归生成编码
        generateCodesRecursive(node.left, code + "0", codes);
        generateCodesRecursive(node.right, code + "1", codes);
    }
    
    // 编码字符串
    public static String encode(String text, Map<Character, String> codes) {
        StringBuilder encoded = new StringBuilder();
        
        for (char c : text.toCharArray()) {
            String code = codes.get(c);
            if (code != null) {
                encoded.append(code);
            }
        }
        
        return encoded.toString();
    }
    
    // 解码字符串
    public static String decode(String encoded, HuffmanNode root) {
        StringBuilder decoded = new StringBuilder();
        HuffmanNode current = root;
        
        for (char bit : encoded.toCharArray()) {
            if (bit == '0') {
                current = current.left;
            } else if (bit == '1') {
                current = current.right;
            }
            
            // 到达叶子节点
            if (current.left == null && current.right == null) {
                decoded.append(current.character);
                current = root;
            }
        }
        
        return decoded.toString();
    }
    
    public static void main(String[] args) {
        String text = "hello world";
        
        // 计算字符频率
        Map<Character, Integer> frequencies = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequencies.put(c, frequencies.getOrDefault(c, 0) + 1);
        }
        
        System.out.println("字符频率: " + frequencies);
        
        // 构建霍夫曼树
        HuffmanNode root = buildHuffmanTree(frequencies);
        
        // 生成编码
        Map<Character, String> codes = generateHuffmanCodes(root);
        System.out.println("霍夫曼编码: " + codes);
        
        // 编码
        String encoded = encode(text, codes);
        System.out.println("编码结果: " + encoded);
        
        // 解码
        String decoded = decode(encoded, root);
        System.out.println("解码结果: " + decoded);
        
        // 计算压缩率
        int originalBits = text.length() * 8;
        int compressedBits = encoded.length();
        double compressionRatio = (double) compressedBits / originalBits;
        
        System.out.println("压缩率: " + String.format("%.2f%%", (1 - compressionRatio) * 100));
    }
}

最佳实践

1. 算法选择

// 根据问题规模选择合适算法
public class AlgorithmSelector {
    
    public static void selectSortingAlgorithm(int[] arr) {
        int n = arr.length;
        
        if (n < 50) {
            // 小规模数据使用插入排序
            insertionSort(arr);
        } else if (n < 1000) {
            // 中等规模数据使用快速排序
            quickSort(arr);
        } else {
            // 大规模数据使用归并排序
            mergeSort(arr);
        }
    }
    
    public static void selectSearchAlgorithm(int[] arr, int target) {
        // 有序数组使用二分查找
        if (isSorted(arr)) {
            int index = binarySearch(arr, target);
            System.out.println("二分查找结果: " + index);
        } else {
            // 无序数组使用线性查找
            int index = linearSearch(arr, target);
            System.out.println("线性查找结果: " + index);
        }
    }
}

2. 性能优化

// 避免重复计算
public class PerformanceOptimization {
    
    // 使用缓存避免重复计算
    private static Map<Integer, Long> fibonacciCache = new HashMap<>();
    
    public static long fibonacciWithCache(int n) {
        if (fibonacciCache.containsKey(n)) {
            return fibonacciCache.get(n);
        }
        
        long result;
        if (n <= 1) {
            result = n;
        } else {
            result = fibonacciWithCache(n - 1) + fibonacciWithCache(n - 2);
        }
        
        fibonacciCache.put(n, result);
        return result;
    }
    
    // 使用备忘录模式
    public static long fibonacciWithMemo(int n) {
        long[] memo = new long[n + 1];
        Arrays.fill(memo, -1);
        return fibonacciMemo(n, memo);
    }
    
    private static long fibonacciMemo(int n, long[] memo) {
        if (memo[n] != -1) {
            return memo[n];
        }
        
        if (n <= 1) {
            memo[n] = n;
        } else {
            memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
        }
        
        return memo[n];
    }
}

3. 代码质量

// 编写清晰的算法代码
public class CodeQuality {
    
    // 使用有意义的变量名
    public static int findMaximumSubarraySum(int[] numbers) {
        int currentSum = 0;
        int maximumSum = Integer.MIN_VALUE;
        
        for (int number : numbers) {
            currentSum = Math.max(number, currentSum + number);
            maximumSum = Math.max(maximumSum, currentSum);
        }
        
        return maximumSum;
    }
    
    // 添加适当的注释
    public static void quickSortWithComments(int[] arr, int low, int high) {
        if (low < high) {
            // 选择基准元素并分区
            int pivotIndex = partition(arr, low, high);
            
            // 递归排序左半部分
            quickSortWithComments(arr, low, pivotIndex - 1);
            
            // 递归排序右半部分
            quickSortWithComments(arr, pivotIndex + 1, high);
        }
    }
    
    // 处理边界情况
    public static int safeBinarySearch(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        
        return binarySearch(arr, target);
    }
}

总结