Java 常用算法详解：从集合框架到并发编程

Java 常用算法详解：从集合框架到并发编程 | 极客日志

// Collections 工具类中的静态算法方法
List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6);

// 1. 排序算法
Collections.sort(numbers);  // 升序排序
Collections.sort(numbers, Collections.reverseOrder());  // 降序排序
Collections.shuffle(numbers);  // 随机打乱

// 2. 查找算法
int index = Collections.binarySearch(numbers, 5);  // 二分查找
int freq = Collections.frequency(numbers, 1);  // 出现频率

// 3. 极值算法
Integer max = Collections.max(numbers);
Integer min = Collections.min(numbers);

// 4. 不可变集合
List<Integer> unmodifiable = Collections.unmodifiableList(numbers);
Set<Integer> singleton = Collections.singleton(42);
List<Integer> nCopies = Collections.nCopies(5, 0);  // [0, 0, 0, 0, 0]

// 创建 → 中间操作 → 终止操作
List<Integer> result = numbers.stream()
    .filter(n -> n % 2 == 0)            // 中间操作：过滤
    .map(n -> n * n)                    // 中间操作：映射
    .sorted((a, b) -> b - a)            // 中间操作：排序
    .distinct()                         // 中间操作：去重
    .limit(3)                           // 中间操作：限制
    .collect(Collectors.toList());      // 终止操作：收集

// 并行流加速处理
long count = numbers.parallelStream()
    .filter(n -> isPrime(n))
    .count();

// 1. 分组与分区
Map<String, List<Employee>> byDept = employees.stream()
    .collect(Collectors.groupingBy(Employee::getDepartment));

Map<Boolean, List<Employee>> partitioned = employees.stream()
    .collect(Collectors.partitioningBy(e -> e.getSalary() > 50000));

// 2. 统计汇总
IntSummaryStatistics stats = employees.stream()
    .mapToInt(Employee::getSalary)
    .summaryStatistics();
// 包含：count, sum, min, max, average

// 3. 连接字符串
String names = employees.stream()
    .map(Employee::getName)
    .collect(Collectors.joining(", ", "[", "]"));

// 4. 归约操作
Optional<Integer> total = numbers.stream()
    .reduce((a, b) -> a + b);  // 求和

Integer sum = numbers.stream()
    .reduce(0, Integer::sum);  // 带初始值的求和

// 5. 自定义收集器
Collector<Employee, ?, Map<String, Double>> avgSalaryByDept = 
    Collectors.groupingBy(
        Employee::getDepartment,
        Collectors.averagingDouble(Employee::getSalary)
    );

// 1. 实现 Comparable 接口
class Person implements Comparable<Person> {
    private String name;
    private int age;
    
    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

// 2. 使用 Comparator（更灵活）
Comparator<Person> byName = Comparator.comparing(Person::getName);
Comparator<Person> byAge = Comparator.comparingInt(Person::getAge);
Comparator<Person> byNameThenAge = 
    Comparator.comparing(Person::getName)
              .thenComparingInt(Person::getAge);

// 3. 复杂排序
List<Person> sorted = people.stream()
    .sorted(Comparator
        .comparing(Person::getLastName)
        .thenComparing(Person::getFirstName)
        .reversed())
    .collect(Collectors.toList());

// 4. 处理 null 值
Comparator<Person> nullsFirst = 
    Comparator.nullsFirst(Comparator.naturalOrder());

// 1. 二分查找（数组必须有序）
int[] sortedArray = {1, 3, 5, 7, 9, 11, 13};
int index = Arrays.binarySearch(sortedArray, 7);  // 返回 3

// 2. 自定义二分查找
public static <T> int binarySearch(List<? extends T> list, T key,
                                  Comparator<? super T> c) {
    int low = 0;
    int high = list.size() - 1;
    
    while (low <= high) {
        int mid = (low + high) >>> 1;  // 无符号右移，防止溢出
        T midVal = list.get(mid);
        int cmp = c.compare(midVal, key);
        
        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid;  // 找到
        }
    }
    return -(low + 1);  // 未找到，返回插入点
}

// 3. 使用 Collections.binarySearch
List<String> words = Arrays.asList("apple", "banana", "cherry", "date");
int pos = Collections.binarySearch(words, "cherry");

