查找算法基本查找/顺序查找基本思想顺序查找也称为线形查找属于无序查找算法。从数据结构线的一端开始顺序扫描依次将遍历到的结点与要查找的值相比较若相等则表示查找成功若遍历结束仍没有找到相同的表示查找失败。二分查找/折半查找tips元素必须是有序的从小到大或者从大到小。基本思想插值查找基本思想基于二分查找算法将查找点的选择改进为自适应选择可以提高查找效率。当然差值查找也属于有序查找。细节对于表长较大而关键字分布又比较均匀的查找表来说插值查找算法的平均性能比折半查找要好的多。反之数组中如果分布非常不均匀那么插值查找未必是很合适的选择斐波那契查找基本思想也是二分查找的一种提升算法通过运用黄金比例的概念在数列中选择查找点进行查找提高查找效率。同样地斐波那契查找也属于一种有序查找算法。斐波那契查找也是在二分查找的基础上进行了优化优化中间点mid的计算方式即可分块查找分块的原则1.前一块中的最大数据小于后一块中的所有数据(块内无序块间有序)2.块数数量一般等于数字的个数开根号核心思路先确定要查找的元素在哪一块然后在块内挨个查找package com.itheima.search; public class A03_BlockSearchDemo { 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); //定义数组用来管理三个块的对象索引表 Block[] blockArr {b1,b2,b3}; //定义一个变量用来记录要查找的元素 int number 37; //调用方法传递索引表数组要查找的元素 int index getIndex(blockArr,arr,number); //打印一下 System.out.println(index); } //利用分块查找的原理查询number的索引 private static int getIndex(Block[] blockArr, int[] arr, int number) { //1.确定number是在那一块当中 int indexBlock findIndexBlock(blockArr, number); if(indexBlock -1){ //表示number不在数组当中 return -1; } //2.获取这一块的起始索引和结束索引 --- 30 // Block b1 new Block(21,0,5); ---- 0 // Block b2 new Block(45,6,11); ---- 1 // Block b3 new Block(73,12,17); ---- 2 int startIndex blockArr[indexBlock].getStartIndex(); int endIndex blockArr[indexBlock].getEndIndex(); //3.遍历 for (int i startIndex; i lt; endIndex; i) { if(arr[i] number){ return i; } } return -1; } //定义一个方法用来确定number在哪一块当中 public static int findIndexBlock(Block[] blockArr,int number){ //100 //从0索引开始遍历blockArr如果number小于max那么就表示number是在这一块当中的 for (int i 0; i lt; blockArr.length; i) { if(number lt; blockArr[i].getMax()){ 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 }; } }排序算法冒泡排序冒泡排序1.相邻数据的两两比较小的放前面大的放后面。2.第一轮循环结束最大值已经找到第二轮可以少循环一次后面以此类推3.如果数组中有n个数据总共我们只要执行n-1轮的代码就可以public class A01_BubbleDemo { public static void main(String[] args) { /* 冒泡排序 核心思想 1相邻的元素两两比较大的放右边小的放左边。 2第一轮比较完毕之后最大值就已经确定第二轮可以少循环一次后面以此类推。 3如果数组中有n个数据总共我们只要执行n-1轮的代码就可以。 */ //1.定义数组 int[] arr {2, 4, 5, 3, 1}; //2.利用冒泡排序将数组中的数据变成 1 2 3 4 5 //外循环表示我要执行多少轮。 如果有n个数据那么执行n - 1 轮 for (int i 0; i lt; arr.length - 1; i) { //内循环每一轮中我如何比较数据并找到当前的最大值 //-1为了防止索引越界 //-i提高效率每一轮执行的次数应该比上一轮少一次。 for (int j 0; j lt; arr.length - 1 - i; j) { //i 依次表示数组中的每一个索引0 1 2 3 4 if(arr[j] gt; arr[j 1]){ int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } printArr(arr); } private static void printArr(int[] arr) { //3.遍历数组 for (int i 0; i lt; arr.length; i) { System.out.print(arr[i] ); } System.out.println(); } }选择排序算法步骤1.从0索引开始跟后面的元素一 一比较。小的放前面大的放后面2.第一次循环结束后最小的数据已经确定3.第二次循环从1索引开始以此类推4.第三轮循环从2索引开始以此类推public class A02_SelectionDemo { public static void main(String[] args) { /* 选择排序 1从0索引开始跟后面的元素一一比较。 2小的放前面大的放后面。 3第一次循环结束后最小的数据已经确定。 4第二次循环从1索引开始以此类推。 */ //1.定义数组 int[] arr {2, 4, 5, 3, 1}; //2.利用选择排序让数组变成 1 2 3 4 5 /* //第一轮 //从0索引开始跟后面的元素一一比较。 for (int i 0 1; i lt; arr.length; i) { //拿着0索引跟后面的数据进行比较 if(arr[0] gt; arr[i]){ int temp arr[0]; arr[0] arr[i]; arr[i] temp; } }*/ //最终代码 //外循环几轮 //i:表示这一轮中我拿着哪个索引上的数据跟后面的数据进行比较并交换 for (int i 0; i lt; arr.length -1; i) { //内循环每一轮我要干什么事情 //拿着i跟i后面的数据进行比较交换 for (int j i 1; j lt; arr.length; j) { if(arr[i] gt; arr[j]){ int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } } printArr(arr); } private static void printArr(int[] arr) { //3.遍历数组 for (int i 0; i lt; arr.length; i) { System.out.print(arr[i] ); } System.out.println(); } }插入排序插入排序将0索引的元素到N索引的元素看做是有序的把N1索引的元素到最后一个当成是无序的。遍历无序的数据将遍历到的元素插入有序序列中适当的位置如遇到相同的数据插在后面。N的范围0~最大索引package com.itheima.mysort; public class A03_InsertDemo { 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}; //1.找到无序的哪一组数组是从哪个索引开始的。 2 int startIndex -1; for (int i 0; i lt; arr.length; i) { if(arr[i] gt; arr[i 1]){ startIndex i 1; break; } } //2.遍历从startIndex开始到最后一个元素依次得到无序的哪一组数据中的每一个元素 for (int i startIndex; i lt; arr.length; i) { //问题如何把遍历到的数据插入到前面有序的这一组当中 //记录当前要插入数据的索引 int j i; while(j gt; 0 arr[j] lt; 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) { //3.遍历数组 for (int i 0; i lt; arr.length; i) { System.out.print(arr[i] ); } System.out.println(); } }快速排序递归算法递归指的是方法中调用方法本身的现象递归的注意点递归一定要有出口否则就会出现内存溢出算法步骤从数列中挑出一个元素一般都是左边第一个数字称为 “基准数”;创建两个指针一个从前往后走一个从后往前走。先执行后面的指针找出第一个比基准数小的数字再执行前面的指针找出第一个比基准数大的数字交换两个指针指向的数字直到两个指针相遇将基准数跟指针指向位置的数字交换位置称之为基准数归位。第一轮结束之后基准数左边的数字都是比基准数小的基准数右边的数字都是比基准数大的。把基准数左边看做一个序列把基准数右边看做一个序列按照刚刚的规则递归排序package com.itheima.mysort; import java.util.Arrays; public class A05_QuickSortDemo { public static void main(String[] args) { System.out.println(Integer.MAX_VALUE); System.out.println(Integer.MIN_VALUE); /* 快速排序 第一轮以0索引的数字为基准数确定基准数在数组中正确的位置。 比基准数小的全部在左边比基准数大的全部在右边。 后面以此类推。 */ int[] arr {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8}; //int[] arr new int[1000000]; /* Random r new Random(); for (int i 0; i lt; arr.length; i) { arr[i] r.nextInt(); }*/ long start System.currentTimeMillis(); quickSort(arr, 0, arr.length - 1); long end System.currentTimeMillis(); System.out.println(end - start);//149 System.out.println(Arrays.toString(arr)); //课堂练习 //我们可以利用相同的办法去测试一下选择排序冒泡排序以及插入排序运行的效率 //得到一个结论快速排序真的非常快。 /* for (int i 0; i lt; 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 gt; end){ //递归的出口 return; } //记录基准数 int baseNumber arr[i]; //利用循环找到要交换的数字 while(start ! end){ //利用end从后往前开始找找比基准数小的数字 //int[] arr {1, 6, 2, 7, 9, 3, 4, 5, 10, 8}; while(true){ if(end lt; start || arr[end] lt; baseNumber){ break; } end--; } System.out.println(end); //利用start从前往后找找比基准数大的数字 while(true){ if(end lt; start || arr[start] gt; baseNumber){ break; } start; } //把end和start指向的元素进行交换 int temp arr[start]; arr[start] arr[end]; arr[end] temp; } //当start和end指向了同一个元素的时候那么上面的循环就会结束 //表示已经找到了基准数在数组中应存入的位置 //基准数归位 //就是拿着这个范围中的第一个数字跟start指向的元素进行交换 int temp arr[i]; arr[i] arr[start]; arr[start] temp; //确定6左边的范围重复刚刚所做的事情 quickSort(arr,i,start - 1); //确定6右边的范围重复刚刚所做的事情 quickSort(arr,start 1,j); } }常见算法的API-Arrays操作数组的工具类public static void sort(数组排序规则)细节-只能给引用数据类型的数组进行排序如果数组是基本数据类型的需要变成其对于的包装类。Lambda表达式Lambda表达式是JDK08开始后的一种信新语法表达式 对应着方法的形参 - 固定格式 { } 对应着方法的方法体注意点1.Lambda表达式可以用来简化匿名内部类的书写2.Lambda表达式只能简化函数式接口的匿名内部类的写法3.函数式接口有且只有一个抽象方法的接口叫接口上方可以Functionlinterface注解Lambda表达式的和省略规则1.参数类型可以省略不写2.如果只有一个参数参数类型可以省略同时( )也可以省略3.如果Lambda表达式的方法体只有一行分号return可以省略不写需要同时省略