六安网站怎么做seo,wordpress公众号模板,网站建设费用计什么科目,长春网站长春网络推广建设常见算法和Lambda 文章目录 常见算法和Lambda常见算法查找算法基本查找#xff08;顺序查找#xff09;二分查找/折半查找插值查找斐波那契查找分块查找扩展的分块查找#xff08;无规律的数据#xff09; 常见排序算法冒泡排序选择排序插入排序快速排序递归快速排序 Array…常见算法和Lambda 文章目录 常见算法和Lambda常见算法查找算法基本查找顺序查找二分查找/折半查找插值查找斐波那契查找分块查找扩展的分块查找无规律的数据 常见排序算法冒泡排序选择排序插入排序快速排序递归快速排序 ArraysLambda表达式函数式编程 常见算法
查找算法
基本查找顺序查找
核心:从0索引开始挨个往后查找
需求定义一个方法利用基本查找查找某个元素是否存在数据如下{131,127,147,81,103,23,7,79}
package com.example.demo;public class Text{public static void main(String[] args) {int [] arr {131,127,147,81,103,23,7,79};int number 81;System.out.println(basicSearch(arr,number));}private static boolean basicSearch(int[] arr, int number) {for (int i 0; i arr.length; i) {if(arr[i] number){return true;}}return false;}
}需求定义一个方法利用基本查找查询某个元素在数组中的索引要求不需要考虑数组中元素是否重复
package com.example.demo;public class Text{public static void main(String[] args) {int [] arr {131,127,147,81,103,23,7,79};int number 81;System.out.println(basicSearch(arr,number));}private static int basicSearch(int[] arr, int number) {for (int i 0; i arr.length; i) {if(arr[i] number){return i;}}return -1;}
}需求定义一个方法利用基本查找查询某个元素在数组中的索引要求需要考虑数组中元素有重复的可能性
package com.example.demo;import java.util.ArrayList;public class Text{public static void main(String[] args) {int [] arr {131,127,147,81,103,23,7,79,81};int number 81;System.out.println(basicSearch(arr,number));}private static ArrayListInteger basicSearch(int[] arr, int number) {ArrayListInteger list new ArrayList();for (int i 0; i arr.length; i) {if(arr[i] number){list.add(i);}}return list;}
}二分查找/折半查找
前提条件数组中的数据必须是有序的
核心思想每次排除一半的查找范围
min和max表示当前要查找的范围mid是在min和max中间的如果要查找的元素在mid的左边缩小范围时min不变max等于mid减一如果要查找的元素在mid的右边缩小范围max不变min等于mid加一
package com.example.demo;public class Text{public static void main(String[] args) {
// 需求定义一个方法利用二分查找查询某个元素在数组中的索引
// 数据如下{7,23,79,81,103,127,131,147}int [] arr {7,23,79,81,103,127,131,147};System.out.println(binarySearch(arr,131));}private static int binarySearch(int[] arr, int number) {
// 1.定义两个变量记录要查找的范围int min 0;int max arr.length-1;// 2.利用循环不断地去找要查找的数据while (true){if(min max){return -1;}// 3.找到min和max的中间位置int mid (min max)/2;
// 4.拿着mid指向的元素跟要查找的元素进行比较if (arr[mid] number){//4.1 number在mid的左边// min不变max min -1max mid - 1;}else if(arr[mid] number){//4.2 number子啊mid的右边//max不变min mid 1min mid 1;}else{//4.3 number跟mid指向的元素一样//找到了return mid;}}}
}插值查找
数组中的值分布比较均匀。 斐波那契查找 分块查找
前一块中的最大数据小于后一块中所有的数据块内无序块间有序块数数量一般等于数字的个数开根号。比如16个数字一般分为4块左右
核心思路先确定要查找的元素在哪一块然后在块内挨个查找。
package com.example.demo;public class Text{public static void main(String[] args) {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 30;// 调用方法传递索引表数组要查找的元素int index getIndex(blockArr,arr,number);// 打印System.out.println(index);}// 利用分块查找的原理查询number的索引
// 1.确定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.获取这一块的起始索引和结束索引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){//从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;}public int getMax() {return max;}public void setMax(int max) {this.max max;}public int getStartIndex() {return startIndex;}public void setStartIndex(int startIndex) {this.startIndex startIndex;}public int getEndIndex() {return endIndex;}public void setEndIndex(int endIndex) {this.endIndex endIndex;}Overridepublic String toString() {return Block{ max max , startIndex startIndex , endIndex endIndex };}
}扩展的分块查找无规律的数据 package com.example.demo;public class Text{public static void main(String[] args) {int[] arr {27,22,30,40,36,13,19,16,20,7,10,43,50,48};//创建三个的块对象Block b1 new Block(22,40,0,4);Block b2 new Block(13,20,5,8);Block b3 new Block(7,10,9,10);Block b4 new Block(43,50,11,13);// 定义数组用来管理三个块的对象索引表Block[] blockArr {b1,b2,b3,b4};// 定义一个变量用来记录要查找的元素int number 48;// 调用方法传递索引表数组要查找的元素int index getIndex(blockArr,arr,number);// 打印System.out.println(index);}// 利用分块查找的原理查询number的索引
// 1.确定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.获取这一块的起始索引和结束索引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){//从0索引开始遍历blockArr如果number小于max大于min那么就表示number是在这一块当中的。for (int i 0;i blockArr.length; i) {if(number blockArr[i].getMax() number blockArr[i].getMin()){return i;}}return -1;}}class Block{private int max;private int min;private int startIndex;private int endIndex;public Block() {}public Block(int min,int max, int startIndex, int endIndex) {this.min min;this.max max;this.startIndex startIndex;this.endIndex endIndex;}public int getMin() {return min;}public void setMin(int min) {this.min min;}public int getMax() {return max;}public void setMax(int max) {this.max max;}public int getStartIndex() {return startIndex;}public void setStartIndex(int startIndex) {this.startIndex startIndex;}public int getEndIndex() {return endIndex;}public void setEndIndex(int endIndex) {this.endIndex endIndex;}Overridepublic String toString() {return Block{ max max , min min , startIndex startIndex , endIndex endIndex };}
}常见排序算法
冒泡排序
相邻的数据两两比较小的放前面大的放后面。第一轮循环结束最大值已经找到在数组的最右边。第二轮可以少循环一次后面以此类推。如果数组中有n个数据总共我们只要执行n-1轮的代码就可以。
package com.example.demo;public class Text {public static void main(String[] args) {
// 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) {if(arr[j] arr[j1]){int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}for (int i 0; i arr.length; i) {System.out.println(arr[i] );}}
}选择排序
从0索引开始拿着每一个索引上的元素跟后面的元素依次比较小的放前面大的放后面以此类推。第一轮结束后最小的数据已经确定
package com.example.demo;public class Text {public static void main(String[] args) {
// 1.定义数组int[] arr {2, 4, 5, 3, 1};// 2.利用选择排序让数组变成1 2 3 4 5for (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.print(arr[i] );}}
}插入排序
将0索引的元素到N索引的元素看做是有序的把N1索引的元素到最后一个当成是无序的。遍历无序的数据将遍历的元素插入有序序列中适当的位置如遇到相同数据插在后面。N的范围0~最大索引
package com.example.demo;public class Text {public static void main(String[] args) {
// 1.定义数组int[] arr {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};// 2.找到无序的那一组数组是从哪个索引开始的int startIndex -1;for (int i 0; i arr.length; i) {if(arr[i] arr[i1] ){startIndex i 1;break;}}// 3.遍历从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--;}}for (int i 0; i arr.length; i) {System.out.print(arr[i] );}}
}快速排序
递归
方法中调用方法本身的现象
注意点:递归一定要有出口否则就会出现内存溢出
作用把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算
package com.example.demo;public class Text {public static void main(String[] args) {//求1~100之间的和System.out.println(getSum(100));}public static int getSum(int number){if(number 1){return 1;}// 如果number不是1return number getSum(number-1);}
}package com.example.demo;public class Text {//求5的阶乘public static void main(String[] args) {System.out.println(getFactorial(5));}public static int getFactorial(int number){if(number 1){return 1;}
// 如果number不是1return number * getFactorial(number-1);}
}快速排序
第一轮把0索引的数字作为基准数确定基准数在数组中正确的位置。
比基准数小的全部在左边比基准数大的全部在右边。
package com.example.demo;public class Text {public static void main(String[] args) {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;}
// 当start和end直系那个了同一个元素的时候那么上面的循环就会结束
// 表示已经找到了基准数在数组中应存入的位置
// 基准数归位int temp arr[i];arr[i] arr[start];arr[start] temp;// 确定6左边的范围重复刚刚所做的事情quickSort(arr,i,start-1);
// 确定6右边的范围重复刚刚所做的事情quickSort(arr,start1,j);}}Arrays
操作数组的工具类 Lambda表达式
函数式编程
是一种思想特点。函数式编程思想忽略面向对象的复杂语法强调做什么而不是谁去做。
