当前位置：首页 > 后端开发 > 正文

java算法怎么写

admin
后端开发
2025-08-24
5

va算法通过代码实现数据处理、搜索排序等功能，需遵循有穷性、确定性等特性，常应用于数据结构与递归等场景

va作为一门面向对象的编程语言,在实现各种算法时具有独特的优势，下面将详细介绍如何在Java中编写常见的基础算法，包括排序、查找和一些经典问题的解决方案。

排序算法

冒泡排序（Bubble Sort）

基本思想：重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，遍历数列的工作是重复地进行直到没有再需要交换的元素为止。

代码示例：

public class BubbleSort {
    public static 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]) {
                    // 交换 arr[j] 和 arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

特点：简单易懂，但效率较低，时间复杂度为O(n²)，适用于小规模数据或基本教学场景。

选择排序（Selection Sort）

基本思想：每次从未排序的部分选出最小（大）的元素放到已排序序列的末尾。

代码示例：

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;
                }
            }
            // 将找到的最小值与第i个位置交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

特点：同样简单直观，但性能也较差，时间复杂度也是O(n²)，不过减少了元素的交换次数。

插入排序（Insertion Sort）

基本思想：构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码示例：

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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

特点：对几乎有序的数据非常高效，时间复杂度介于O(n)到O(n²)之间，取决于输入数据的初始状态。

快速排序（Quick Sort）

java算法怎么写第1张

基本思想：采用分治法策略，选取一个基准元素，将数组分为两部分，一部分小于基准，另一部分大于基准，然后递归地对这两部分进行快速排序。

代码示例：

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi 1);
            quickSort(arr, pi + 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;
    }
}

特点：平均情况下时间复杂度为O(n log n)，最坏情况下为O(n²)，但在实际应用中表现优异，常被用作默认排序算法之一。

归并排序（Merge Sort）

基本思想：也是基于分治法，先将数组分成两半分别排序，然后将两个有序子数组合并成一个大的有序数组。

代码示例：

public class MergeSort {
    public 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[] L = new int[mid left + 1];
        int[] R = new int[right mid];
        System.arraycopy(arr, left, L, 0, L.length);
        System.arraycopy(arr, mid + 1, R, 0, R.length);
        int i = 0, j = 0, k = left;
        while (i < L.length && j < R.length) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }
        while (i < L.length) {
            arr[k++] = L[i++];
        }
        while (j < R.length) {
            arr[k++] = R[j++];
        }
    }
}

特点：稳定且时间复杂度始终为O(n log n)，但需要额外的存储空间来辅助合并操作。

以下是上述几种排序算法的性能对比表格：
|算法名称|时间复杂度（最好情况）|时间复杂度（平均情况）|时间复杂度（最坏情况）|是否稳定|所需辅助空间|
|—-|—-|—-|—-|—-|—-|
|冒泡排序|O(n)|O(n²)|O(n²)|是|O(1)|
|选择排序|O(n²)|O(n²)|O(n²)|否|O(1)|
|插入排序|O(n)|O(n²)|O(n²)|是|O(1)|
|快速排序|O(n log n)|O(n log n)|O(n²)|否|O(log n)|
|归并排序|O(n log n)|O(n log n)|O(n log n)|是|O(n)|

查找算法——二分查找（Binary Search）

基本思想：在一个有序数组中查找某个特定元素的位置，每次比较中间位置的元素与目标值的大小关系，从而缩小搜索范围的一半，可以使用递归或迭代的方式实现。

非递归实现代码示例：

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; // 如果未找到返回-1
    }
}

递归实现代码示例：

public class BinarySearchRecursive {
    public static int binarySearch(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 binarySearch(arr, target, mid + 1, right);
        } else {
            return binarySearch(arr, target, left, mid 1);
        }
    }
}

特点：前提是数组必须是有序的，时间复杂度为O(log n)，效率较高。

动态规划——背包问题（以0-1背包为例）

问题描述：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品使得总价值最大，每个物品只能选一次（要么装入背包，要么不装）。
基本思想：使用动态规划来解决这类优化问题，定义一个二维数组dp[i][w]表示前i件物品恰好放入容量为w的背包中所能得到的最大价值，状态转移方程为：dp[i][w] = max(dp[i 1][w], dp[i 1][w weight[i]] + value[i])，其中weight[i]和value[i]分别是第i件物品的重量和价值，最终答案是dp[n][W]，n是物品数量，W是背包总容量。

代码示例：

public class KnapsackProblem {
    public static int knapsack(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 = 1; 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];
    }
}

特点：通过存储中间结果避免重复计算，显著提高了解决问题的效率，适用于具有重叠子问题和最优子结构性质的问题。

贪心算法——集合覆盖问题（Set Cover Problem）

问题描述：给定一个全集U以及若干个子集S₁, S₂, …, Sₙ，这些子集构成了原集合的一个覆盖（即它们的并集等于U），目标是从中选出最少数量的子集仍然能够覆盖整个集合U，这是一个典型的NP难问题，但对于某些特殊情况可以用贪心算法得到近似解。
基本思想：每次选择一个未被选中过的、能覆盖最多新元素的子集加入解决方案中，直到所有元素都被覆盖为止，虽然不能保证总是得到最优解，但在很多实际应用场景下可以得到较好的结果。
代码示例：由于该问题的复杂性，这里仅提供伪代码思路：初始化一个空的结果集；当还有元素未被覆盖时循环执行以下步骤：遍历剩余可选的子集，找出那个能新增最多未被覆盖元素的子集将其添加到结果集中；更新已被覆盖的元素集合；重复上述过程直至所有元素均被覆盖，具体的Java实现会根据具体的数据结构和需求有所不同。
特点：实现相对简单快捷，但不一定能获得全局最优解，适合于对实时性要求较高而精度要求不是极高的场合。