JAVA_FourTEEN_常见算法
目录
1. 排序算法
① 冒泡排序（Bubble Sort）
② 快速排序（Quick Sort）
2. 查找算法
① 二分查找（Binary Search）
3. 递归算法
① 斐波那契数列
② 阶乘
4. 动态规划（Dynamic Programming）
① 爬楼梯问题
5. 字符串算法
① 反转字符串
6.正则表达式
1. 排序算法
① 冒泡排序（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 - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换相邻元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("排序后: " + Arrays.toString(arr)); // [11, 12, 22, 25, 34, 64, 90]}
}
② 快速排序（Quick Sort）
原理：选择一个 “基准值”，将数组分为两部分（小于基准和大于基准），递归排序。
示例：
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++;// 交换arr[i]和arr[j]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 static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("排序后: " + Arrays.toString(arr)); // [1, 5, 7, 8, 9, 10]}
}
2. 查找算法
① 二分查找（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; // 未找到}public static void main(String[] args) {int[] arr = {2, 5, 8, 12, 16, 23, 38};int target = 12;int index = binarySearch(arr, target);System.out.println("目标位置: " + index); // 3}
}
3. 递归算法
① 斐波那契数列
原理：第 n 项 = 第 n-1 项 + 第 n-2 项（n ≥ 2）。
示例：
public class Fibonacci {// 递归实现（效率低，适合理解原理）public static int fib(int n) {if (n <= 1) {return n; // 边界：n=0返回0，n=1返回1}return fib(n - 1) + fib(n - 2);}public static void main(String[] args) {int n = 10;System.out.println("斐波那契第" + n + "项: " + fib(n)); // 55}
}
② 阶乘
原理：n! = n × (n-1) × ... × 1（0! = 1）。
示例：
public class Factorial {public static int factorial(int n) {if (n == 0) {return 1; // 边界条件}return n * factorial(n - 1);}public static void main(String[] args) {int n = 5;System.out.println(n + "的阶乘: " + factorial(n)); // 120}
}
4. 动态规划（Dynamic Programming）
① 爬楼梯问题
问题：一次可爬 1 或 2 阶，求爬到第 n 阶的方法数。
原理：dp [n] = dp [n-1] + dp [n-2]（第 n 阶 = 从 n-1 阶爬 1 阶 + 从 n-2 阶爬 2 阶）。
示例：
public class ClimbStairs {public static int climbStairs(int n) {if (n <= 2) {return n; // 1阶1种，2阶2种}int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}public static void main(String[] args) {int n = 5;System.out.println("爬到第" + n + "阶的方法数: " + climbStairs(n)); // 8}
}
5. 字符串算法
① 反转字符串
示例：
public class ReverseString {public static String reverse(String s) {char[] arr = s.toCharArray();int left = 0;int right = arr.length - 1;while (left < right) {// 交换左右字符char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}return new String(arr);}public static void main(String[] args) {String s = "hello";System.out.println("反转后: " + reverse(s)); // "olleh"}
}6.正则表达式
正则表达式就像 “文本过滤器”，能快速从一堆文字中找到符合特定格式的内容（比如邮箱、手机号、网址等），或对文本做复杂替换。
示例
/*
*正则表述式检验电话号码和邮箱号码格式是否正确
*/
import java.util.Scanner;public class RegexTest {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (true) {System.out.println("输入1检验电话号码是否正确,输入2检验邮箱号码是否正确");int flag = scanner.nextInt();if (flag == 0) {checkPhone();} else {checkEmail();}}}//检验输入电话的格式是否正确public static void checkPhone() {Scanner sc = new Scanner(System.in);while (true) {System.out.println("请输入电话号码或座机号码:");String phone = sc.next();//以数字1开头,3~9为第二位,其余九位为任意数字 或以数字0开头,后跟2~7位数字，-可有1次或无,其余后跟3~5位任意数字if (phone.matches("1[3-9]\\\\d{9}|0\\\\d{2,7}-?\\\\d{3,5}")) {System.out.println("输入电话号码正确!");break;} else {System.out.println("输入电话号码错误,请重新输入");}}}//检验输入邮箱的格式是否正确public static void checkEmail() {Scanner sc = new Scanner(System.in);while (true) {System.out.println("请输入邮箱号码:");String phone = sc.next();if (phone.matches("\\\\w{3,19}@\\\\w{2,11}(\\\\.\\\\w{2,7}){1,2}")) {System.out.println("输入邮箱号码正确!");break;} else {System.out.println("输入邮箱号码错误,请重新输入");}}}}