递归
- 自己调用自己，每次的变量都不一样
规范
执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
方法的局部变量是独立的，不会相互影响, 比如n变量
如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError（栈溢出）， 死龟了
当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果 返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕
递归 - 迷宫回溯问题
- 小球得到的路径，和程序员 设置的找路策略有关即：找 路的上下左右的顺序相关
- 再得到小球路径时，可以先 使用(下右上左)，再改成(上 右下左)，看看路径是不是有变化
- 测试回溯现象
package com.recursion; /** * @author Kcs 2022/8/25 */ public class MiGong { public static void main(String[] args) { //二维数组模拟迷宫 int[][] map = new int[8][7]; //1.表示墙 //上下两行置为 1 for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } //左右两侧的列置为 1 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } //挡板 map[3][1] = 1; map[3][2] = 1; System.out.println("原地图："); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } //设置起点 // setWay(map, 1, 1); setWay2(map, 1, 1); //新的地图，标识过的 System.out.println("走过的路径："); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } } /** * @param map 地图 * @param i 起始位置 * @param j * @return true ,false * 当 map[i][j]为 0：还没有走的点，1：墙，2：走过的路径，3：走不通的点，(6,5)为终点 * 策略一: 下 → 右 → 上 → 左，走不通，再回溯 * 策略二：下 → 左 → 上 → 右 * 策略三：上 → 右 → 下 → 左 * 策略很多，可以自己尝试修改，本次使用的策略为策略一，但是存在最优路径 */ public static boolean setWay(int[][] map, int i, int j) { if (map[6][5] == 2) { return true; } else { if (map[i][j] == 0) { // 假设可以走 map[i][j] = 2; //对应策略的顺序进行修改 if (setWay(map, i + 1, j)) { //向下走 return true; } else if (setWay(map, i, j + 1)) { //向右走 return true; } else if (setWay(map, i - 1, j)) { //向上走 return true; } else if (setWay(map, i, j - 1)) { //向左走 return true; } else { //走不通的起点 map[i][j] = 3; return false; } } else { return false; } } } /** * 策略三：上 → 右 → 下 → 左 * @param map * @param i * @param j * @return */ public static boolean setWay2(int[][] map, int i, int j) { if (map[6][5] == 2) { return true; } else { if (map[i][j] == 0) { // 假设可以走 map[i][j] = 2; //对应策略的顺序进行修改 if (setWay2(map, i - 1, j)) { //向上走 return true; } else if (setWay2(map, i, j + 1)) { //向右走 return true; } else if (setWay2(map, i + 1, j)) { //向下走 return true; } else if (setWay2(map, i, j - 1)) { //向左走 return true; } else { //走不通的起点 map[i][j] = 3; return false; } } else { return false; } } } }
八皇后问题（92种）
问题描述：在一个8 × 8 的国际象棋摆放 8个皇后，使其不能互相攻击
要求：任意两个皇后都不能处于同一列、同一行或者同一斜线上，问有多少种摆法
分析
第一个皇后先放第一行第一列
第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在 第二列、第三列、依次把所有列都放完，找到一个合适
继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个 不冲突的位置，算是找到了一个正确解
当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第 一个皇后，放到第一列的所有正确解，全部得到.
然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤
说明：
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法， 用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}
对应arr 下标表示第几行，即第几个皇后，arr[i] = val , val 表示第 i + 1 个皇后，放在第 i + 1行的 第val+1列
package com.recursion; /** * @author Kcs 2022/8/28 */ public class Queue8 { /** * 皇后总数 */ int max = 8; /** * 定义数组array，保留皇后放置的位置 */ int[] array = new int[max]; /** * 统计一共有多少种解法 */ static int count = 0; public static void main(String[] args) { //测试 Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("共有解法：%d", count); } /** * 放置第n个皇后 * check每一次递归时，都会进入到for循环 */ private void check(int n) { //8皇后已经放完 if (n == max) { print(); return; } //依次放入皇后，并判断是否冲突 for (int i = 0; i < max; i++) { //本皇后n，放置行的首列 array[n] = i; //皇后放置第i列，判断是否与前面的皇后的列是否冲突 if (judge(n)) { //不冲突，接着下一个皇后， 递归 check(n + 1); } //冲突，回去到上一行 array[n] = i，将第n个皇后，放置在本行的后移一个位置 } } /** * 查看放置的皇后是否与前面放置的皇后是否产生冲突 * n: 第n个皇后 */ private boolean judge(int n) { for (int i = 0; i < n; i++) { //判断皇后是否在同一列上，或者统一斜线上(Math.abs(n - i) == Math.abs(array[n] - array[i] n:表示列上， // 比如 n = 1 时，array[n] = array[1] = 1 ,arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列 // 同一行就不要判断， n不断在增加 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { return false; } } return true; } /** * 输出皇后的位置 */ public void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
排序算法
- 排序是一种数据结构，不是算法，指定的顺序进行排序的过程。
内部排序
- 将需要处理的所有数据都加载到内存处理器中去进行排序
外部排序
- 数据量过大，无法全部加载到内 存中，需要借助外部存储进行 排序
常见排序算法
算法时间复杂度
度量一个程序(算法)执行时间的两种方法
- 事后统计的方法
存在两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；
二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。 - 事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优
时间频率
一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法 中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频 度或时间频度。记为T(n)。
举例
时间复杂
一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函 数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它 们的T(n) 不同，但时间复杂度相同，都为O(n²)。
计算时间复杂度
用常数1代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1
修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²
去除最高阶项的系数 T(n) = n²=> T(n) = n² => O(n²)
————————————————
平方阶：2个 for 循环
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n 2 )＜ Ο(n3 )＜ Ο(nk ) ＜Ο(2n ) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的 执行效率越低
常数阶
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
int i = 2; int j = 3; ++i; j++; int m = i+j;
- 它消耗的时候并不随着某个变量的增长而增长，那么无论这类代 码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度
- 对数阶O(log2n)
int i = 1; while(i<n){ i = i*2; }
在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环 x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为： O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n)
线性阶O(n)
for(i=1,i<=n,i++){ j =i; j++; }
- 这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变 化的，因此这类代码都可以用O(n)来表示它的时间复杂度
- 线性对数阶O(nlogN)
for(i=1,i<=n,i++){ i = 1; while(i<n){ i = i*2; } }
- 将时间复杂度为O(logn)的代码循环N遍的 话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
- 平方阶O(n2)
for(i=1,i<=n,i++){ for(j=1,j<=n,j++){ j = i; j++; } }
平方阶O(n2)
for(i=1,i<=n,i++){ for(j=1,j<=n,j++){ j = i; j++; } }
- 如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂 度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n * n)， 即 O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m * n)
- 立方阶O(n³)、K次方阶O(nk)
平均时间复杂度和最坏时间复 杂度
平均时间复杂度是指所有可能的输 入实例均以等概率出现的情况下， 该算法的运行时间。
最坏情况下的时间复杂度称最坏时 间复杂度。一般讨论的时间复杂度 均是最坏情况下的时间复杂度。 原因是：最坏情况 下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证 了算法的运行时间不会比最坏情况更长。
空间复杂度
一个算法的空间复杂度(Space Complexity)定义为该 算法所耗费的存储空间，它也是问题规模 n 的函数
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大 小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它 随着n的增大而增大，当n较大时，将占用较多的存储单元
一、冒泡排序 Bubble Sorting
基本思想
通过对待 排序序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，使值较大 的元素逐渐从前移向后部，就象水底下的气泡一样逐渐 向上冒。
优化
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下 来没有进行过交换，就说明序列有序，因此要在排序过程中设置 一个标志flag判断元素是否进行过交换。从而减少不必要的比较
分析
冒泡数组：3 ，9， -1， 10， -5
- 使用冒泡排序法将其排成一个从小到大的有序数列
- 相邻元素逆序就交换
结论
- 循环次数：数组长度 - 1 次
- 每一趟排序的次数不断减少
- 某一趟排序中，没有进行一次交换，则说明是有序排序（优化）
import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * @author Kcs 2022/9/2 */ public class BubbleSorting { public static void main(String[] args) { //排序数组 int[] array = {3, 9, -1, 10, 20}; System.out.println("原始冒泡数组：" + Arrays.toString(array)); bubbleSort(array); System.out.println("排序结果：" + Arrays.toString(array)); // 测试冒泡排序的时间复杂度, 用一个较大的数据进行测试 int[] test = new int[8000]; for (int i = 0; i < 8000; i++) { test[i] = (int) (Math.random() * 80000); } Date beforeDate = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String formatBefore = simpleDateFormat.format(beforeDate); System.out.println("排序前时间" + formatBefore); bubbleSort(test); Date afterDate = new Date(); String afterDateformat = simpleDateFormat.format(afterDate); System.out.println("排序前时间" + afterDateformat); } //封装冒泡方法 public static void bubbleSort(int[] arr) { //表示是否进行交换 boolean flag = false; int temp; //第一趟排序 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { //前面的比后面的数大，就进行交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } // System.out.println("第" + (i + 1) + "次排序结果：" + Arrays.toString(arr)); if (!flag) { //没有发生交换 break; } else { //重置flag ,进行下次交换 flag = false; } } } }
二、选择排序 （Select Sorting）
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一 元素，再依规定交换位置后达到排序的目的。
思路
第 一次从arr[0] ~ arr[n-1]中选取最小值，与arr[0]交换，第二次从 arr[1] ~ arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~ arr[n-1]中 选取最小值，与arr[2]交换，…，第i次从arr[i-1] ~ arr[n-1]中选取最小值， 与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2] 交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
分析
原始数组 ： 101，34，119，1，要求：由小到大
每次执行的得到的结果：
- 1，34，119，101
- 1，34，119，101
- 1，34，101，119
结论
- 需要执行数组大小 -1轮排序
- 每一轮都是一个循环，循环的规则（代码）
- 先假定当前数为最小数，
- 然后和后面的数进行比较，若当前数更小，重新得到最小数，并得到下标
- 遍历到数组的最后时，就得到本轮的最小数和下标
- 交换
import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * @author Kcs 2022/9/2 */ public class SelectSorting { public static void main(String[] args) { int[] arr = {101, 34, 119, 1}; System.out.println("排序前：" + Arrays.toString(arr)); selectSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); //测试时间 int[] test = new int[8000]; for (int i = 0; i < 8000; i++) { test[i] = (int) (Math.random() * 80000); } Date beforeDate = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String formatBefore = simpleDateFormat.format(beforeDate); System.out.println("排序前时间" + formatBefore); selectSort(test); Date afterDate = new Date(); String afterDateformat = simpleDateFormat.format(afterDate); System.out.println("排序前时间" + afterDateformat); } /** * 选择排序 * 时间复杂度 O(n^2) * @param arr */ public static void selectSort(int[] arr) { //原始数组 ： 101，34，119，1，要求：由小到大 for (int i = 0; i < arr.length - 1; i++) { //起始索引 int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { //由大到小：> 由小到大：< ；当前值进行比较，找出索引 if (min > arr[j]) { min = arr[j]; // 得到最小值索引 minIndex = j; } } //最小值放在arr[0] if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } // System.out.println("第" + (i + 1) + "轮排序结果：" + Arrays.toString(arr)); } } }
三、插入排序
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的 适当位置，以达到排序的目的
基本思想
把n个待排序的元素看成为 一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中 包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它 的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的 适当位置，使之成为新的有序表。
分析
原始数组：101, 34, 119, 1
import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * @author Kcs 2022/9/3 */ public class InsertSort { public static void main(String[] args) { int[] arr = {101, 34, 119, 1, 45, 78}; System.out.println("排序前结果：" + Arrays.toString(arr)); insertSort(arr); System.out.println("排序后结果：" + Arrays.toString(arr)); // 测试冒泡排序的时间复杂度, 用一个较大的数据进行测试 int[] test = new int[8000]; for (int i = 0; i < 8000; i++) { test[i] = (int) (Math.random() * 80000); } Date beforeDate = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String formatBefore = simpleDateFormat.format(beforeDate); System.out.println("排序前时间" + formatBefore); insertSort(test); Date afterDate = new Date(); String afterDateformat = simpleDateFormat.format(afterDate); System.out.println("排序后时间" + afterDateformat); } /** * 插入排序 */ public static void insertSort(int[] arr) { int insertValue = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { //定义待插入的数 insertValue = arr[i]; //arr[1] 前面这个数的索引 insertIndex = i - 1; //insertValue 找到插入的位置 由小到大 < ；由大到小：< // insertIndex >= 0 放置越界 // insertValue < arr[insertIndex] : 带插入的数字 // arr[insertIndex] 后移 while (insertIndex >= 0 && insertValue < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //找到插入的位置 if (insertIndex + 1 == i) { arr[insertIndex + 1] = insertValue; } // System.out.println("第" + i + "轮排序结果：" + Arrays.toString(arr)); } } }
四、希尔排序
基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰 被分成一组，算法便终止
分析
初始数组 {8,9,1,7,2,3,5,4,6,0}
- 希尔排序时， 对有序序列在插入时采用交换法, 并测试排序速度.
- 希尔排序时， 对有序序列在插入时采用移动法, 并测试排序速度
交换法：
import java.util.Arrays; /** * @author Kcs 2022/9/3 */ public class ShellSort { public static void main(String[] args) { int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; shellSort(arr); } /** * 希尔排序 */ public static void shellSort(int[] arr) { int temp = 0; int count = 0; // 循环处理 希尔排序 for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { //遍历各组中所有的元素 for (int j = i - gap; j >= 0; j -= gap) { //当前元素大于加上步长后的元素，则进行交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } System.out.println("第" + (++count) + "轮希尔排序结果：" + Arrays.toString(arr)); } } }
移步法
import java.util.Arrays; /** * @author Kcs 2022/9/3 */ public class ShellSort { public static void main(String[] args) { int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; shellSort(arr); System.out.println("交换法：" + Arrays.toString(arr)); shellSort2(arr); System.out.println("移位法：" + Arrays.toString(arr)); } /** * 移位法 * @param arr */ public static void shellSort2(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { //从gap个元素，逐个对其所在组进行之直接插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { // 元素进行移动 arr[j] = arr[j - gap]; j -= gap; } //找到插入的位置 arr[j] = temp; } } } } }
五、快速排序
基本思想
通过一趟排序 将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分 的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个 排序过程可以递归进行，以此达到整个数据变成有序序列
左右递归有顺序
import java.util.Arrays; /** * @author Kcs 2022/9/3 */ public class QuickSort { public static void main(String[] args) { int[] arr = {-9, 78, 0, 23, -567, 70}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } /** * 快速排序 * @param arr */ public static void quickSort(int[] arr, int left, int right) { //左下标 int l = left; //右下标 int r = right; //中轴值 int pivot = arr[(left + right) / 2]; //作为交换 int temp = 0; // 比 pivot 小的值 放到左边，大的值放到右边 while (l < r) { //在pivot的左边找，比pivot大于等于的值 while (arr[l] < pivot) { l += 1; } //在pivot的右边找，比pivot小于等于的值 while (arr[r] > pivot) { r -= 1; } //左边是小于pivot的值， 右边大于等于pivot的值 if (l == r) { break; } //进行交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //交换后，发现arr[l] == pivot 值 ,则前移 if (arr[l] == pivot) { r -= 1; } //交换后，发现arr[r] == pivot 值 ,则后移 if (arr[r] == pivot) { l += 1; } } // l==r 要 l++ r-- if (l == r) { l += 1; r -= 1; } //左递归 if (left < r) { quickSort(arr, left, r); } //右递归 if (right > l) { quickSort(arr, l, right); } } }
六、归并排序
采用分治策略。分治法将问题分 (divide) 成一些小的问 题然后递归求解，而治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一 起，即分而治之。
以上结构很像一棵完全二叉树，采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归 拆分子序列的过程
分析
上图合并了七次，下图为最后一次的合并详解：
import java.util.Arrays; /** * @author Kcs 2022/9/3 */ public class MergeSort { public static void main(String[] args) { int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; System.out.println("要排序的数组:" + Arrays.toString(arr)); //归并需要一个额外的空间 int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); System.out.println("归并排序结果：" + Arrays.toString(arr)); } /** * 分解 + 合并 过程 */ public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; // 向左递归进行分解 mergeSort(arr, left, mid, temp); //向右递归分解 mergeSort(arr, mid + 1, right, temp); //合并 merge(arr, left, mid, right, temp); } } /** * 合并起来 * @param arr 原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { // 初始化i 左边有序序列的初始索引 int i = left; // 初始化 j ,右边有序序列的初始索引 int j = mid + 1; // 指向temp数组的当前索引 int t = 0; // 1. 左右两边的数据，按照规则进行填充到 temp 数组，直到左右两边的有序序列，有一边完成为止 while (i <= mid && j <= right) { //左边的有序序列的当前元素，小于等于右边有序序列的当前元素，即将左边的当前元素，拷贝到 temp 中 if (arr[i] < arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } else { // 右边的比左边的元素大，填充到temp数据 temp[t] = arr[j]; t += 1; j += 1; } } // 2. 把剩余数据的一边的数据依次全部填充到 temp 中 while (i <= mid) { //左边的 有序序列还有剩余元素，全部填充到 temp 中去 temp[t] = arr[i]; t += 1; i += 1; } while (j <= right) { //左边的 有序序列还有剩余元素，全部填充到 temp 中去 temp[t] = arr[j]; t += 1; j += 1; } // 3. 将temp 数据的元素拷贝到 arr,并不是每次拷贝所有 t = 0; int tempLeft = left; //最后一次 tempLeft = 0 ,right = 7 System.out.println("tempLeft=" + tempLeft + " " + "right=" + right); while (tempLeft <= right) { arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } }
七、基数排序（桶排序）
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort
它是通过键值的各个位的值， 将要排序的元素分配至某些 “桶” 中，达到排序的作用。
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法（相同的数字会有先后顺序）
基本思想
- 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完 成以后, 数列就变成一个有序序列
分析
将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。有多少位数就要进行多少次桶排序
说明： 事先准备10个数组(10个桶)， 0-9 分别对应位数的 0-9
第1轮排序
将各个数，按照个位大小放入到对应的各个数组中 （看每个元素的个位数，把这个多位数，放置在个位数对应的桶中（一个桶一个数组））
然后从 0-9 个数组 / 桶，依次按照加入元素的先后顺序取出
- 得到结果 ：542 、53、3、14、214、748
- 第二轮排序 （后一轮是根据上一轮得到的结果进行排序）
- 将各个数，按照 十位 大小放入到对应的各个 数组 / 桶 中
- 然后从 0-9 个数组 / 桶，依次按照加入元素的先后顺序取出
- 得到结果 ：542 、53、3、14、214、748
- 第二轮排序 （后一轮是根据上一轮得到的结果进行排序）
- 将各个数，按照 十位 大小放入到对应的各个 数组 / 桶 中
- 然后从 0-9 个数组 / 桶，依次按照加入元素的先后顺序取出
import java.util.Arrays; /** * @author Kcs 2022/9/3 */ public class RadixSort { public static void main(String[] args) { int[] arr = {53, 3, 542, 748, 14, 214}; radixSort(arr); } /** * 基数排序 时间换空间算法 * @param arr */ public static void radixSort(int[] arr) { //第一轮(每个元素的个位数进行处理) //二维数组表示十个桶，每个桶就是一个一维数组 //防止数据溢出，将一维数组大小为arr.length int[][] bucket = new int[10][arr.length]; //记录桶放入的有效数据中，实际存放的数据。存放bucket[0~10]的对应的数据 int[] bucketElementCounts = new int[10]; //得到数组中最大的数的位数 int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } //得到最大的位数 int maxLength = (max + "").length(); for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { //取出各位 个 十 百 千 位 for (int j = 0; j < arr.length; j++) { //取出每个元素对应位数的值 int digitOfElment = arr[j] / n % 10; //放入对应的桶中,前一个找到对应的桶，后一个为该个位对应的多位数 bucket[digitOfElment][bucketElementCounts[digitOfElment]] = arr[j]; //下一个桶 bucketElementCounts[digitOfElment]++; } //依次桶的顺序，依次取出数据，放入原来的数组 int index = 0; //遍历每一个桶，就将桶的数据，放入到原数组中， for (int k = 0; k < bucketElementCounts.length; k++) { //桶中有数据才放入原数组 if (bucketElementCounts[k] != 0) { //循环改桶的数据，放入原数组 for (int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入 arr arr[index++] = bucket[k][l]; } } //对桶进行清零 bucketElementCounts[k] = 0; } System.out.println("第" + (i + 1) + "次排序结果:" + Arrays.toString(arr)); } //以下为推导过程 /*//第二轮：取出十位 for (int j = 0; j < arr.length; j++) { //得到十位的数 每一轮只要修改这个取模的 个 十 百 千 位 int digitOfElment = arr[j] / 10 % 10; //放入对应的桶中,前一个找到对应的桶，后一个为该个位对应的多位数 bucket[digitOfElment][bucketElementCounts[digitOfElment]] = arr[j]; //下一个桶 bucketElementCounts[digitOfElment]++; } //依次桶的顺序，依次取出数据，放入原来的数组 index = 0; //遍历每一个桶，就将桶的数据，放入到原数组中， for (int k = 0; k < bucketElementCounts.length; k++) { //桶中有数据才放入原数组 if (bucketElementCounts[k] != 0) { //循环改桶的数据，放入原数组 for (int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入 arr arr[index++] = bucket[k][l]; } } //对桶进行清零 bucketElementCounts[k] = 0; } System.out.println("第二轮结果:" + Arrays.toString(arr)); //第三轮：取出白位 for (int j = 0; j < arr.length; j++) { //得到十位的数 每一轮只要修改这个取模的 个 十 百 千 位 int digitOfElment = arr[j] / 100; //放入对应的桶中,前一个找到对应的桶，后一个为该个位对应的多位数 bucket[digitOfElment][bucketElementCounts[digitOfElment]] = arr[j]; //下一个桶 bucketElementCounts[digitOfElment]++; } //依次桶的顺序，依次取出数据，放入原来的数组 index = 0; //遍历每一个桶，就将桶的数据，放入到原数组中， for (int k = 0; k < bucketElementCounts.length; k++) { //桶中有数据才放入原数组 if (bucketElementCounts[k] != 0) { //循环改桶的数据，放入原数组 for (int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入 arr arr[index++] = bucket[k][l]; } } //对桶进行清零 bucketElementCounts[k] = 0; } System.out.println("第三轮结果:" + Arrays.toString(arr));*/ } }
排序算法对比
解释：
稳定：如果 a原本在 b前面，而a=b ， 排序之后 a仍然在 b的前面；
不稳定：如果 a原本在 b的前面，而 a=b，排序之后 a可能会出现在 b的后 面；
内排序：所有排序操作都在内存中完 成；
外排序：由于数据太大，因此把数据 放在磁盘中，而排序通过磁盘和内存 的数据传输才能进行；
时间复杂度： 一个算法执行所耗费 的时间。
空间复杂度：运行完一个程序所需内 存的大小。
n：数据规模
k：“桶”的个数
In -place：不占用额外内存
Out -place：占用额外内存
查找算法
顺序（线性查找）查找
- 从头到尾一个一个进行对比查找，找到则返回下标
/** * @author Kcs 2022/9/5 */ public class SequenceSearch { public static void main(String[] args) { //数组 int[] arr = {1 ,-25, 45, 32, 3, 0, 12, -20}; int index = seqSearch(arr, 0); if (index == -1) { System.out.println("查无次数据"); } else { System.out.println("该数字位于:" + index); } } /** * 找到一个就返回 * @param arr 匹配数组 * @param value 要查找的数 * @return index */ public static int seqSearch(int[] arr, int value) { //逐一比对 for (int i = 0; i < arr.length; i++) { if (arr[i] == value) { return i; } } return -1; } }
二分查找 / 折半查找
必须是顺序的数组，若是无序的，则需要先排序（小到大 / 大到小）
思路
（以下是排序已为由小到大）
首先确定该数组的中间下标
mid = （left + right）/ 2
然后让需要查找的数 findValue 和 arr[mid] 进行比较
findValue > mid[arr] ：说明要查找的数在 mid 的右边，应该向右查找（向右递归查找）
findValue < mid[arr] ：说明要查找的数在 mid 的左边，应该向左查找（向左递归查找）
findValue = mid[arr] ：说明已经找到，则返回
退出递归
找到目标退出递归
找不到退出递归 （left > right）
/** * @author Kcs 2022/9/5 */ public class BinarySearch { public static void main(String[] args) { //有序数组 int[] arr = {0, 11, 22, 33, 44, 45, 55, 77, 88, 88, 88, 88, 99}; // int index = binarySearch(arr, 0, arr.length - 1, 12); // System.out.println("index=" + index); List<Integer> integers = binarySearch2(arr, 0, arr.length - 1, 99); System.out.println(integers); } /** * 二分查找算法 * @param arr 查找数组 * @param left 左边索引 * @param right 右边索引 * @param findValue 查找的值 * @return index */ public static int binarySearch(int[] arr, int left, int right, int findValue) { //没有找到 if (left > right) { return -1; } //中间索引 int mid = (left + right) / 2; //中间值 int midValue = arr[mid]; //判断递归的方向 //向右 if (findValue > midValue) { return binarySearch(arr, mid + 1, right, findValue); } else if (findValue < midValue) { return binarySearch(arr, left, mid - 1, findValue); } else { //查找到所有相同的值，并返回 return mid; } } /** * 查找重复的值索引 * @param arr * @param left * @param right * @param findValue * @return */ public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findValue) { //没有找到 if (left > right) { return new ArrayList<Integer>(); } //中间索引 int mid = (left + right) / 2; //中间值 int midValue = arr[mid]; //判断递归的方向 //向右 if (findValue > midValue) { return binarySearch2(arr, mid + 1, right, findValue); } else if (findValue < midValue) { return binarySearch2(arr, left, mid - 1, findValue); } else { ArrayList<Integer> resIndexlist = new ArrayList<>(); int temp = mid - 1; //向mid左边开始继续搜索 while (true) { //退出 if (temp < 0 || arr[temp] != findValue) { break; } resIndexlist.add(temp); temp -= 1; } resIndexlist.add(mid); //向mid右边继续搜索 temp = mid + 1; while (true) { if (temp > (arr.length - 1) || arr[temp] != findValue) { break; } resIndexlist.add(temp); temp += 1; } return resIndexlist; } } }
插值查找
也是得用在有序数组上
插值查找每次从自适应mid处开始查找
将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是 findValue
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;
- 对应前面的代码公式： int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
特点
- 可以一次就能查找想要的结果
- 与二分查找相比， 想过肯定的好很多的
使用场景
- 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快
- 关键字分布不均匀的情况下，该方法不一定比折半查找要好
/** * @author Kcs 2022/9/6 */ public class InsertValueSearch { public static void main(String[] args) { //1 ~ 100 数组 int[] array = new int[100]; for (int i = 0; i < 100; i++) { array[i] = i + 1; } int index = insertValueSearch(array, 0, array.length - 1, 50); System.out.println("index = " + index); } /** * 插值查找算法 * @param array 查找的数组 * @param left 左边 索引 * @param right 右边索引 * @param findValue 查找的值 * @return index */ public static int insertValueSearch(int[] array, int left, int right, int findValue) { System.out.println("查找了！！！！"); //不符合，则退出 优化查找，防止mid越界。自适应的查找 if (left > right || findValue < array[0] || findValue > array[array.length - 1]) { return -1; } //求出mid int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]); //中间的值 int midValue = array[mid]; if (findValue > midValue) { //向右递归查找 return insertValueSearch(array, mid + 1, right, findValue); } else if (findValue < midValue) { //向左递归查找 return insertValueSearch(array, left, mid - 1, findValue); } else { //相等 return mid; } } }
斐波那契查找
斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ···} 发现斐波那契数 列的两个相邻数 的比例，无限接近黄金分割值0.618
原理
mid不 再是中间或插值得到，而是位于黄金分 割点附近，即mid=low+F(k-1)-1 （F代表斐波那契数列）
由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。 该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如 上图所示。从而中间位置为mid=low+F(k-1)-1
顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只 要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到 F[k]-1位置），都赋为n位置的值即可
分析
有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234}
import java.util.Arrays; /** * @author Kcs 2022/9/7 */ public class FibonacciSearch { //斐波那契额数列的显示个数 public static int maxSize = 20; public static void main(String[] args) { int[] arr = {1, 8, 10, 89, 1000, 1234}; System.out.println(fibSearch(arr, 8)); } /** * 20个斐波那契数列 * @return f[] */ public static int[] fib() { int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; } /** * 斐波那契薯类 * @param a 要在查找的数组 * @param key 需要查找的关键值 * @return index */ public static int fibSearch(int[] a, int key) { //左边下标 int low = 0; //右边下标 int high = a.length - 1; //斐波那契分割数值的下标 int k = 0; //mid int mid = 0; //获取斐波那契数列 int[] f = fib(); while (high > f[k] - 1) { k++; } //防止f[k] 大于 数组的长度,不足的时候使用 0 填充 int[] temp = Arrays.copyOf(a, f[k]); //不使用0 进行填充，使用 arr数组的最后一位进行填充 for (int i = high + 1; i < temp.length; i++) { temp[i] = a[high]; } //查找目标值 while (low <= high) { mid = low + f[k - 1] - 1; if (key < temp[mid]) { //查找前半部分（左边） high = mid - 1; k--; } else if (key > temp[mid]) { //向右边查找 low = mid + 1; //f[k-1] = f[k -3]+f[k -4] k -= 2; } else { //查找到 if (mid <= high) { //左边mid return mid; } else { //右边的index return high; } } } //没有找到 return -1; } }
哈希表
- 哈希表属于数据结构
散列表（Hash table，也叫哈希表）， 是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表
思路
有一个公司,当有新的员工来报道时,要求将该员工的信息加入 (id,名字，···),当输入该员工的id时,要求查找到该员工的所有信息
要求
- 不使用数据库,速度越快越好=>哈希表(散列)
- 添加时，保证按照id从低到高插入
实现思路
- 使用链表来实现哈希表, 该链表不带表头 [即: 链表的第一个结点就存放雇员信息]
- 代码实现[增删改查(显示所有员工，按id查询)]
散列函数
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：
- 计算哈希函数所需时间
- 关键字的长度
- 哈希表的大小
- 关键字的分布情况
- 记录的查找频率
散列函数的几种方法
- 直接寻址法
- 数字分析法
- 平方取中法
- 折叠法
- 随机数法
- 除留余数法
创建三个类
- 雇员类：雇员的信息
- 雇员链表类：管理雇员
- 哈希表类：存放 n个 雇员，散列函数：使 id 对应的链表
import java.util.Scanner; /** * @author Kcs 2022/9/9 */ public class HashTabDemo { public static void main(String[] args) { HashTab hashTab = new HashTab(7); //测试菜单 String key = ""; Scanner scanner = new Scanner(System.in); while (true) { System.out.println("add：添加雇员"); System.out.println("list：显示雇员"); System.out.println("find：查找雇员"); System.out.println("delete：删除雇员"); System.out.println("exit：退出系统"); System.out.println("请选择add/list/find/delete/exit"); key = scanner.next(); switch (key) { case "add": System.out.println("请添加员工id"); int id = scanner.nextInt(); System.out.println("请添加员工姓名"); String name = scanner.next(); // 创建雇员 Emp emp = new Emp(id, name); hashTab.add(emp); System.out.println("添加成功！"); break; case "list": hashTab.list(); break; case "find": System.out.println("请输入要查找雇员的id"); id = scanner.nextInt(); hashTab.findEmpByID(id); System.out.println("查找成功！"); break; case "delete": System.out.println("请输入要删除雇员的id"); id = scanner.nextInt(); hashTab.delEmp(id); System.out.println("删除成功！"); break; case "exit": scanner.close(); System.exit(0); System.out.println("成功退出！"); break; default: break; } } } } /** * 雇员类 */ class Emp { /** * id */ public int id; /** * 姓名 */ public String name; /** * next : null */ public Emp next; public Emp(int id, String name) { this.id = id; this.name = name; } } /** * 哈希表 管理雇员 */ class HashTab { //数组存放雇员信息 private EmpLinkedList[] empLinkedListsArray; //链表总数 private int size; /** * 构造 * @param size 多少链表 */ public HashTab(int size) { this.size = size; //初始化 empLinkedListsArray empLinkedListsArray = new EmpLinkedList[size]; //初始化每个链表 for (int i = 0; i < size; i++) { empLinkedListsArray[i] = new EmpLinkedList(); } } /** * 添加雇员 */ public void add(Emp emp) { //根据id 获得该员工的应该添加到的那一条链表 int empLinkedListNo = hashFun(emp.id); // 添加到对应的链表种 empLinkedListsArray[empLinkedListNo].add(emp); } /** * 遍历所有链表 */ public void list() { for (int i = 0; i < size; i++) { empLinkedListsArray[i].list(i); } } /** * 根据id 查找雇员 */ public void findEmpByID(int id) { //散列函数确定查找的链表 int empLinkedListNo = hashFun(id); Emp emp = empLinkedListsArray[empLinkedListNo].findEmpById(id); if (emp != null) { System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id); } else { System.out.println("在哈希表中，没有找到该雇员！"); } } /** * 删除雇员信息 * @param id 雇员id */ public void delEmp(int id) { int i = hashFun(id); empLinkedListsArray[i].delete(id); } /** * 散列函数 取模 */ public int hashFun(int id) { return id % size; } } /** * 创建EmpLinkedList，表示链表 */ class EmpLinkedList { /** * 头指针，指向第一个雇员的Emp */ private Emp head; /** * 添加雇员 * 添加的雇员id 自增长，id 总是从小到大，所有将该雇员添加到本链表的最后 */ public void add(Emp emp) { //第一个雇员 if (head == null) { head = emp; return; } //不是第一个雇员,添加到链表最后 Emp curEmp = head; while (true) { //到链表最后 if (curEmp.next == null) { break; } //后移 curEmp = curEmp.next; } //退出时，加入链表 curEmp.next = emp; } /** * 遍历链表 */ public void list(int num) { //链表为空 if (head == null) { System.out.println("第" + (num + 1) + "个链表为空!"); return; } System.out.print("第" + (num + 1) + "链表的信息为："); Emp curEmp = head; while (true) { System.out.printf("=> id = %d ,name=%s\t", curEmp.id, curEmp.name); //curEmp到最后结点 if (curEmp.next == null) { break; } //指针后移 curEmp = curEmp.next; } System.out.println(); } /** * 通过id查找雇员信息 * @param id 雇员id * @return 雇员信息 */ public Emp findEmpById(int id) { //链表是否为空 if (head == null) { System.out.println("链表为空！"); return null; } Emp curEmp = head; //id 不重复 while (true) { if (curEmp.id == id) { //curEmp指向要查找的雇员 break; } //退出 if (curEmp.next == null) { //没有找到该雇员的信息 curEmp = null; } //后移 curEmp = curEmp.next; } return curEmp; } /** * 根据id删除雇员信息 * @param id */ public void delete(int id) { if (head == null) { System.out.println("链表为空,无须删除"); return; } if (head.id == id) { //头节点为空 if (head.next == null) { head = null; } else { //后移 head = head.next; } return; } //辅助指针 Emp curEmp = head; boolean flag = false; while (true) { if (head.id == id) { head = head.next; return; } if (curEmp.next.id == id) { flag = true; break; } if (flag) { curEmp.next = curEmp.next.next; } else { System.out.println("要删除的雇员不存在"); } curEmp = curEmp.next; } } }
w EmpLinkedList();
}
}
/** * 添加雇员 */ public void add(Emp emp) { //根据id 获得该员工的应该添加到的那一条链表 int empLinkedListNo = hashFun(emp.id); // 添加到对应的链表种 empLinkedListsArray[empLinkedListNo].add(emp); } /** * 遍历所有链表 */ public void list() { for (int i = 0; i < size; i++) { empLinkedListsArray[i].list(i); } } /** * 根据id 查找雇员 */ public void findEmpByID(int id) { //散列函数确定查找的链表 int empLinkedListNo = hashFun(id); Emp emp = empLinkedListsArray[empLinkedListNo].findEmpById(id); if (emp != null) { System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id); } else { System.out.println("在哈希表中，没有找到该雇员！"); } } /** * 删除雇员信息 * @param id 雇员id */ public void delEmp(int id) { int i = hashFun(id); empLinkedListsArray[i].delete(id); } /** * 散列函数 取模 */ public int hashFun(int id) { return id % size; }
} /** 创建EmpLinkedList，表示链表 / class EmpLinkedList { /* 头指针，指向第一个雇员的Emp */ private Emp head; /** 添加雇员 添加的雇员id 自增长，id 总是从小到大，所有将该雇员添加到本链表的最后 */ public void add(Emp emp) { //第一个雇员 if (head == null) { head = emp; return; } //不是第一个雇员,添加到链表最后 Emp curEmp = head; while (true) { //到链表最后 if (curEmp.next == null) { break; } //后移 curEmp = curEmp.next; } //退出时，加入链表 curEmp.next = emp; } /** 遍历链表 */ public void list(int num) { //链表为空 if (head == null) { System.out.println(“第” + (num + 1) + “个链表为空!”); return; } System.out.print(“第” + (num + 1) + “链表的信息为：”); Emp curEmp = head; while (true) { System.out.printf(“=> id = %d ,name=%s\t”, curEmp.id, curEmp.name); //curEmp到最后结点 if (curEmp.next == null) { break; } //指针后移 curEmp = curEmp.next; } System.out.println(); } /** 通过id查找雇员信息 @param id 雇员id @return 雇员信息 */ public Emp findEmpById(int id) { //链表是否为空 if (head == null) { System.out.println(“链表为空！”); return null; } Emp curEmp = head; //id 不重复 while (true) { if (curEmp.id == id) { //curEmp指向要查找的雇员 break; } //退出 if (curEmp.next == null) { //没有找到该雇员的信息 curEmp = null; } //后移 curEmp = curEmp.next; } return curEmp; } /** 根据id删除雇员信息 @param id */ public void delete(int id) { if (head == null) { System.out.println(“链表为空,无须删除”); return; } if (head.id == id) { //头节点为空 if (head.next == null) { head = null; } else { //后移 head = head.next; } return; } //辅助指针 Emp curEmp = head; boolean flag = false; while (true) { if (head.id == id) { head = head.next; return; } if (curEmp.next.id == id) { flag = true; break; } if (flag) { curEmp.next = curEmp.next.next; } else { System.out.println(“要删除的雇员不存在”); } curEmp = curEmp.next; } } }