// 1. 使用 Math 类
double sqrt = Math.sqrt(16.0);       // 4.0
double pow = Math.pow(2, 10);        // 1024.0
double sin = Math.sin(Math.PI / 2);  // 1.0
long round = Math.round(3.14159);    // 3

// 2. 随机数生成
Random random = new Random();
int randomInt = random.nextInt(100);       // 0-99
double randomDouble = random.nextDouble(); // 0.0-1.0

// 3. 安全的随机数（密码学安全）
SecureRandom secureRandom = new SecureRandom();
byte[] randomBytes = new byte[16];
secureRandom.nextBytes(randomBytes);

// 4. 大数计算
BigInteger bigInt = new BigInteger("12345678901234567890");
BigInteger result = bigInt.multiply(new BigInteger("2"));

BigDecimal decimal1 = new BigDecimal("10.50");
BigDecimal decimal2 = new BigDecimal("3.75");
BigDecimal division = decimal1.divide(decimal2, 4, RoundingMode.HALF_UP);

// 1. 基本统计
public class Statistics {
    public static double mean(double[] values) {
        return Arrays.stream(values).average().orElse(0.0);
    }
    
    public static double median(double[] values) {
        double[] sorted = values.clone();
        Arrays.sort(sorted);
        int n = sorted.length;
        if (n % 2 == 0) {
            return (sorted[n/2 - 1] + sorted[n/2]) / 2.0;
        } else {
            return sorted[n/2];
        }
    }
    
    public static double standardDeviation(double[] values) {
        double mean = mean(values);
        double variance = Arrays.stream(values)
            .map(x -> Math.pow(x - mean, 2))
            .average().orElse(0.0);
        return Math.sqrt(variance);
    }
}

// 2. 使用 DoubleSummaryStatistics
DoubleSummaryStatistics stats = Arrays.stream(new double[]{1.0, 2.0, 3.0, 4.0})
    .summaryStatistics();

// 3. 移动平均
public static double[] movingAverage(double[] data, int window) {
    double[] result = new double[data.length - window + 1];
    double sum = 0;
    
    for (int i = 0; i < window; i++) {
        sum += data[i];
    }
    result[0] = sum / window;
    
    for (int i = window; i < data.length; i++) {
        sum = sum - data[i - window] + data[i];
        result[i - window + 1] = sum / window;
    }
    
    return result;
}

// 1. KMP 字符串匹配算法
public class KMP {
    public static int search(String text, String pattern) {
        int[] lps = computeLPS(pattern);
        int i = 0, j = 0;
        
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) {
                    return i - j;
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
    
    private static int[] computeLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0, i = 1;
        
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}

// 2. 字符串编辑距离（动态规划）
public static int editDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1],  // 替换
                    Math.min(
                        dp[i - 1][j],  // 删除
                        dp[i][j - 1]   // 插入
                    )
                );
            }
        }
    }
    return dp[m][n];
}

// 3. 使用 StringBuilder 优化字符串操作
public static String reverseString(String s) {
    return new StringBuilder(s).reverse().toString();
}

public static boolean isPalindrome(String s) {
    String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    return cleaned.equals(new StringBuilder(cleaned).reverse().toString());
}

// 1. 并行流计算
long sum = LongStream.rangeClosed(1, 10_000_000)
    .parallel()
    .sum();

// 2. 自定义 Fork/Join 任务
class SumTask extends RecursiveTask<Long> {
    private static final int THRESHOLD = 10_000;
    private final long[] array;
    private final int start, end;
    
