常见算法的学习笔记

常见算法（用Java语言描述）的学习笔记

一、查找算法

01 线性查找

1、介绍

核心思想是按照顺序依次对数据结构里的每个元素进行检查，直至找到目标元素。数据不需要有任何顺序。

2、代码表示

public static boolean BasicSearch(int[] arr, int number) {//利用基本查找来在数组中进行查找for (int i = 0; i < arr.length; i++) {if (arr[i] == number) {return true;}}return false;}

3、适用场景

顺序查找简单易懂，适用于数据量较小或者数据无序的情况。

不过，当数据量很大时，由于其时间复杂度较高，查找效率会比较低。

4、时间复杂度

顺序查找需要遍历整个数组，因此在最坏的情况下，时间复杂度是$O(n)$,n 是数组的长度。

02 二分查找/折半查找

1、二分查找优势

相比基本查找效率高，每次可以去掉一半的查找范围。

2、前提条件

查找的数据必须是有序的排列。

3、查找过程

• min和max表示当前要查找的范围
• mid是在min和max中间的
• 如果要查找的元素在mid的左边，缩小范围时，min不变，max=mid-1
• 如果要查找的元素在mid的右边，缩小范围时，max不变，mix=mid+1

[!IMPORTANT]

要查找的数据是用索引来和min、mid、max比较的。

4、代码表示

	//定义静态方法binarySearch，接收两个参数：//int[] arr：表示一个有序的整数数组。//int number：代表要查找的目标元素。//此方法的返回值类型为int，如果找到元素，返回其在数组中的索引，否则返回-1public static int binarySearch(int[] arr, int number) {//1、定义两个变量记录要查找的范围//min表示数组的起始索引；max代表数组的最后一个元素的索引int min = 0;int max = arr.length - 1;//2、利用无限循环while（true）持续的查找目标元素//在每次循环开始时，检查min是否大于max，若满足此条件，//意味着查找范围为空，目标元素不在数组中，此时返回 -1。while(true){if (min > max) {return -1;}//3、计算当前查找范围的中间位置mid，通过(min + max) / 2得到。int mid = (min + max) / 2;//4、拿mid指向的元素和要查找的元素进行比较//4.1 number在mid的左边//4.2 number在mid的右边//4.3 number和mid指向的元素一样if (arr[mid] > number) {//number在mid的左边,min不变，max = mid - 1max = mid -1;}else if (arr[mid] < number) {//number在mid的右边,min不变，max = mid + 1min = mid + 1;}else {//找到啦！return mid;}}}

5、时间复杂度

• 二分查找算法的时间复杂度为${\log }_{2}n$，这里的n是数组的长度。
• 示例说明：假设数组长度 n=16，每次迭代后搜索范围的变化为：

迭代次数	搜索范围长度
0	16
1	8
2	4
3	2
4	1

可以看到，经过$lo{g}_{2}16=4$次迭代后，搜索范围缩小到了 1。

综上，二分查找算法的时间复杂度为$O(\log n)$。随着数组长度的增加，算法的执行时间增长速度相对较慢，具有较高的效率。

03 插值查找

1、基本思想

假设查找表中的数据是按升序排列的，对于给定的关键字mid，插值查找通过公式

$$mid=min+\frac{key-arr[min]}{arr[max]-arr[min]}\ast (max-min)$$

来计算中间位置mid，其中arr[min]和arr[max]分别是查找区间的最小值和最大值。该公式是基于数据在查找区间内均匀分布的假设，通过估算mid在区间*[min,max]中的相对位置来确定mid*，而不是像二分查找那样简单地取中间位置。

后面的max和min是对应的索引。

2、代码表示

public static int interpolationSearch(int[] arr, int key) {int low = 0;int high = arr.length - 1;while (low <= high && key >= arr[low] && key <= arr[high]) {if (low == high) {if (arr[low] == key) {return low;}return -1;}int mid = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);if (arr[mid] == key) {return mid;} else if (arr[mid] > key) {high = mid - 1;} else {low = mid + 1;}}return -1;}

[!CAUTION]

插值查找需要数据 分布均匀。

3、时间复杂度

