查找算法：
基本查找/顺序查找
基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。
二分查找/折半查找
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 <= 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 < blockArr.length; i++) { if(number <= 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 < arr.length - 1; i++) { //内循环：每一轮中我如何比较数据并找到当前的最大值 //-1：为了防止索引越界 //-i：提高效率，每一轮执行的次数应该比上一轮少一次。 for (int j = 0; j < arr.length - 1 - i; j++) { //i 依次表示数组中的每一个索引：0 1 2 3 4 if(arr[j] > 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 < 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 < arr.length; i++) { //拿着0索引跟后面的数据进行比较 if(arr[0] > arr[i]){ int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; } }*/ //最终代码： //外循环：几轮 //i:表示这一轮中，我拿着哪个索引上的数据跟后面的数据进行比较并交换 for (int i = 0; i < arr.length -1; i++) { //内循环：每一轮我要干什么事情？ //拿着i跟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) { //3.遍历数组 for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }插入排序
插入排序：将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同的数据，插在后面。
N的范围：0~最大索引
package com.itheima.mysort; public class A03_InsertDemo { 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}; //1.找到无序的哪一组数组是从哪个索引开始的。 2 int startIndex = -1; for (int i = 0; i < arr.length; i++) { if(arr[i] > arr[i + 1]){ startIndex = i + 1; break; } } //2.遍历从startIndex开始到最后一个元素，依次得到无序的哪一组数据中的每一个元素 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) { //3.遍历数组 for (int i = 0; i < 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 < 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 < 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，从后往前开始找，找比基准数小的数字 //int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8}; while(true){ if(end <= start || arr[end] < baseNumber){ break; } end--; } System.out.println(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; } //当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可以省略不写，需要同时省略
