Java算法详解(9大常用算法)

Java算法是开发经常使用到的，也是面试必考的，下面详解常见的9大Java算法@mikechen

冒泡排序算法

冒泡排序是一种简单的排序算法，它多次遍历数组，比较相邻的元素并交换它们，直到整个数组排序完成。

如下所示：

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;
            }
        }
    }
}

 

选择排序算法

选择排序是一种简单的排序算法，它每次从未排序的部分中选择最小的元素并将其放在已排序的部分末尾。

如下所示：

public 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;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

 

插入排序算法

插入排序是一种简单的排序算法，它将数组分为已排序和未排序两部分，然后逐个将未排序部分的元素插入到已排序部分的适当位置。

如下所示：

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;
    }
}

 

快速排序算法

快速排序是一种分而治之排序算法，它通过选择一个基准元素，将数组分成两个子数组，然后递归地对子数组进行排序。

如下所示：

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;
}

 

归并排序算法

归并排序是一种分而治之的排序算法，它将数组分为两个子数组，然后递归地对子数组进行排序，最后将排好序的子数组合并成一个有序的数组。

如下所示：

public class MergeSort {
    public void mergeSort(int[] arr) {
        if (arr.length > 1) {
            int mid = arr.length / 2;
            int[] left = new int[mid];
            int[] right = new int[arr.length - mid];

            // 将原数组拆分为左右两个子数组
            for (int i = 0; i < mid; i++) {
                left[i] = arr[i];
            }
            for (int i = mid; i < arr.length; i++) {
                right[i - mid] = arr[i];
            }

            // 递归排序左右子数组
            mergeSort(left);
            mergeSort(right);

            // 合并排序好的左右子数组
            merge(arr, left, right);
        }
    }

    private void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // 合并两个子数组
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        // 将剩余的元素复制回原数组
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        MergeSort sorter = new MergeSort();
        sorter.mergeSort(arr);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

希尔排序算法

希尔排序（Shell Sort）是一种改进的插入排序算法，它通过比较距离较远的元素来交换相邻的元素，从而将大的元素快速移动到数组的一端。

如下所示：

public class ShellSort {
    public void shellSort(int[] arr) {
        int n = arr.length;
        int gap = n / 2;

        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        ShellSort sorter = new ShellSort();
        int[] arr = {12, 34, 54, 2, 3};
        sorter.shellSort(arr);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

二分查找算法

二分查找算法，是一种高效的查找算法，要求输入数据必须是已排序的。

如下所示：

public int binarySearch(int[] arr, int target) {
    int left = 0, 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 class FibonacciDP {
    public int calculateFibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[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 void main(String[] args) {
        FibonacciDP fibonacci = new FibonacciDP();
        int n = 10;
        int result = fibonacci.calculateFibonacci(n);
        System.out.println("Fibonacci number at index " + n + " is " + result);
    }
}

 

贪心算法

贪心算法是一种寻找局部最优解以构建全局最优解的方法。

贪心算法通常用于解决那些可以被分解为一系列子问题的问题，每一步都选择局部最优解，而不是考虑整体的选择。

如下所示：

import java.util.Arrays;

public class GreedyCoinChange {
    public int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 首先对面值进行排序
        int coinCount = 0;

        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                coinCount++;
            }
        }

        if (amount == 0) {
            return coinCount;
        } else {
            return -1; // 无法凑出零钱
        }
    }

    public static void main(String[] args) {
        GreedyCoinChange changer = new GreedyCoinChange();
        int[] coins = {1, 2, 5, 10, 20, 50, 100};
        int amount = 63;
        int result = changer.minCoins(coins, amount);
        if (result != -1) {
            System.out.println("Minimum coins required: " + result);
        } else {
            System.out.println("It's not possible to make change for the given amount.");
        }
    }
}

在这个示例中，我们尝试找零钱，使用尽可能少的硬币。

首先：我们对硬币面值进行排序，以便在每一步选择最大面值的硬币，从而获得局部最优解。

然后：我们不断减去面值直到达到零。

最终：我们得到了最小数量的硬币。

mikechen

mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【架构】即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》