# 常见算法
算法：解决某个实际问题的过程和方法
# 冒泡排序
每次从数组中找出最大值放在数组的后面去
实现关键步骤：
- 确定总共需要做几轮：
数组的长度-1 - 每轮比较几次
- 当前位置大于后一个位置则交换数据
演示
public class Test { | |
public static void main(String[] args) { | |
int[] arr = {5, 2, 3, 1}; | |
for (int i = 0; i < arr.length - 1; i++) { | |
for (int j = 0; j < arr.length - i - 1; j++) { | |
if (arr[j] > arr[j + 1]) { | |
int temp = arr[j + 1]; | |
arr[j + 1] = arr[j]; | |
arr[j] = temp; | |
} | |
} | |
} | |
System.out.println(Arrays.toString(arr)); | |
} | |
} |
# 选择排序
每轮选择当前位置，开始找出后面的较小值与该位置交换
实现关键步骤：
- 确定总共需要选择几轮：
数组的长度-1 - 控制每轮从以前位置为基准，与后面元素选择几次
演示
public class Test { | |
public static void main(String[] args) { | |
int[] arr = {5, 2, 3, 1}; | |
for (int i = 0; i < arr.length - 1; i++) { | |
for (int j = i + 1; j < arr.length; j++) { | |
if (arr[i] > arr[j]) { | |
int temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
} | |
} | |
// 进一步优化 | |
for (int i = 0; i < arr.length - 1; i++) { | |
int minIndex = i; | |
for (int j = i + 1; j < arr.length; j++) { | |
if (arr[minIndex] > arr[j]) { | |
minIndex = j; | |
} | |
} | |
if (i != minIndex) { | |
int temp = arr[i]; | |
arr[i] = arr[minIndex]; | |
arr[minIndex] = temp; | |
} | |
} | |
System.out.println(Arrays.toString(arr)); | |
} | |
} |
# 查找算法 👇🏻
# 基本查找（顺序查找）
从前往后挨个查找
数据量大的时候，性能很差
# 二分查找（折半查找）
前提条件：数组中的数据必须是有序的
核心思想：每次排除一半的数据，查询数据的性能明显提高极多
二分查找正常的折半条件应该是 开始位置left <= 结束位置right
public class Test { | |
public static void main(String[] args) { | |
int[] arr = {7, 23, 79, 81, 103, 127, 131, 147}; | |
System.out.println(binarySearch(arr, 150)); | |
//java 自带的方法 | |
System.out.println(Arrays.binarySearch(arr, 81)); | |
} | |
public static int binarySearch(int[] arr, int data) { | |
int left = 0; | |
int right = arr.length - 1; | |
while (left <= right) { | |
int middle = (left + right) / 2; | |
if (data < arr[middle]) { | |
// 往左边找，截止位置（右边位置） = 中间位置 - 1 | |
right = middle - 1; | |
} else if(data > arr[middle]) { | |
// 往右边找，起始位置（左边位置） = 中间位置 + 1 | |
left = middle + 1; | |
} else { | |
// 中间位置处的元素值，正好等于要找的元素值 | |
return middle; | |
} | |
} | |
return -1; // 没有找到数据 | |
} | |
} |
# 正则表达式
由一些特定的字符组成，代表的是一个规则
- 用来校验数据格式是否合法
- 在一段文本中查找满足要求的内容
String 提供了一个匹配正则表达式的方法：
| 方法名 | 说明 |
|---|---|
| public boolean matches(String regex) | 判断字符串是否匹配正则表达式 匹配返回 true，不匹配返回 false |
# 书写规则
| 符号 | 含义 | 举例 |
|---|---|---|
| 数量词 👇🏻 | ||
| ? | 0 次或 1 次 | \\d? ➡ 0 次或 1 次的数字 |
| * | 0 次或多次 | \\d* ➡ 0 次或 1 次的数字(abc)* ➡ 0 次或 1 次的 abc |
| + | 1 次或多次 | \\d+ ➡ 1 次或多次的数字(abc)+ ➡ 1 次或多次的 abc |
| {} | 具体次数 | X {n} ➡ X，正好 n 次 X {n,} ➡ X，至少 n 次 X {n,m} ➡ X，至少 n 但不超过 m 次 |
| 字符类（只匹配单个字符）👇🏻 | ||
| (?i) | 忽略后面字符的大小写 | (?i) abc ➡ 忽略 abc 的大小写 a ((?i) b) c ➡ 只忽略 b 的大小写 |
| [] | 里面的内容出现一次 | [abc] ➡ 只能是 a, b, 或 c |
| ^ | 取反 | [^abc] ➡ 除了 a, b, c 之外的任何字符 |
| && | 交集，不能写单个的 & | [a-z&&m-p] ➡ m-p 的小写字母 |
| 预定义字符（只匹配单个字符）👇🏻 | ||
| . | 任意字符 | \n 回车符号不匹配 |
| \ | 转义字符 | \d ➡ 0-9 |
\\d | 0-9 | \\d+ ➡ 1 次或多次的数字 |
\\D | 非 0-9 | \\D+ ➡ 1 次或多次的数字 |
\\s | 空白字符 | |
\\S | 非空白字符 | [^\s] ➡ 一个非空白字符 |
\\w | 单词字符 | 等同于 [a-zA-Z_0-9] |
\\W | 非单词字符 | [^\w] ➡ 一个非单词字符 |
| () | 分组 | a (bc)+ ➡ a 和 1 次或多次的 bc |
| | | 写在方括号外面表示并集 | ab|AB ➡ ab 或 AB |
