Java常用算法

1.排序算法

冒泡排序

实现原理：左边大于右边交换一趟排下来最大的在右边

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = new int[]{
                3, 5, 15, 26, 27, 2, 36
        };
        // 冒泡排序：从左到右（由小到大）
        int[] res = BubbleSort.bubbleSort(arr);
        for (int r : res) {
            System.out.print(r+"-");
        }
    }

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

插入排序

原理

1.从第一个元素开始，该元素可以认为已经被排序

2.取下一个元素tem，从已排序的元素序列从后往前扫描

3.如果该元素大于tem，则将该元素移到下一位

4.重复步骤3，直到找到已排序元素中小于等于tem的元素

5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置

6.重复步骤2~5

选择排序

​ 每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

​ 实际上，可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍

/**
 * 选择排序
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = new int[]{
                3, 5, 15, 26, 27, 2, 36
        };
        // 选择排序
        int[] res = SelectionSort.selectionSort(arr);
        for (int r : res) {
            System.out.print(r+"-");
        }
    }

    public static int[] selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 找到从i到n-1中的最小元素
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // 将找到的最小元素与i位置的元素交换
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }
}

2.搜索算法

二分搜索/折半搜索

• 前提条件：数组中的数据必须有序
• 核心逻辑：每次排除一般的查找范围

/**
 * 二分法搜索
 */
public class BinarySearch {

    public static void main(String[] args) {
        // 二分搜索需对数组进行排序，随后调用二分搜索进行检索，返回数组下标
        int[] arr = new int[]{
                1, 6, 15, 17, 29
        };
        System.out.println(BinarySearch.binarySearch(arr, 15));
    }

    public static int binarySearch(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 检查x是否在中间
            if (arr[mid] == x)
                return mid;
            // 如果x大于中位数，忽略左半边
            if (arr[mid] < x)
                left = mid + 1;
                // 如果x小于中位数，忽略右半边
            else
                right = mid - 1;
        }
        // 如果没有找到，返回-1
        return -1;
    }
}

3.图算法

4.动态规划