-
算法学习的积累
查找算法(7)
基本查找
- 条件：可以适应无序查找
顺序查找
package src.AlgorithmTest.Search; import java.util.Scanner; public class Sequence { public static void main(String[] args) { /*基本查找，顺序查找，按索引查找*/ int[] arr = {1222, 323, 444, 555, 666, 77754436, 89, 000}; Scanner sc = new Scanner(System.in); System.out.println("请输入要查找的数字"); int num = sc.nextInt(); boolean search = Search(arr, num); System.out.println(search); } private static boolean Search(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { if (arr[i] == num) { return true; } } return false; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
(折半/二分)查找
二分查找的优势？ 查找效率高 二分查找的条件？ 1.数据必须有序 2.数据是乱的排序了之后的索引发生了改变，就没有实际意义- 1
- 2
- 3
- 4
- 5
二分查找的过程：
1.min和max表示当前要查找的范围
2.mid是在min和max中间的
3.num在中间索引数字的右边，去掉左边，mid+1;
4.num在中间索引数字的右边，去掉左边，mid+1前提条件
- 数组中的数据必须是有有序的
核心逻辑
- 每次排除一半次查找范围
package src.AlgorithmTest.Search; import java.util.Scanner; public class DichotomyTest { /*对于学习二分查找法的记录*/ public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("输入查找的数据"); int num = sc.nextInt(); int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int dichotomy = dichotomy(arr, num); System.out.println(dichotomy); } private static int dichotomy(int[] arr, int num) { /*定义索引来表示最大最小索引*/ int min = 0; int max = arr.length - 1; while (true) { if (min > max) {/*循环结束的条件*/ return -1; } int mid = (min + max) / 2;/*中间索引位置*/ if (num > arr[mid]) {/*num在中间索引数字的右边，去掉左边，mid+1*/ min = mid + 1; } else if (num < arr[mid]) {/*num在中间索引数字的左边，去掉右边，mid-1*/ max = mid - 1; } else { return mid; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
分块查找：
1.分块的原则：块内无序，块间有序；但是前一块中的最大的<后面一块的最大的 2.块数的原则：分块的数量一般是块的个数开根号- 1
- 2
核心思路 1.先确定元素在哪一个块里面，然后在块内挨个查找。- 1
- 2
创建对象Block来表示块对象: class Block { /*块内最大值*/ int max; /*起始索引*/ int startIndex; /*结束索引*/ int endIndex; } 需要创建多个这样的对象来表示块，将这些块对象放入一个数组里面，形成了专有名称索引表- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
对于无规律的数据，通过合理的分组来保证分组的原则正确，就可以使用分块查找，但是block中的属性多了一个 int min;
在存放一个随机的数据，要保证不能重复，可以将存放的个数进行分块处理，然后随机数字在放入对应的块中，如果块中有数据则将数据挂载在后面。
-
课后扩展查找
- 插值查找
- 条件：数据要有序
缺点:在数据分布不均匀的情况下，跳跃的位置比较大，效率会降低
他的本质和二分查找是一样的但是他的效率非常高，他的前提条件必须是分布均匀的且有序排列的，通过查找他的索引所占的大概，位置，最后加上偏移量来实现快速查找
-
斐波那契查找
- 条件：数据有序
- 树表查找
- 哈希查找
-
排序算法
- 冒泡排序
相邻的数据两个进行比较，小的放前面，大的放后面，元素个数为了，循环的总次数为：n-1
package src.AlgorithmTest.Sort; public class BuddleTest { /*- 冒泡排序 相邻的数据两个进行比较，小的放前面，大的放后面，元素个数为了，循环的总次数为：n-1*/ public static void main(String[] args) { int[] arr = {2, 4, 5, 3, 1}; /*循环的次数*/ for (int i = 0; i < arr.length - 1; i++) { /*冒泡排序的展示,其中的arr.length-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; } } } printArr(arr); } private static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 选择排序
核心思想：从0索引开始拿着元素进行比较，小的元素放前面，大的元素放后面
package src.AlgorithmTest.Sort; public class Select_Sort { /*选择排序核心思想：从0索引开始拿着元素和他后面的元素进行比较，小的元素放前面，大的元素放后面*/ public static void main(String[] args) { int[] arr = {2, 4, 5, 3, 1}; /*其中的i表示从0号位置开始拿数据进行比较，外循环表示循环的次数*/ for (int i = 0; i < arr.length - 1; i++) { /*j=i+1表示的是从0号为和后面的1位置开始比较内循环表示交换数据*/ 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] + " "); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 插入排序
将元素分为俩大类，一边是有序的（0~n索引），一边是无序的（n+1索引），将无序的数据遍历后得到的数据插入到有序序列的中适当的位置
package src.AlgorithmTest.Sort; public class Insert_Sort { /*插入排序核心思想：将元素分为俩大类，一边是有序的（0~n索引），一边是无序的（n+1索引），将无序的数据遍历后得到的数据插入到有序序列的中适当的位置*/ public static void main(String[] args) { int[] arr = {1, 3, 10, 9, 6, 7, 5, 4, 8, 2}; int startIndex = -1; /*找到无序的起始索引*/ for (int i = 0; i < arr.length - 1; 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--;/*注意这里的j--是和前面有序的数列的比较索引*/ } } printArr(arr); } private static void printArr(int[] arr) { for (int j : arr) { System.out.println(j); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
-
快速排序
-
快速排序的核心思想：把0号索引位置的数据拿做基准数，从0号位置开始的索引为start，最后的索引为end，从start向end开始排序的数据是比基准数大的数据，从end向start排序的是比基准数小的数据。找到大的数据和小的数据，开始交换位置。当索引位置重复了，那这个位置就是基准数位置。
-
递归算法：
-
核心思想：递归是指在方法中调用方法本身。
-
递归的注意事项：必须要有递归出口，来防止堆内存占满的情况；规则：如何将大问题化成小问题
-
作用：把复杂的问题转化成一个较小的问题，只需要少量的程序即可解决问题
-
Tips:方法内部调用方法的时候，其中的参数要靠近递归出口
-
-
-
-
字符串匹配算法
- 基本查找
- KMP算法
Arrays：
方法名 说明 toString(数组) 数组拼接字符串 binarySerach(数组，元素) 二分法查找元素 int[] copyOf(原数组，新数组长度) 拷贝数组 int[]copyOfRange(原数组，起始索引，结束索引) 拷贝数组(指定范围) void fill(数组，元素) 填充数组 void sort(数组) 按默认方法将数组排序 void sort(数组，排序规则) 按照指定规则排序 package src.AlgorithmTest.Arrays; import java.util.Arrays; import java.util.Comparator; public class StaticTest { public static void main(String[] args) { int[] arr={1,2,3,4,5,8,6,7,9,10}; Integer[] arrt={1,2,3,4,5,8,6,7,9,10,11}; System.out.println(Arrays.toString(arr));/*将数组转化为字符串*/ System.out.println("-------------------------"); System.out.println(Arrays.binarySearch(arr, 9));/*二分法查找元素*/ System.out.println("-------------------------"); int[] ints = Arrays.copyOf(arr, 5); System.out.println(Arrays.toString(ints));/*拷贝指定长度的新数组*/ System.out.println("-------------------------"); int[] ints1 = Arrays.copyOfRange(arr, 4, 9); System.out.println(Arrays.toString(ints1));/*拷贝数组指定索引，到新数组,拷贝规则是包头不包尾，包左不包右*/ System.out.println("-------------------------"); // Arrays.fill(arr,1);/*数组里面填充数据*/ System.out.println(Arrays.toString(arr)); System.out.println("-------------------------"); Arrays.sort(arr);/*将数组按照默认方式进行排序*/ System.out.println(Arrays.toString(arr)); System.out.println("-------------------------"); /*在我们进行降序排列的操作下，首先需要的是将基本数据类型的数组，转为对应的包装类 * 其二是，由于第二个这个排序的规则是接口，且我们只用一次，没有必要写一个类，直接使用匿名内部类的方法直接实现*/ Arrays.sort(arrt, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) {/*其中的o1表示无序列表的无序元素，o2表示有序列表中的有序元素， 如果他们的差是正数，就将无序元素，插入到二分查找元素的后面，反之则插入到前面*/ return o2-o1;/*o1-o2是正序排列*/ } }); System.out.println(Arrays.toString(arrt)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
// /*在我们进行降序排列的操作下，首先需要的是将基本数据类型的数组，转为对应的包装类 * 其二是，由于第二个这个排序的规则是接口，且我们只用一次，没有必要写一个类，直接使用匿名内部类的方法直接实现*/ Arrays.sort(arrt, (o1, o2) -> {/*其中的o1表示无序列表的无序元素，o2表示有序列表中的有序元素， 如果他们的差是正数，就将无序元素，插入到二分查找元素的后面，反之则插入到前面*/ return o2-o1;/*o1-o2是正序排列*/ }); System.out.println(Arrays.toString(arrt)); 这个里面是用了lambda来更简单的实现了匿名内部类- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
Lambda：
注意事项
- 简化函数式接口匿名内部类的书写的
- lambda只能简化函数式编程接口里面的匿名内部类的写法
- 函数式接口：有且只有一个抽象方法的接口，或者加上@FunctionalInterface;没有报错误就是可以简化的
省略规则:
- 省略核心
- 可推导，可省略
- 参数类型可以省略
- 只有一个参数的时候，参数类型可以省略不写，同时（）也可以省略不写
- 如果lambda表达式的方法体只有一行，大括号，分号 return 也可以省略不写
综合练习：
- arrays练习
package src.AlgorithmTest.Arrays; import java.util.Arrays; import java.util.Comparator; public class gilrTest { /*定义女生对象，属性有姓名，年龄，身高;排序规则为年龄大小排，年龄一样，按照身高排，身高一样，按照姓名字母排*/ public static void main(String[] args) { gilr g = new gilr(20, 160, "a"); gilr g1 = new gilr(20, 165, "b"); gilr g2 = new gilr(20, 170, "c"); gilr g3 = new gilr(21, 165, "d"); gilr g4 = new gilr(22, 160, "w"); gilr[] arr = {g, g1, g2, g3, g4}; /*按照比较规则进行比较*/ Arrays.sort(arr, new Comparator<gilr>() { @Override public int compare(gilr o1, gilr o2) { int temp = o1.getAge() - o2.getAge(); temp = temp == 0 ? o1.getHigh() - o2.getHigh() : temp;/*三元运算符，if temp=0，则比较身高，如果身高=0， temp就是0，比较名字*/ temp = temp == 0 ? o1.getName().compareTo(o2.getName()) : temp; if (temp > 0) { return 1; } else if (temp < 0) { return -1; } else { return 0; } } }); System.out.println(Arrays.toString(arr)); } } class gilr { int age; int high; String name; public gilr() { } public gilr(Integer age, Integer high, String name) { this.age = age; this.high = high; this.name = name; } /** * 获取 * * @return age */ public int getAge() { return age; } /** * 设置 * * @param age */ public void setAge(int age) { this.age = age; } /** * 获取 * * @return high */ public int getHigh() { return high; } /** * 设置 * * @param high */ public void setHigh(int high) { this.high = high; } /** * 获取 * * @return name */ public String getName() { return name; } /** * 设置 * * @param name */ public void setName(String name) { this.name = name; } public String toString() { return "gilr{age = " + age + ", high = " + high + ", name = " + name + "}"; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
总结：
-
在选择排序和冒泡排序中，他们的区别在与，选择是拿着0索引的位置，和后面每一个元素进行比较，先找出来的是最小的值，而冒泡排序是相邻的俩元素进行比较，导致最先找出来的是最大值，并且他的下次比较个数减少;
-
快排中的sart<=end 这个问题是在于处理相同的元素，不会让start>end导致数据交换异常，可以确保相等元素的相对顺序在排序后不会改变。
-
相关阅读:
数据仓库介绍及应用场景
动手强化学习（六）：DQN 算法
C Primer Plus(6) 中文版 第1章 初识C语言 1.8 编程机制 1.11 本章小结
17种简单有效更快地增加电子邮件列表的方法
小程序开发时：getLocation:fail require permission desc
金仓数据库KingbaseES客户端编程开发框架-Django（2. 概述）
【测控电路】自举式高输入阻抗放大电路
【C++】静态库动态库
代码随想录算法训练营第五十七天 | 动态规划 part 15 | 392.判断子序列、115.不同的子序列
计算机毕业设计Java家教到家平台(源码+系统+mysql数据库+lw文档)
- 原文地址：https://blog.csdn.net/weixin_49513202/article/details/132723302
