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