在数据均匀分布的情况下，插值查找的时间复杂度为 $O(loglogn)$，优于二分查找的 $O(\log n)$。但如果数据分布不均匀，其性能可能会退化为 $O(n)$。

04 分块查找

1、分块原则

• 前一块中的最大数据，小于后一块中的所有数据（块内无序，块间有序）。
• 块数数量一般等于数字的个数开根号。例：16个数字一般分为4块左右。

2、核心思路

先确定要查找的元素在哪一块，然后在块内挨个查找。

3、代码表示

public class A03_BlockSearchDemo {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};//1、分块//2、创建3个块的对象Block b1 = new Block(21,0,5);Block b2 = new Block(45,6,11);Block b3 = new Block(73,12,17);//3、定义数组用来管理三个块的对象（索引表）Block[] blockArr = {b1,b2,b3};//4、定义变量用来记录要查找的元素int number = 5;//5、调用方法，传递索引表、数组、要查找的元素int index = getIndex(blockArr,arr,number);//6、打印输出System.out.println(index);}//定义方法。private static int getIndex(Block[] blockArr, int[] arr, int number) {//1、确定number在哪个块int indenBlock = findIndexBlock(blockArr,number);if (indenBlock == -1) {  //表示number不在数组中return -1;}//获取这一块的起始索引和结束索引int startIndex = blockArr[indenBlock].getStartIndex();int endIndex = blockArr[indenBlock].getEndIndex();//3、遍历for (int i = startIndex; i <= endIndex; i++) {if (arr[i] == number) {return i;}}return -1;}//定义方法确定number在哪个块中private static int findIndexBlock(Block[] blockArr, int number) { //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号块//从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 + "}";}
}

4、时间复杂度

分块查找的时间复杂度与块数、每块中的元素个数以及查找方式有关。假设将长度为 n 的数组分为 m 块，每块有 s 个元素（n=m×s）。

在索引表中查找块的时间复杂度：如果索引表是有序的，使用二分查找等高效算法，时间复杂度为$O(\log m)$；如果索引表是无序的，采用顺序查找，时间复杂度为$O(m)$。

在块内查找元素的时间复杂度：通常采用顺序查找，时间复杂度为$O(s)$。

因此，分块查找的平均时间复杂度为**索引表查找时间复杂度与块内查找时间复杂度之和。**当索引表采用顺序查找时，分块查找的平均时间复杂度为$O(m+s)$；当索引表采用二分查找时，平均时间复杂度约为$O(\log m+s)$。

理想情况：由于m=n/s，当s取n时，m也为n，此时分块查找的平均时间复杂度为O(n)。

5、适用场景

分块查找适用于数据量较大且需要快速查找的场景，尤其是当数据无法一次性全部加载到内存中时，可以将数据分块存储在磁盘上，通过索引表快速定位到目标元素所在的块，然后再在块中进行查找。

---

二、排序算法

01 冒泡排序！！！

1、核心思想

• 相邻的数据两两比较，大的放右边，小的放左边。（从小到大）
• 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推。
• 如果数组中有n个数据，总共执行n-1次代码。

2、代码表示

