一.查找算法
1.基本查找/顺序查找
核心:从0索引开始挨个往后查找
public static void main(String[] args) { //基本查找/ //原理:从0索引开始以此查找 int[] arr = {131,127,147,81,103,23,7,79}; int number = 82; System.out.println(basicSearch(arr, number)); } public static boolean basicSearch(int[] arr, int number) { for (int i = 0; i < arr.length; i++) { if (arr[i] == number){ return true; } } return false; }2.二分查找/折半查找
前提:数组中的数据必须是有序的,如果数据是乱的,先排序再用二分查找得到的索引没有实际意义,只能确定当前数字在数组中是否存在,因为排序之后的数字的位置就可能发生变化了
核心逻辑:每次排除一半的查找范围
优势:提高查找效率
查找过程:
min和max表示当前要查找的范围
mid是在min和max中间的
如果要查找的元素再mid的左边,缩小范围时,min不变,max等于mid减1
如果要查找的元素在mid的右边,缩小范围是,max不变,min等于mid加1
public static void main(String[] args) { //二分查找/折半查找 //核心:每次排除一半的查找范围 int[] arr = {7,23,79,81,103,127,131,147}; int number = 147; System.out.println(binarySearch(arr, number)); } public static int binarySearch(int[] arr, int number) { int min = 0; int max = arr.length - 1; while (true){ if (min > max){ return -1; } int mid = (min + max) / 2; if (arr[mid] > number){ //number在mid左边 max = mid - 1; } else if (arr[mid] < number) { //number在mid右边 min = mid + 1; }else { return mid; } } }3.分块查找
分块的原则:
1.前一块中的最大数据,小于后一块中所有的数据(块内无序,快间有序)
2.块数数量一般等于数字的个数开根号
核心思路:先确定要查找的元素在哪一块,然后在块内挨个查找
实现步骤:
1.创建数组blockArr存放每一块对象的信息
2.先查找blockArr确定要查找的数据属于那一块
3.再单独遍历这一块数据即可
public static void main(String[] args) { //分块查找 //核心思想:块内无序,块间有序 //实现步骤: //1.创建数组blockArr存放每一个块对象的信息 //2.先查找blockArr确定要查找的数据属于那一块 //3.再单独遍历这一块数据即可 int[] arr = {16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66}; //创建三个块的对象 Block b1 = new Block(21, 0, 5); Block b2 = new Block(45, 6, 11); Block b3 = new Block(73, 12, 17); //创建数组blockArr(索引表) Block[] blockArr = {b1, b2, b3}; //创建要查找的数据对象 int number= 23; //调用方法,传递索引表，数组，要查找的元素 int index = getIndex(blockArr,arr,number); //输出打印 System.out.println(index); } //利用分块查询的原理,查询number的索引 private static int getIndex(Block[] blockArr,int[] arr,int number) { int indexBlock = findIndexBlock(blockArr, number); if (indexBlock == -1){ //要查找的数据不在数组中 return -1; } int startIndex = blockArr[indexBlock].getStartIndex(); int endIndex = blockArr[indexBlock].getEndIndex(); for (int i = startIndex; i <= endIndex; i++) { if (arr[i] == number){ return i; } } return -1; } //定义方法判断要查找的索引在那个代码块 public static int findIndexBlock(Block[] blockArr,int number){ for (int i = 0; i < blockArr.length; i++) { if (blockArr[i].getMax() >= number){ return i; } } return -1; } } class Block { private int max; private int startIndex; private int endIndex; public Block() { } public Block(int max, int startIndex, int endIndex) { this.max = max; this.startIndex = startIndex; this.endIndex = endIndex; } /** * 获取 * * @return max */ public int getMax() { return max; } /** * 设置 * * @param max */ public void setMax(int max) { this.max = max; } /** * 获取 * * @return startIndex */ public int getStartIndex() { return startIndex; } /** * 设置 * * @param startIndex */ public void setStartIndex(int startIndex) { this.startIndex = startIndex; } /** * 获取 * * @return endIndex */ public int getEndIndex() { return endIndex; } /** * 设置 * * @param endIndex */ public void setEndIndex(int endIndex) { this.endIndex = endIndex; } public String toString() { return "block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}"; }4.插值查找
mid = min + (key - arr[min]) / (arr[max] - arr[min]) * (max - min)
和二分查找类似,区别在于中间值计算的不同
mid尽可能的靠近要查找的数据,但是要求数据尽可能的分布均匀
5.斐波那契查找
找黄金分割点,即左边和右边的长度比是1:0.61
mid = min + 黄金分割点左半边长度 -1
6.数表查找
7.哈希查找
二.排序算法
1.冒泡排序
核心思想:
1.相邻的元素两两比较,大的放右边,小的放左边
2.第一轮比较完毕之后,最大值就已经确定, 第二轮可以少循环一次,后面以此类推
3.如果数组中有n个数据,总共执行n-1轮代码即可
public static void main(String[] args) { //冒泡排序: //1.相邻的元素两两比较,大的放右边,小的放左边 //2.第一轮比较完毕之后,最大值就已经确定,第二轮可以少循环一次,后面以此类推 //3.如果数组中有n个数据,总共只要执行n-1轮的代码就可以 int[] arr = {2,4,5,3,1}; //外循环:一共循环多少次 for (int i = 0; i < arr.length - 1; i++) { //内循环:每一轮中如何找到本轮最大值 //-1 防止索引越界 //-i 提高效率,每一轮执行的次数应比上一轮少一次 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]){ int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }2.选择排序
核心思想:
1.从0索引开始,跟后面的元素一一比较
2.小的放前面,大的放后面
3.第一次循环结束后,最小的数据已经确定
4.第二次循环从1索引开始以此类推
public static void main(String[] args) { //选择排序: //1.从0索引开始，跟后面的元素一一比较 //2.小的放前面，大的放后面 //3.第一次循环结束后，最小的数据已经确定 //4.第二次循环从1索引开始以此类推 //定义数组 int[] arr = {2,4,5,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; } } } printArr(arr); } private static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); }3.插入排序
核心思想:将0索引的元素到N索引的元素看作是有序的,把N+1索引的元素到最后一个当成是无序的。遍历无序的数据,将遍历到的元素插入有序序列中适当的位置,如遇到相同的数据插到后面
N的范围:0~最大索引
public static void main(String[] args) { //插入排序: //将0索引的元素到N索引的元素看作是有序的,把N+1索引的元素到最后一个当成是无序的 //遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面 //N的范围:0~最大索引 int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; //定义无序数据起始索引 int startIndex = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] > arr[i + 1]){ startIndex = i + 1; break; } } //遍历无序索引,进行插入排序 for (int i = startIndex; 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--; } } printArr(arr); } private static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); }4.快速排序
第一轮:以0索引的数字为基准数,确定基准数在数组中正确的位置。比基准数小的全部在左边,比基准数大的全部在右边。后面以此类推
整体核心思路:
将排序范围中的第一个数字作为基准数,再定义两个变量start,end
start从前往后找比基准数大的,end从后往前找比基准数小的
找到之后交换start和end指向的元素,并循环这一过程,知道start和end处于同一个位置,该位置是基准数在数组中应存入的位置,在让基准数归为
public static void main(String[] args) { //快速排序: //第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置 //比基准数小的全部在左边，比基准数大的全部在右边 //后面以此类推 int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8}; quickSort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void quickSort(int[] arr, int i, int j) { //定义两个变量记录查找的范围 int start = i; int end = j; //递归的出口 if (start > end){ return; } //定义基准数 int baseNumber = arr[i]; //利用循环找到要交换的数组 while (start != end){ //利用end，从后往前找，找到比基准数小的数据 while (true){ if (end <= start || arr[end] < baseNumber){ break; } end--; } //利用start，从前往后找，找到比基准数大的数据 while (true){ if (end <= start || arr[start] > baseNumber){ break; } start++; } //把end和start指向的元素进行交换 int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } //基准数归位 int temp = arr[start]; arr[start] = baseNumber; arr[i] = temp; //确定基准数左边的范围,重复执行上述操作 quickSort(arr,i,start - 1); //确定基准数右边的范围，重复执行上述操作 quickSort(arr,end + 1,j); }5.希尔排序
6.堆排序
7.桶排序
8.归并排序
9.计数排序
10.基数排序
三.递归算法
介绍:指方法中调用方法本身的现象
注意:递归一定要有出口,否则就会出现内存溢出
作用:把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算
核心:1.找出口:什么时候不再调用方法
2.找规则:如何把大问题变成规模较小的问题
public static void main(String[] args) { //需求:利用递归求1-100之间的和 // 100 + 99 + 99 + ... + 2 + 1 //大问题拆解成小问题 //1~100之间的和 = 100 + （1~99之间的和） //1~99之间的和 = 99 + （1~98之间的和） //1~98之间的和 = 98 + （1~97之间的和） //... //1~2之间的和 = 2 + （1~1之间的和） //1~1之间的和 = 1（递归的出口） //核心: //1.找出口 //2.找规律 System.out.println(getSum(100)); } public static int getSum(int number){ if (number == 1){ return 1; } return number + getSum(number - 1); }四.Arrays
介绍:操作数组的工具类
| 方法名 | 说明 |
| public static String toString(数组) | 把数组拼接成一个字符串 |
| public static int binarySearch(数组,查找的元素) | 二分查找法查找元素 |
| public static int[] copyOf(原数组,新数组长度) | 拷贝数组 |
| public static int[] copyOfRange(原数组,起始索引,结束索引) | 拷贝数组(指定范围) |
| public static void fill(数组,元素) | 填充数组 |
| public static void sort(数组) | 按照默认方式进行数组排序 |
| public static void sort(数组,排序规则) | 按照指定的规则排序 |
binarySearch:二分查找法查找元素
细节:1.二分查找的前提:数组红的元素必须是有序,数组中的元素必须是升序的
2.如果要查找的元素是存在的,那么返回的是真实的索引
如果要查找的元素书不存在的,返回的是-插入点 -1
-1的原因:如果要查找数字0,数字0在数组中不存在,那么返回的值是-插入点,应该是就是-0而-0和0是一样的,会被误解为0索引,为了避免这样的情况,Java会在这个基础上又减一
copyOf:拷贝数组
方法的底层会根据第二个参数来创建新的数组
如果新数组的长度是小于老数组的长度,会部分拷贝
如果新数组的长度是等于老数组的长度,会完全拷贝
如果新数组的长度是大于老数组的长度,会补上默认初始值
copyOfRange:拷贝数组(指定范围)
细节:包头不包尾,包左不包右
sort:排序
默认情况下给数组进行升序排序。底层使用的是快速排序
sort:指定的规则排序
细节:只能给引用数据类型的数组进行排序
如果数组是基本数据类型,需要变成其对应的包装类
底层原理:利用插入排序+二分查找的方式进行排序。默认吧0索引的数据当作是有序的序列,1索引到最后认为是无序的序列。遍历无序的序列得到里面的每一个元素,假设当前遍历得到的元素是A元素,把A往有序序列中进行插入,在插入时,利用二分查找确定A元素的插入点。拿着A元素和插入点的元素进行比较,比较的规则就是compare方法的方法体。如果方法的返回值是负数,拿着A继续跟前面的数据进行比较;如果方法的返回值是正数,拿着A继续跟后面的数据进行比较;如果方法的返回值是0,也拿着A跟后面的数据进行比较知道能确定A的最终位置为止
compare方法的形式参数:
参数一 o1: 表示在无序序列中,遍历得到的每一个元素
参数二 o2: 有序序列的元素
返回值:
负数:表示当前要插入的元素是小的,放在前面
正数:表示当前要插入的元素是大的,放在后面
0:表示当前要插入的元素跟现在的元素比是一样的也会放在后面
五.Lambda表达式
函数式编程:一种思想特点,忽略面向对象的复杂语法,强调做什么,而不是谁去做,lambda表达式就是函数式思想的体现
面向对象:先找对象,让对象做事情
Lambda作用:简化函数式接口的匿名内部类的写法
Lambda好处:Lambda是一个匿名函数,可以把Lambda表达式理解为是一段可以传递的代码,它可以写出更简洁、更灵活的代码,作为一种更紧凑的代码风格,使Java语言表达能力得到提升
Lambda表达式的标准格式:
Lambda表达式时JDK8开始后的一种新语法形式
() ->{
}
() 对应着方法的形参
-> 固定格式
{} 对应着方法的方法体
注意:1.Lambda表达式可以用来简化匿名内部类的书写
2.Lambda表达式只能简化函数式接口的匿名内部类的写法
函数式接口:有且仅有一个抽象方法的接口叫做函数式接口,接口上方可以加@FunctionalInterface注解
Lambda表达式的省略写法:
核心:可推导,可省略
省略规则:
1.参数类型可以省略不写
2.如果只有一个参数,参数类型可以省略,同时()也可以省略
3.如果Lambda表达式的方法体只有一行,大括号,分号，return可以省略不写,需要同时省略
