1.常见算法
（1）查找算法
1.查找方式
基本查找，二分查找，分块查找，插值查找，斐波那契查找，树表查找，哈希查找
2.基本查找
也叫顺序查找，从0索引开始挨个往后查找
public class Text1 {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9,0};
System.out.println(basicSearch(arr, 5));
}
public static boolean basicSearch(int[] arr, int number){
for (int j : arr) {
if (j == number) {
return true;
}
}
return false;
}
}3.二分查找
（1）二分查找
也叫折半查找，数组中的数据必须是有序的，每次排除一半的查找范围
public class Text1 {
public static void main(String[] args) {
int[] arr = {0,1,2,3,4,5,6,7,8,9};
System.out.println(binarySearch(arr, 9));
}
public static int binarySearch(int[] arr, int number){
int min = 0;
int max = arr.length - 1;
int mid = 0;
while(min <= max){
mid = (min + max) / 2;
if(arr[mid] == number){
return mid;
}
else if(arr[mid] < number){
min = mid+1;
}
else if(arr[mid] > number){
max = mid-1;
}
}
return -1;
}
}（2）二分查找步骤
1.min和max表示当前要查找的范围
2.mid是在min和max中间
3.如果要查找的元素在mid的左边，缩小范围时，min不变，max等于min-1
4.如果要查找的元素在mid的右边，缩小范围时，max不变，min等于mid+1
（3）二分查找、插值查找、斐波那契查找
1.相同点
都是通过不断的缩小范围来查找对应的数据
2.不同点
（1）二分查找：mid每次都是指向范围的中间位置
（2）插值查找：mid尽可能的靠近要查找的数据，但是要求数据尽可能的分布均匀
（3）斐波那契查找：根据黄金分割点来计算mid指向的位置
4.分块查找
（1）分块的原则
1.前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）
2.块数数量一般等于数字的个数开根号
public class BlockSearch {
// 索引表结构
static class Index {
int maxValue; // 块内最大值
int start; // 块起始位置
int end; // 块结束位置
public Index(int maxValue, int start, int end) {
this.maxValue = maxValue;
this.start = start;
this.end = end;
}
}
/**
* 分块查找
* @param arr 原始数组
* @param indexes 索引表
* @param key 要查找的值
* @return 找到返回索引，否则返回-1
*/
public static int blockSearch(int[] arr, Index[] indexes, int key) {
// 1. 先在索引表中确定可能所在的块
int blockIndex = findBlock(indexes, key);
if (blockIndex == -1) {
return -1; // 不在任何块中
}
// 2. 在确定的块内进行顺序查找
int start = indexes[blockIndex].start;
int end = indexes[blockIndex].end;
for (int i = start; i <= end; i++) {
if (arr[i] == key) {
return i;
}
}
return -1; // 块内未找到
}
// 在索引表中查找key可能所在的块
private static int findBlock(Index[] indexes, int key) {
for (int i = 0; i < indexes.length; i++) {
if (key <= indexes[i].maxValue) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
// 原始数组（块内无序，块间有序）
int[] arr = {3, 2, 1, 5, 9, 8, 7, 13, 12, 11, 16, 15, 14};
// 创建索引表（每块最大值、起始和结束位置）
Index[] indexes = {
new Index(5, 0, 3), // 第一块最大值5，范围0-3
new Index(9, 4, 6), // 第二块最大值9，范围4-6
new Index(13, 7, 9), // 第三块最大值13，范围7-9
new Index(16, 10, 12) // 第四块最大值16，范围10-12
};
// 测试查找
System.out.println("查找 7 的位置: " + blockSearch(arr, indexes, 7)); // 输出: 6
System.out.println("查找 12 的位置: " + blockSearch(arr, indexes, 12)); // 输出: 8
System.out.println("查找 4 的位置: " + blockSearch(arr, indexes, 4)); // 输出: -1
}
}（2）排序算法
1.冒泡排序
（1）冒泡排序
相邻的数据两两比较，小的放前面，大的放后面（从小到大）
（2）步骤
1.相邻的元素两两比较，大的放右边，小的放左边
2.第一轮循环结束，最大值已经找到，在数组的最右边，第二轮可以少循环一次，后面依次类推（如果数组中有n个数据，只需要执行n-1轮的代码就可以）
3.依次循环找到剩余元素的最大值
public class Text1 {
public static void main(String[] args) {
int[] arr = {5,3,2,1,4};
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}2.选择排序
（1）选择排序
从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面（从小到大排序）
（2）步骤
1.从0索引开始，跟后面一一比较，小的放前面，大的放后面
2.第一轮循环结束后，最小的数据已经确定
3.依次循环
public class Text1 {
public static void main(String[] args) {
int[] arr = {5,3,2,1,4};
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; i++) {
System.out.println(arr[i]);
}
}
}3.插入排序
（1）插入排序
将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的，遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同的数据，插在后面（N的范围：0~最大索引）
public class Text1 {
public static void main(String[] args) {
int[] arr = {5,3,2,1,4};
int start = -1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
//找到无序的开始索引
start = i + 1;
break;
}
}
//遍历start开始到最后一个元素，依次得到无序那一组的每一个索引
for (int i = start; i < arr.length; i++) {
//记录当前要插入数据的索引
int j = i;
while(j > 0 && arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}4.递归算法
（1）递归算法
1.递归指的是方法中调用方法本身的现象
2.递归一定要有出口，否则就会出现内存溢出
（2）作用
1.把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题求解
2.递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算
5.快速排序
（1）快速排序
把0索引的数字作为基准数，确定基准数在数组中正确的位置，比基准数小的全部在左边，比基准数大的全部在右边，再把左右两边的数据重复此操作
public class Text1 {
public static void main(String[] args) {
int[] arr = {5,6,3,2,8,1,7,9,4};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void quickSort(int[] arr, int i, int j) {
//定义两个变量记录要查找的范围
int start = i;
int end = j;
//递归的出口5
if (start > end) {
return;
}
//记录基准数
int baseNume = arr[i];
//利用循环找到要交换的数字
while (start != end) {
//利用end，从后往前开始找，找到比基准数小的数字(一定要先移动end，不能先移动start)
while (true){
if(end <= start || arr[end] < baseNume){
break;
}
end--;
}
//利用start，从前往后开始找，找到比基准数大的数字
while (true){
if(end <= start || arr[start] > baseNume){
break;
}
start++;
}
//把end和start指向的元素进行交换
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//基准数归为，左边全为小于基准数的数，右边全为大于基准数的数
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
//确定基准数左边的范围，重复刚才的步骤
quickSort(arr, i, start-1);
//确定基准数右边的范围，重复刚才的步骤
quickSort(arr, start+1, j);
}
}