    SumTask(long[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
    
    @Override
    protected Long compute() {
        if (end - start <= THRESHOLD) {
            long sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            int mid = (start + end) / 2;
            SumTask left = new SumTask(array, start, mid);
            SumTask right = new SumTask(array, mid, end);
            left.fork();
            long rightResult = right.compute();
            long leftResult = left.join();
            return leftResult + rightResult;
        }
    }
}

// 使用 Fork/Join 池
ForkJoinPool pool = new ForkJoinPool();
long[] numbers = new long[100_000];
// 填充数组...
SumTask task = new SumTask(numbers, 0, numbers.length);
long result = pool.invoke(task);

// 1. ConcurrentHashMap 的原子操作
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 线程安全的更新
map.compute("key", (k, v) -> v == null ? 1 : v + 1);

// 原子操作
map.merge("key", 1, Integer::sum);

// 2. CopyOnWriteArrayList（读多写少场景）
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("item1");
list.addIfAbsent("item1");  // 不会重复添加

// 3. 阻塞队列算法
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(10);

// 生产者
new Thread(() -> {
    try {
        for (int i = 0; i < 100; i++) {
            queue.put(i);  // 阻塞直到有空间
            Thread.sleep(100);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

// 消费者
new Thread(() -> {
    try {
        while (true) {
            Integer item = queue.take();  // 阻塞直到有元素
            System.out.println("Consumed: " + item);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

// 1. 邻接表表示
class Graph {
    private final int V;
    private final List<List<Integer>> adj;
    
    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }
    
    public void addEdge(int v, int w) {
        adj.get(v).add(w);
    }
    
    // 深度优先搜索
    public void dfs(int start) {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                visited[v] = true;
                System.out.print(v + " ");
                
                for (int neighbor : adj.get(v)) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
    
    // 广度优先搜索
    public void bfs(int start) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            
            for (int neighbor : adj.get(v)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
}

// 2. Dijkstra 最短路径算法
public class Dijkstra {
    public static int[] dijkstra(int[][] graph, int src) {
        int V = graph.length;
        int[] dist = new int[V];
        boolean[] sptSet = new boolean[V];
        
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;
            
            for (int v = 0; v < V; v++) {
                if (!sptSet[v] && graph[u][v] != 0 &&
                    dist[u] != Integer.MAX_VALUE &&
                    dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
        return dist;
    }
    
    private static int minDistance(int[] dist, boolean[] sptSet) {
        int min = Integer.MAX_VALUE, minIndex = -1;
        
        for (int v = 0; v < dist.length; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
}

// 策略接口
interface SortStrategy {
    void sort(int[] array);
}

// 具体策略
class BubbleSortStrategy implements SortStrategy {
    @Override
    public void sort(int[] array) {
        // 冒泡排序实现
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

class QuickSortStrategy implements SortStrategy {
    @Override
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }
    
    private void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }
    
    private int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }
    
    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

// 上下文类
class Sorter {
    private SortStrategy strategy;
    
    public Sorter(SortStrategy strategy) {
        this.strategy = strategy;
    }
    
    public void setStrategy(SortStrategy strategy) {
        this.strategy = strategy;
    }
    
    public void sort(int[] array) {
        strategy.sort(array);
    }
}

// 使用示例
public class StrategyPatternDemo {
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 1, 9, 3};
        
        Sorter sorter = new Sorter(new BubbleSortStrategy());
        sorter.sort(array);
        System.out.println("Bubble sort: " + Arrays.toString(array));
        
        sorter.setStrategy(new QuickSortStrategy());
        sorter.sort(array);
        System.out.println("Quick sort: " + Arrays.toString(array));
    }
}

Java 常用算法详解：从集合框架到并发编程

一、Java 算法生态：集合框架与流式编程

1.1 Java 算法的演进历程

1.2 集合框架中的算法

二、Stream API：声明式算法编程

2.1 Stream 操作的三阶段

2.2 高级 Stream 操作

三、排序与搜索算法

3.1 对象排序的多种方式

3.2 搜索算法实现

四、数值计算与统计

4.1 基本数值算法

4.2 统计与聚合算法

五、字符串处理算法

5.1 字符串匹配与操作

六、并发与并行算法

6.1 并行流与 Fork/Join 框架

6.2 并发集合算法

七、图算法实现

7.1 图的表示与遍历

八、设计模式在算法中的应用

8.1 策略模式实现排序算法

更多推荐文章

相关免费在线工具

Java 常用算法详解：从集合框架到并发编程

一、Java 算法生态：集合框架与流式编程

1.1 Java 算法的演进历程

1.2 集合框架中的算法

二、Stream API：声明式算法编程

2.1 Stream 操作的三阶段

2.2 高级 Stream 操作

三、排序与搜索算法

3.1 对象排序的多种方式

3.2 搜索算法实现

四、数值计算与统计

4.1 基本数值算法

4.2 统计与聚合算法

五、字符串处理算法

5.1 字符串匹配与操作

六、并发与并行算法

6.1 并行流与 Fork/Join 框架

6.2 并发集合算法

七、图算法实现

7.1 图的表示与遍历

八、设计模式在算法中的应用

8.1 策略模式实现排序算法

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具