public class A01_BubbleDemo1 {public static void main(String[] args) {//1、定义数组int[] arr = {2, 4, 5, 3, 1};//2、利用冒泡for (int i = 0; i < arr.length - 1; i++) {  //外循环，表示我要执行多少轮，n个数据，执行n-1轮for (int j = 0; j < arr.length - 1 - i; j++) {//内循环，每一轮中我如何比较数据并找到当前的最大值//-1：为了防止索引越界//-i：提高效率，每一轮执行的次数应该比上一轮少一次。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] + " ");}}
}

02 选择排序！！！

1、核心思想

• 从0索引开始，跟后面的元素一一比较。
• 小的放前面，大的放后面。
• 第一轮循环结束后，最小的数据已经确定。
• 第二轮循环从1索引开始以此类推。
• 第三轮循环从2索引开始…后面类推

2、代码展示

public class A02_SelectionDemo {public static void main(String[] args) {//1、定义数组int[] arr = {2, 4, 5, 3, 1};//2、利用选择排序进行//外循环,i表示拿着哪个索引上的数据跟后面的数据进行比较并交换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;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

03 插入排序

1、核心思想

将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到最后一个当成是无序的。

遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

N的范围：0-最大索引。

2、代码展示

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、找到无序的那一组数组是从哪个索引开始的。2int 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++) {//3、记录当前要插入数据的索引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();}}

04 递归算法

1、核心思想

递归指的是：方法中调用方法本身的现象。

2、代码展示

public class A04_RecursionDemo1 {public static void main(String[] args) {method();}public static void method() {method();	//方法中自己调用自己}
}

[!CAUTION]

递归一点要有出口，否则就会出现内存溢出的现象。

3、书写递归的核心

• 找出口：什么时候不再调用方法。
• 找规则：如何把大问题变为规模较小的问题。
• 心得：方法内部再次调用方法的时候，参数必须要更加的靠近出口。

4、练习

1、需求：利用递归求1-100之间的和。

代码展示：

public class A04_RecursionDemo2 {public static void main(String[] args) {/** 需求：利用递归求1-100之间的和。* 100 + 99 + 98 + 97 + ... + 3 + 2 + 1** 1-100之间的和 = 100 +（1-99之间的和）* 1-99之间的和 = 99 + （1-98之间的和）* ...* 1-2之间的和 = 2 + （1-1之间的和）* 1-1之间的和 = 1 （递归的出口)*/System.out.println(getSum(100));}public static int getSum(int number) {if (number == 1) {    //number为1return 1;}return number + getSum(number - 1); //number不为1}
}

2、需求：利用递归求5的阶乘，并把结果在控制台输出。

代码展示：

public class A04_RecursionDemo3 {public static void main(String[] args) {//需求：利用递归求5的阶乘//5!=5*4*3*2*1System.out.println(getFactorialRecursion(5));}public static int getFactorialRecursion(int number) {if (number == 1) {return 1;}return number * getFactorialRecursion(number - 1);}}

05 快速排序

1、核心思想

第一轮：以0索引的数字为基准数，确定基准数在数组中的正确位置。

​ 比基准数小的全部在左边，比基准数大的全部在右边。

​ 后面的以此类推。

2、代码展示

public class A05_QuickSortDemo {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] + " ");}}/**   参数1：我们要排序的数组*   参数2：要排序的数组的起始索引*   参数3：要排序的数组的结束索引 */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, start + 1, j);}}

三、综合练习

1、按照要求进行排序

需求：定义数组并存储一些女朋友对象，利用Arrays中的sort（）方法进行排序

要求1：属性有姓名、年龄、身高。

要求2：按照年龄的大小进行排序，年龄一样，按照身高排序，身高一样按照姓名的字母进行排序。（姓名中不要有中文或特殊字符）

代码展示：

import java.util.Arrays;
import java.util.Comparator;public class Test1 {public static void main(String[] args) {//1、创建三个女朋友对象GirlFriend gf1 = new GirlFriend("xiaoshishi", 18, 1.67);GirlFriend gf2 = new GirlFriend("xiaodandan", 19, 1.72);GirlFriend gf3 = new GirlFriend("xiaohuihui", 19, 1.78);GirlFriend gf4 = new GirlFriend("abc", 19, 1.78);//2、定义数组存储GirlFriend[] arr = {gf1, gf2, gf3, gf4};//3、利用Array中的sort方法进行排序//匿名内部类/*Arrays.sort(arr, new Comparator<GirlFriend>() {@Overridepublic int compare(GirlFriend o1, GirlFriend o2) {//比较规则double temp = o1.getAge() - o2.getAge();temp = temp == 0 ? o1.getHeight() - o2.getHeight() : temp;temp = temp == 0 ? o1.getName().compareTo(o2.getName()) : temp;if (temp > 0) {return 1;} else if (temp < 0) {return -1;} else {return 0;}}});*///lanbda表达式//() -> {}//():对应着抽象方法的形参//{}：方法体Arrays.sort(arr, (o1, o2) -> {//比较规则double temp = o1.getAge() - o2.getAge();temp = temp == 0 ? o1.getHeight() - o2.getHeight() : temp;temp = temp == 0 ? o1.getName().compareTo(o2.getName()) : temp;if (temp > 0) {return 1;} else if (temp < 0) {return -1;} else {return 0;}});//4、展示数组中的内容System.out.println(Arrays.toString(arr));}}