Java函数实现算法：排序、查找、图算法等算法函数实现方法

在Java中，我们可以使用函数来实现各种算法，包括排序、查找、图算法等。下面将介绍一些常见算法的实现方法。

一、排序算法实现方法

1. 冒泡排序：比较相邻的元素，如果前一个比后一个大，则交换它们的位置，重复该过程，直到整个数组排序完成。

代码示例：

public void bubbleSort(int[] arr){
    int n = arr.length;
    for (int i = 0; i < n - 1; i++){
        for (int j = 0; j < n - i - 1; j++){
            if (arr[j] > arr[j + 1]){
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 插入排序：将数组分为已排序和未排序两部分，每次从未排序部分选取一个元素插入到已排序部分的适当位置。

代码示例：

public void insertionSort(int[] arr){
    int n = arr.length;
    for (int i = 1; i < n; i++){
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

3. 快速排序：选择一个元素作为基准，将数组分为比基准小和比基准大的两部分，然后递归地对这两部分进行排序。

代码示例：

public 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 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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

二、查找算法实现方法

1. 二分查找：对于有序数组，从中间元素开始比较，如果不等于目标元素，则根据大小关系缩小查找范围，直到找到目标元素或查找范围为空。

代码示例：

public int binarySearch(int[] arr, int target){
    int low = 0, high = arr.length - 1;
    while (low <= high){
        int mid = (low + high) / 2;
        if (arr[mid] == target){
            return mid;
        }
        else if (arr[mid] < target){
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }
    return -1;
}

2. 线性查找：从数组的 个元素开始逐个比较，直到找到目标元素或遍历完整个数组。

代码示例：

public int linearSearch(int[] arr, int target){
    int n = arr.length;
    for (int i = 0; i < n; i++){
        if (arr[i] == target){
            return i;
        }
    }
    return -1;
}

三、图算法实现方法

1. 广度优先搜索（BFS）：从起始顶点开始，逐层遍历图中的顶点，直到找到目标顶点或遍历完整个图。

代码示例：

public void bfs(int start, int target){
    boolean[] visited = new boolean[numVertices()];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()){
        int vertex = queue.poll();
        if (vertex == target){
            System.out.println("Target found!");
            return;
        }
        List<Integer> neighbors = getNeighbors(vertex);
        for (int neighbor : neighbors){
            if (!visited[neighbor]){
                queue.add(neighbor);
                visited[neighbor] = true;
            }
        }
    }
    System.out.println("Target not found!");
}

2. 深度优先搜索（DFS）：从起始顶点开始，递归地遍历图中的顶点，直到找到目标顶点或遍历完整个图。

代码示例：

public void dfs(int start, int target, boolean[] visited){
    visited[start] = true;
    if (start == target){
        System.out.println("Target found!");
        return;
    }
    List<Integer> neighbors = getNeighbors(start);
    for (int neighbor : neighbors){
        if (!visited[neighbor]){
            dfs(neighbor, target, visited);
        }
    }
    System.out.println("Target not found!");
}

以上是一些常见算法在Java中的实现方法。根据具体的需求，我们可以选择合适的算法来解决问题。希望对你有帮助！