一.查找算法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加1public 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.61mid min 黄金分割点左半边长度 -16.数表查找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索引的元素看作是有序的,把N1索引的元素到最后一个当成是无序的。遍历无序的数据,将遍历到的元素插入有序序列中适当的位置,如遇到相同的数据插到后面N的范围:0~最大索引public static void main(String[] args) { //插入排序: //将0索引的元素到N索引的元素看作是有序的,把N1索引的元素到最后一个当成是无序的 //遍历无序的数据将遍历到的元素插入有序序列中适当的位置如遇到相同数据插在后面 //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,endstart从前往后找比基准数大的,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可以省略不写,需要同时省略
