用Java函数实现常用算法和数据结构

Java是一种面向对象的编程语言，它提供了强大的工具和库来实现各种算法和数据结构。下面将介绍Java中常用的算法和数据结构，并提供相应的实现示例。

1. 排序算法：Java中常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。以下是一个示例使用快速排序来实现整数数组升序排序的函数。

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 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 void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

2. 查找算法：Java中常见的查找算法有线性查找、二分查找、哈希查找等。以下是一个示例使用二分查找算法在有序整数数组中查找目标元素的函数。

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) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

3. 栈：Java的java.util.Stack类提供了栈的实现。以下是一个示例使用栈来判断输入的括号序列是否合法的函数。

public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
            stack.pop();
        } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
            stack.pop();
        } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
            stack.pop();
        } else {
            return false;
        }
    }

    return stack.isEmpty();
}

4. 队列：Java的java.util.LinkedList类提供了队列的实现。以下是一个示例使用队列来实现基于广度优先搜索的图遍历的函数。

public static void bfs(Graph graph, int start) {
    boolean[] visited = new boolean[graph.V];
    Queue<Integer> queue = new LinkedList<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        System.out.print(vertex + " ");

        for (int neighbor : graph.adjList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

5. 链表：Java的java.util.LinkedList类提供了链表的实现。以下是一个示例使用链表来实现LRU（最近最少使用）缓存算法的函数。

class LRUCache {
    // ...
    // 内部实现省略
    // ...
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            list.remove(key);
        } else if (list.size() >= capacity) {
            int leastKey = list.removeFirst();
            map.remove(leastKey);
        }

        list.addLast(key);
        map.put(key, value);
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        list.remove(key);
        list.addLast(key);

        return map.get(key);
    }
}

以上是Java中常用的算法和数据结构的实现示例。通过学习和掌握这些算法和数据结构，可以帮助我们解决实际问题，提高代码的效率和质量。当然，Java还提供了更多的算法和数据结构的库和类，可以根据实际需求选择合适的工具来实现。