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 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(\"输入邮箱号码错误,请重新输入\"); } } }}
