如果一个 *** 作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。称这样的 *** 作为常数时间的 *** 作
- 执行时间固定的 *** 作都是常数时间的 *** 作（比如数组取值， *** 作时间，不会因为取下标为1或者取下标为10000的值，而发生变化，都是拿到地址直接取）
- 执行时间不固定的 *** 作，都不是常数时间 *** 作（比如一组数排序，你的算法就是要一个一个比较一遍，才能得到正确结果，那么数越多， *** 作时间越长，它不是固定的）
- 常见常数时间 *** 作
- 时间复杂度(由流程决定)
- 额外空间复杂度(流程决定)
- 常数项时间(实现细节决定)
就是研究整个算法执行完，常数时间 *** 作的执行次数，以此生成表达式
- 当完成表达式建立，只要把最高阶项留下即可，低阶项都去掉，高阶项的系数也去掉，最终记为O(忽略掉系数的最高阶项)
- 对于为什么要去掉系数，因为我们计算的是一个算法，在任何数据量下，所需时间复杂度，系数的大小没有什么意义
- 一定要按最差情况来，比如插入排序算法，123456，排序，无需交换位置，复杂度为O(N),而最坏情况654321，每次都要排满，为O(N ^ 2),那么我们只考虑最坏的情况，插入排序时间复杂度就是O(N ^ 2)
- 但是如果你是科班出身，时间复杂度计算，其实有3种，最好的情况(符号为Θ），平均情况(符号为Ω)，最差情况(符号为O)，但是面试问，日常计算等，都是只估计最差情况O
public class Main {
public static void main(String[] args) {
int arr[] = {10,4,5,2,3,7,11,26};
int minIndex;
//顺序排序，此算法主要常数 *** 作为比较，我们计算比较次数即可
for(int i = 0;iarr[j]){
minIndex = j;
}
}
if(i != minIndex){
//交换位置
arr[i] = arr[i]^arr[minIndex];//获取异或结果,相当于一个第三变量，一个密钥，这个密钥异或arr[i]就得到arr[minIndex],异或arr[minIndex]就可以得到arr[i]
arr[minIndex] = arr[i]^arr[minIndex];//异或结果再次异或arr[minIndex]，得到arr[i]
arr[i] = arr[i]^arr[minIndex];//异或结果异或arr[i],得到arr[minIndex]
}
}//去掉系数 (n-1)*(n)=n^2 - n ,只保留最高阶项 n^2 最终记为O(n^2)
for(int i = 0;i
插入排序时间复杂度也是O(N^2) public class Main {
public static void main(String[] args) {
int arr[] = {10,4,5,2,3,7,11,26};
System.out.print("原序列为:"+arr[0]+" ");
//插入排序，就是下标0~0保证有序，0~1保证有序，0~2保证有序....0~i保证有序，i是需要排序元素个数
//插入排序，0~0有序，不用排，直接排0~i
for(int i = 1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
for (int j = i-1;j >=0 && arr[j]>arr[j+1];j--){
arr[j] = arr[j]^arr[j+1];//获取异或结果,相当于一个第三变量，一个密钥，这个密钥异或arr[i]就得到arr[minIndex],异或arr[minIndex]就可以得到arr[i]
arr[j+1] = arr[j]^arr[j+1];//异或结果再次异或arr[minIndex]，得到arr[i]
arr[j] = arr[j]^arr[j+1];//异或结果异或arr[i],得到arr[minIndex]
}
}
System.out.print("n排序后为：");
for(int i = 0;i
额外空间复杂度
- 你要实现一个算法流程，在实现算法流程过程中，你需要开辟一些空间来支持你的算法流程，这就是额外空间复杂度
- 一些必要，或者用户要求的，和实现目标有关，但不是算法流程中需要的不算额外空间，比如：
- 作为输入参数的空间
- 作为输出结果的空间
- 如果你的流程还需要开辟空间才能让你的流程继续下去，这部分也是额外空间
- 如果你的流程只需要开辟有限的几个变量（比如一共就需要3个变量，如果你不确定几个，那就是无限）额外空间复杂度就是O(1)
常数项时间
- 因为时间复杂度这个指标，忽略低阶项和所有常数系数，那么同样时间复杂度的流程，比如选择排序，冒泡排序，插入排序，实际运行时，一样好吗？当然不是
- 如果两个相同时间复杂度的算法，要在时间上拼一个孰高孰低，拼一个优劣，就进入拼常数时间的阶段，简称拼常数项
- 直接申请大样本，实际去跑，然后观察运行时间，不要去理论分析，因为浪费精力，还没什么必要
如何获取最优解
- 先再时间复杂度上，尽可能低
- 满足时间复杂度后，使用最少的空间，即为最优解
- 常数项比较无关紧要，因为这个因素只决定实现层次的优化和考虑，而和怎么解决整个问题的思想无关
常见时间复杂度,排名由小到大，最好的是第一个，最坏的是最后一个，
- O(1)：常数级别算法
- O(logN)：log以2为底的N
- O(N)
- O(N*logN)
- O(N ^ 2),O(N ^ 3)…,O(N ^ K)
- O(2 ^ N),O(3 ^ N)…,O(K ^ N)
- O(N!)：N的阶乘
2. 回溯
2.1 迷宫问题
- 小球初始在迷宫左上角，求出小球走到右下角的路径
- 运行效果(1:代表墙，0：代表空地，2：代表小球走的路线)
- 代码
public class Test {
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;
}
//设置挡板, 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);
//输出新的地图, 小球走过，并标识过的递归
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();
}
}
//使用递归回溯来给小球找路
//说明
//1. map 表示地图
//2. i,j 表示从地图的哪个位置开始出发 (1,1)
//3. 如果小球能到 map[6][5] 位置，则说明通路找到.
//4. 约定： 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 ； 2 表示通路可以走 ； 3 表示该点已经走过，但是走不通
//5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
public static boolean setWay(int[][] map, int i, int j) {
if(map[6][5] == 2) { // 通路已经找到ok
return true;
} else {
if(map[i][j] == 0) { //如果当前这个点还没有走过
//按照策略 下->右->上->左 走
map[i][j] = 2; // 假定该点是可以走通.
if(setWay(map, i+1, j)) {//向下走
2.2 n皇后问题
打印指定n皇后的所有棋盘摆法，结果存放到集合中
- 我们以8皇后举例（8皇后就是8*8的棋盘摆8个皇后，n皇后就是n * n的棋牌摆n个皇后）
- 核心思路
- n代表皇后个数，有n个皇后，就代表棋盘有几行几列，8皇后，就8行8列
- 通过一维数组抽象皇后在棋盘位置，用数组下标代表皇后所在行，用下标对应元素值，代表皇后所在列，比如在下标从0开始的情况下。arr[0]=0 就代表第1个皇后，在第一行第1列，arr[4]=3 代表当前皇后在第5行，第4列
- 判断皇后是否在同一行因为我们按行摆，每个皇后不可能在同一行，无需考虑行
- 判断是否在同一列，我们通过数组元素对应值表示列，所以只需要判断当前皇后和已有皇后的元素值是否相同，就可以知道是否冲突，比如a[0]=1 和 a[3]=1，说明在第一行的皇后和在第4行的皇后都在第一列，冲突
- 判断是否在对角线，根据数学知识，如果两个坐标的横坐标相减的绝对值，等于纵坐标相减的绝对值，说明两个点，构成对角线，比如a[0]=0和a[1]=1,|0-0| = 0 = |1-1|
- 运行效果
- 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private int arr[];//用来存储皇后，其中下标代表每个皇后所在行，值代表每个皇后所在列
private ArrayList> result = new ArrayList<>();
public List> solveQueues(int n){
arr = new int[n];
check(n,0);
return result;
}
public void check(int n,int index){
//递归退出条件，因为数组下标从0开始，所以index==n时，实际是在摆n+1皇后，此时就可以退出了
if(index==n){//如果满足退出条件，说明已经摆完，进行处理，这里将棋盘结果封装到List集合result中
ArrayList list = new ArrayList<>();
for(int i = 0;i < n;i++){
StringBuilder stringBuilder = new StringBuilder();
for(int j = 0;j < n;j++){
if(arr[i]==j){
stringBuilder.append("Q");
}else{
stringBuilder.append(".");
}
}
list.add(new String(stringBuilder));
}
result.add(list);
}else{
for(int i = 0;i < n;i++){//这个循环表示列，给每行皇后，尝试放在不同列上，因为是n*n的棋盘，所以n既可以代表行数，也能代表列数
arr[index] = i;
if(judge(index)){//判断当前行（index行）的皇后，摆在此列（i列），是否冲突,不冲突返回true,摆下一行
check(n,index+1);
}//如果冲突，重新摆这一行
}
}
}
public boolean judge(int index){
for(int i = 0;i> lists;//用来保存结果集
lists=main.solveQueues(n);//调用n皇后入口方法
for(List list1 : lists){//遍历输出棋盘
System.out.println(list1);
}
}
sc.close();
}
}
3. 排序
1. 插入排序
- 就是依次遍历要排序的序列元素，将每个元素插入到合适的位置，就是遍历第一个元素时，保证这个元素有序（因为一个元素本来就有序，所以不用排），遍历第二个元素时，保证前两个元素有序，遍历第三个元素时，保证前三个元素有序，保证有序的过程，其实就是将元素插入到合适位置的过程，所以称之为插入排序。（注意：每个元素，都是从后往前依次比较，这个问题很大，我们后面说）
运行效果
代码
public static void main(String[] args) {
int arr[] = {10,4,5,2,3,7,11,26};
System.out.println("原序列为:"+ Arrays.toString(arr));
//插入排序，就是下标0~0保证有序，0~1保证有序，0~2保证有序....0~i保证有序，i是需要排序元素个数
//插入排序，0~0有序，不用排，直接排0~i
for(int i = 1;i<=arr.length-1;i++){
for (int j = i-1;j >=0 && arr[j]>arr[j+1];j--){//两个两个比较，从小到大排
arr[j] = arr[j]^arr[j+1];//获取异或结果,相当于一个第三变量，一个密钥，这个密钥异或arr[i]就得到arr[minIndex],异或arr[minIndex]就可以得到arr[i]
arr[j+1] = arr[j]^arr[j+1];//异或结果再次异或arr[minIndex]，得到arr[i]
arr[j] = arr[j]^arr[j+1];//异或结果异或arr[i],得到arr[minIndex]
}
}
System.out.print("排序后为：");
for(int i = 0;i
2. 希尔排序
- 插入排序的劣势
- 因为插入排序每个元素都是从后往前比较，那么当插入的数较小，排序（比较）次数明显增多，比如10000个数排序，偏偏最后一个数是最小的，那么单单最后一个数就需要比较9999次，才能完成最后一个数的排序，效率将会十分低下
- 希尔排序
- 希尔与1959年提出的算法，插入排序的改进版，更加高效，少许人称缩小增量排序
- 采用了分治思想，就是分而治之，基本就是按照下标的一定增量分组（比如增量是5，那么下标为0的元素和下标为0+5=5的元素分组，有过有下标为5+5=10的元素，那么0、5、10。3个下标元素分为一组，依次类推），对每组分别使用插入排序，然后增量就会越来越少，当增量为1时，整个文件正好成为一组，最后再执行一次插入排序，即可完成整体排序（增量缩小规则，增量 = 增量/2，初始增量为序列长度，第二次为初始增量算出的增量结果，第三次为第二次算出的增量结果）
希尔排序有两种实现方法，交换法实现希尔排序，思路简单，但速度非常慢，移动法实现希尔排序，思路不容易理解，但速度快
- 移动法，就是杜绝没用的交换 *** 作，比如4、5、3、1这4个数，1要进行插入排序，那么我们就先将1这个数保存，然后让3移动到1的位置，5移动到3的位置，4移动到5的位置，最后，让1存储到4这个位置，这样就杜绝了交换 *** 作，效率大大提高
- 80000组数据测试发现（不使用位运算的前提下），使用插入排序排80000个数据，花费4秒，使用交换法实现的希尔排序花费了14秒，使用移动法实现的希尔排序花费了4毫秒（1秒=1000毫秒）（下图是使用位运算的消耗时间）
- 运行结果
- 代码
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
public class Test {
public static void main(String[] args) {
int arr[]= {8,9,1,7,2,3,5,4,6,0};
int arr1[]={10,4,5,2,3,7,11,26};
System.out.println("原序列为:"+ Arrays.toString(arr));
shellSort1(arr);
print(arr);
System.out.println("原序列为:"+ Arrays.toString(arr1));
shellSort1(arr1);
print(arr1);
System.out.println("=============================移动法============================");
int arr2[]= {8,9,1,7,2,3,5,4,6,0};
int arr3[]={10,4,5,2,3,7,11,26};
System.out.println("原序列为:"+ Arrays.toString(arr));
shellSort2(arr2);
print(arr2);
System.out.println("原序列为:"+ Arrays.toString(arr1));
shellSort2(arr3);
print(arr3);
//如果想要测试，需要你把，希尔排序方法中的输出语句注释掉
// System.out.println("=================================80000组数据测试======================");
// int array[] = new int[80000];
// for (int i = 0 ;i<80000;i++){//生成80000个[0,8000000)的随机数
// array[i] = (int) (Math.random()*800000);
// }
// int[] array2 = array.clone();
// int[] array3 = array.clone();
// long start = new Date().getTime();
// insertSort(array);
// long end = new Date().getTime();
// System.out.println("插入排序消耗时间"+(end-start));
// start = new Date().getTime();
// shellSort1(array);
// end = new Date().getTime();
// System.out.println("交换法希尔排序消耗时间"+(end-start));
// start = new Date().getTime();
// shellSort2(array);
// end = new Date().getTime();
// System.out.println("移动法希尔排序消耗时间"+(end-start));
}
public static void insertSort(int arr[]){
//插入排序，0~0有序，不用排，直接排0~i
for(int i = 1;i<=arr.length-1;i++){
for (int j = i-1;j >=0 && arr[j]>arr[j+1];j--){//两个两个比较，从小到大排
arr[j] = arr[j]^arr[j+1];//获取异或结果,相当于一个第三变量，一个密钥，这个密钥异或arr[i]就得到arr[minIndex],异或arr[minIndex]就可以得到arr[i]
arr[j+1] = arr[j]^arr[j+1];//异或结果再次异或arr[minIndex]，得到arr[i]
arr[j] = arr[j]^arr[j+1];//异或结果异或arr[i],得到arr[minIndex]
}
}
}
public static void print(int arr[]){
System.out.print("排序后为：");
for(int i = 0;i1){//如果增量为1,那么只需要最后一次插入排序
for(int i = gap;i < arr.length;i++){//控制分组,但是插入排序，总是，后面的不断比较前面的
for(int j = i-gap;j >= 0 && arr[j] > arr[j+gap];j-=gap){//控制增量排序,并且从小到大，不断从后往前比较
arr[j]=arr[j]^arr[j+gap];
arr[j+gap] = arr[j]^arr[j+gap];
arr[j] = arr[j]^arr[j+gap];
}
}
gap /= 2;
System.out.print("第"+index+"轮希尔排序结果为：");//用来打印的可省略代码
index++;
print(arr);
}
insertSort(arr);
}
public static void shellSort2(int arr[]){
int gap = arr.length/2;//增量
int index = 1;//可省略的代码，用来打印
while(gap>1){//如果增量为1,那么只需要最后一次插入排序
for(int i = gap;i < arr.length;i++){//控制分组,但是插入排序，总是，后面的不断比较前面的
//
if(arr[i-gap] > arr[i]){//如果需要交换位置，就将当前值记录
int temp = arr[i];//将当前要交换的值记录，其它在它前面比他小的数，依次后移即可
int j ;
for(j = i -gap;j >= 0 && temp < arr[j];j-=gap){
arr[j+gap] = arr[j];//元素前移
}
arr[j+gap] = temp;
}
}
gap /= 2;
System.out.print("第"+index+"轮希尔排序结果为：");
index++;
print(arr);
}
insertSort(arr);
}
}
3. 快速排序
- 快速排序是冒泡排序的改进版。依然采用分治思想，先通过一趟排序将数据分割成两部分，其中一部分的所有数据要比另一部分的所有数据要小，然后再按此方法，对这两部分数据分别进行快速排序，整个过程可以用递归实现。
- 就是拿到一组数据，先找一个数，作为中间数（你可以直接拿序列中间的数，或者拿最后一个数，或者第一个数），然后依据此数，先排成两组，不用有序，就是比中间数大的，分为一组，比中间数小的，分为一组，中间数最后归哪组，随意，不归任何一组也可以。然后分别对这两组再进行快速排序（就像冒泡一样，每次把中间数冒出去）
- 实现思路与运行效果
- 首先，我们选择中间数（基准数），我们这里指定序列的第一个数是基准数，将基准数保存。然后创建两个下标，分别位于序列的最左面和最右面，依次从右边找大于中间数的值，将其放在左边，左边找小于中间数的值，放在右边，最后，左边下标最后的位置，就是中间，将中间数放进去即可
- 代码
import java.util.Arrays;
import java.util.Date;
public class Test {
public static void main(String[] args) {
int arr[]= {8,9,1,7,2,3,5,4,6,0};
int arr1[]={-9,78,0,23,-567,70, -1,900, 4561};
System.out.println("原序列为:"+ Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
print(arr);
System.out.println("原序列为:"+ Arrays.toString(arr1));
quickSort(arr1,0,arr1.length-1);
print(arr1);
System.out.println("=================================80000组数据测试======================");
int array[] = new int[80000];
for (int i = 0 ;i<80000;i++){//生成80000个[0,8000000)的随机数
array[i] = (int) (Math.random()*800000);
}
long start = new Date().getTime();
quickSort(array,0,array.length-1);
long end = new Date().getTime();
System.out.println("消耗时间"+(end-start));
}
public static void quickSort(int[] a, int left, int right) {
if (left < right) {//如果l>r表示已经排完，可以出递归了
int l = left;//左下标
int r = right;//右下标
int temp = a[l];//保存一个指标变量
while (l < r) {//如果l>=r时，退出循环，表示排完
while(l < r && a[r] > temp)//从右向左遍历找小于temp的数，但是不能越过l
r--; // 从右向左找第一个小于temp的数
if(l < r)//如果上面循环结束，依然ll,表示满足交换条件
a[r--] = a[l]; //将左边第一个大于temp的数，放在右边，因为它的值已经移动到左边了，不用担心覆盖
}
a[l] = temp;//最后l下标所在位置，就是temp最终可以确定的位置
quickSort(a, left, l-1);
quickSort(a, l+1,right);
}
}
public static void print(int arr[]){
System.out.print("排序后为：");
for(int i = 0;i
4. 归并排序
- 利用归并思想实现的排序方式，采用经典分治策略，将问题分成多个小问题，依次求解，最后将小问题的结果修补到一起。也就是分而治之
- 运行效果
- 代码
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int arr[] = {8,4,5,7,1,3,6,2};
int temp[] = new int[arr.length];
System.out.println("原数组为："+Arrays.toString(arr));
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);
}
}
public static void merge(int arr[],int left,int mid,int right,int[] temp){
int i = left;//初始化i，左边有序序列的初始索引
int j = mid + 1;//初始化j,右边有序序列的初始索引
int t = 0;//指向temp数组的当前索引
//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];
i++;
t++;
}
while(j <= right){//右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
j++;
t++;
}
//3、将temp数组的元素拷贝到arr，但并不是每次都拷贝所有
t = 0;
int tempLeft = left;
while(tempLeft <= right){
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
5. 基数排序（桶排序）
- 属于分配时排序，又称桶子法，顾名思义，它通过键值的各个位的值，将要排序的元素分配至某些桶中，达到排序的作用
- 基数排序法是属于稳定的排序，并且效率很高
- 桶排序的扩展
- 1887年赫尔曼·何乐礼发明的。将整数按位数切割成不同数字，然后按每个位数分别比较
- 基本思想
- 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成后，数列就有序了
- 实现思路
- 首先确定数组数据最大位数，比如最大数是1900，那么最大位数就是4位
- 创建10个桶，就是一个二维数组，里面有10个一维数组，每个一维数组代表一个桶，分别代表0-9
- 创建桶的有效数据记录，就是一个一维数组，记录每个桶的有效数据个数
- 根据最大位数，进行遍历，如果要从小到大排序，那么就需要先比较个位，根据个位的数字，放到对应桶中，然后让桶有效数据记录自增
- 然后依次遍历桶，将桶中数据，放到原数组，然后将桶有效数据记录清零，然后比较十位，依次类推
- 运行效果
- 代码（没有做负数的处理）
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int arr[] = {53,3,542,748,14,214};
radixSort(arr);
int arr1[] = {9,7,13,0,5,0,14,21,197};
radixSort(arr1);
}
public static void radixSort(int arr[]){
//1. 通过Java Stream API Arrays.stream(arr).max().getAsInt() 获取数组最大数，然后+""将其变成字符串，通过length()方法获取字符串长度确定最大位数
int maxLength = (Arrays.stream(arr).max().getAsInt()+"").length();
//2. 创建桶,一共10个桶，每个桶的长度，因为不确定数据个数，所以都设置成arr.length,这样就不会出现溢出，典型的空间换时间
int bucket[][] = new int[10][arr.length];
//3. 创建桶的有效数据记录，记录每个桶的有效元素个数，下标
int bucketEleCount[] = new int[10];
//4. 根据最大位数遍历，按从小到大排
for(int i = 0;i < maxLength;i++){
//遍历数组放入桶
for( int j = 0;j
6. 堆排序
- 堆排序是利用堆（数据结构）设计的排序算法，属于选择排序，最坏，最好，平均时间复杂度均为O(n logn)，不稳定排序
- 堆是具有以下性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，
- 没有要求结点的左孩子的值和右孩子的值的大小关系。
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
堆排序基本思想（以升序使用大顶堆为例）
- 将待排序序列构成一个大顶堆
- 因为大顶堆最大值就是根节点，此时将其与末尾元素交换，末尾值就是最大值
- 然后将剩下的n-1个元素构成大顶堆，重复上面 *** 作，每次构建都可以获取一个最大值，最终得到有序序列
代码
- 用到的公式(二叉树的基本公式)
- arr[i]<=arr[2i+1] && arr[i] <= arr[2i+2] 小顶堆条件，当前非叶子节点arr[i]，左节点和右节点，都小于它,大顶堆正好相反，左右都大于它本身
- 第一个非叶子节点arr.length/2-1
- 当前节点的左子节点，i2+1，当前节点右子节点i2+2
- 基本实现思路
- 构建大顶堆，从二叉树下面往上构建
- 每构建一次，交换堆顶元素到堆最后面，这样整个数组依次的就形成了，最后一个是最大值，倒数第二个是倒数第二大的值
- 然后去掉数组后面内些排好的，再次构建堆，再交换，依次类推
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int arr[] = {4,6,8,5,9};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int arr[]){
//第一次构建大顶堆，需要单独来，后面的就依次按规则就好，当然有其它方法
//1.将序列构建成大顶堆,length/2-1是第一个非叶子节点，length/2-2是第二个非叶子节点，依次类推，0是整个序列个根节点
for(int i = arr.length /2 -1;i >= 0 ;i--){
//i是每个非叶子节点，从下往上依次构建，调用adjustHeap方法，让i指向的节点作为根，保存最大值
adjustHeap(arr,i,arr.length);
}
//2.上面构建了一次大顶堆，获取了一个最大值，接下来进行交换，然后构建剩下的大顶堆，让其余的最大值有序
for(int i = arr.length-1;i>0;i--){
// 2.1 堆顶元素与末尾元素交换，此时最大值保存到了末尾，length需要减少
arr[i]=arr[i]^arr[0];
arr[0]=arr[i]^arr[0];
arr[i]=arr[i]^arr[0];
// 2.2 重新调整结构(构建剩下的大顶堆)，使其满足堆定义，然后继续交换，直到整个序列有序
adjustHeap(arr,0,i);//每次都从0开始，但是长度，每次都要递减，因为最后一个元素有序了
}
}
public static void adjustHeap(int arr[],int i ,int length){
int temp = arr[i];//保存当前非叶子节点的值
//以i为根（父节点）构建大顶堆，i*2+1是当前i节点的左子节点下标，K*2+1是k节点的左子节点下标
for(int k = i*2+1;ktemp){
arr[i] = arr[k];
i = k;//这里将i指向它的子节点k，下次循环就是它的子节点
}else{
break;//如果他比i小，那么无需交换值，直接退出循环即可
}
}
//此时，大顶堆构建完成，i为父节点的树的最大值，放在了最顶部
arr[i] = temp;//最后将temp的值赋值给做出更换的位置
}
}
4. 查找
- java中常用查找有：顺序（线性）查找、二分/折半查找、插值查找、斐波那契查找
1. 二分查找（递归）
- 二分查找的前提是，序列有序
- 首先我们要查找一个数，先找到序列中间的数，进行比较，如果比中间数大，那么我们从右边继续找，如果比中间数小，那么左边找
- 比如比中间数大，那么去右边找，此时，需要重新找右边这一半序列的中间数，然后继续判断，依次类推
- 运行效果
- 代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//注意：使用二分查找的前提是 该数组是有序的.
public class Test {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
//
System.out.println("序列为："+ Arrays.toString(arr1));
int resIndex = binarySearch(arr1, 0, arr1.length - 1, 8);
System.out.println("元素8的下标为resIndex=" + resIndex);
System.out.println("序列为："+Arrays.toString(arr));
List resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
System.out.println("元素1000的下标为resIndexList=" + resIndexList);
}
// 二分查找算法
public static int binarySearch(int[] arr, int left, int right, int findVal) {
// 当 left > right 时，说明递归整个数组，但是没有找到
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) { // 向 右递归
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 向左递归
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
//完成一个课后思考题:
public static List binarySearch2(int[] arr, int left, int right, int findVal) {
System.out.println("hello~");
// 当 left > right 时，说明递归整个数组，但是没有找到
if (left > right) {
return new ArrayList();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) { // 向 右递归
return binarySearch2(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 向左递归
return binarySearch2(arr, left, mid - 1, findVal);
} else {
// * 思路分析
// * 1. 在找到mid 索引值，不要马上返回
// * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
// * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
// * 4. 将Arraylist返回
List resIndexlist = new ArrayList();
//向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
int temp = mid - 1;
while(true) {
if (temp < 0 || arr[temp] != findVal) {//退出
break;
}
//否则，就temp 放入到 resIndexlist
resIndexlist.add(temp);
temp -= 1; //temp左移
}
resIndexlist.add(mid); //
//向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
temp = mid + 1;
while(true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
break;
}
//否则，就temp 放入到 resIndexlist
resIndexlist.add(temp);
temp += 1; //temp右移
}
return resIndexlist;
}
}
}
2. 插值查找
- 二分查找改进版，因为如果我们要查找一个有序序列的第一个元素，那么它需要从中间一次一次折半，反而耗费大量时间，而插值查找与二分查找不同的是，每次从自适应mid处开始查
- 二分查找公式为mid = (left+right)/2,而插值查找公式为mid = left + (key - a[left])/(a[right]-a[left])*(high-low)
- 代码（和二分查找一样，就换了个公式,然后退出递归的条件变一下就可以了）
//编写插值查找算法
//说明：插值查找算法，也要求数组是有序的
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
System.out.println("插值查找次数~~");
//注意：findVal < arr[0] 和 findVal > arr[arr.length - 1] 必须需要
//否则我们得到的 mid 可能越界
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
// 求出mid, 自适应
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal) { // 说明应该向右边递归
return insertValueSearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) { // 说明向左递归查找
return insertValueSearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
3. 斐波那契查找
- 利用斐波那契数列查找，查找的时候，需要先确定数组最大下标，如果比相应斐波那契数列的小，那么需要创建一个新的数组，来填充数据，和斐波那契数列配合
- 实际上查就是在新数组中查找，不断的通过斐波那契数列来查
- 核心思路，就是如何和斐波那契配合，所以也无需过多解释，直接看代码理解
import java.util.Arrays;
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("index=" + fibSearch(arr, 189));// 0
}
//因为后面我们mid=low+F(k-1)-1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列
//非递归方法得到一个斐波那契数列
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;
}
//编写斐波那契查找算法
//使用非递归的方式编写算法
public static int fibSearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
int k = 0; //表示斐波那契分割数值的下标
int mid = 0; //存放mid值
int f[] = fib(); //获取到斐波那契数列
//获取到斐波那契分割数值的下标
while(high > f[k] - 1) {
k++;
}
//因为 f[k] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]
//不足的部分会使用0填充
int[] temp = Arrays.copyOf(a, f[k]);
//实际上需求使用a数组最后的数填充 temp
//举例:
//temp = {1,8, 10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
for(int i = high + 1; i < temp.length; i++) {
temp[i] = a[high];
}
// 使用while来循环处理，找到我们的数 key
while (low <= high) { // 只要这个条件满足，就可以找
mid = low + f[k - 1] - 1;
if(key < temp[mid]) { //我们应该继续向数组的前面查找(左边)
high = mid - 1;
//为甚是 k--
//说明
//1. 全部元素 = 前面的元素 + 后边元素
//2. f[k] = f[k-1] + f[k-2]
//因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
//即 在 f[k-1] 的前面继续查找 k--
//即下次循环 mid = f[k-1-1]-1
k--;
} else if ( key > temp[mid]) { // 我们应该继续向数组的后面查找(右边)
low = mid + 1;
//为什么是k -=2
//说明
//1. 全部元素 = 前面的元素 + 后边元素
//2. f[k] = f[k-1] + f[k-2]
//3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
//4. 即在f[k-2] 的前面进行查找 k -=2
//5. 即下次循环 mid = f[k - 1 - 2] - 1
k -= 2;
} else { //找到
//需要确定，返回的是哪个下标
if(mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
4. 二分查找（非递归版本）
- 运行效果
- 代码
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {1,3,8,10,11,67,100};
System.out.println("数组元素为："+Arrays.toString(arr));
int index = binarySearch(arr,10);
System.out.println("查找元素10的下标为"+index);
}
public static int binarySearch(int[] arr,int target){
int left = 0;//左下标，起始为0
int right = arr.length - 1; //右下标，起始为最后一个元素下标
while(left <= right){//如果左>右下标，表示没有找到
int mid = (left + right)/2;//找到中间下标
if(arr[mid]==target){//如果找到了，返回下标
return mid;
}else if(arr[mid]>target){//如果比要找的数大，去左边找
right = mid-1;
}else{//否则去右边找
left = mid+1;
}
}
//如果没找到，返回-1
return -1;
}
}
5. 分治算法
1. 汉诺塔
- 运行效果
- 代码
public class Test {
public static void main(String[] args) {
System.out.println("5个盘子的移动步骤");
hanoiTower(5,'A','B','C');
}
public static void hanoiTower(int num,char a,char b,char c){
//如果只有一个盘了，就不需要分了，因为已经是最小的单位了，开始治理它，直接从a移动到c
if(num == 1)
System.out.println("第1个盘从 "+a+"->"+c);
else{
//如果多于一个盘，我们就用分治思想，将所有盘子分成两部分，最下面的一个盘，和上面的所有盘
//先把上面的所有盘，从A移动到B，移动过程借助C移动
hanoiTower(num-1,a,c,b);
//下面的盘，从A移动到C
System.out.println("第"+num+"个盘从 "+a+"->"+c);
//最后再把B塔的盘，全部移动到C，借助A塔移动
hanoiTower(num-1,b,a,c);
}
}
}
6. 动态规划
任何动态规划的动态转移方程，都是暴力递归过程的推导 只要暴力递归有重复计算，那么我们就需要动态规划，避免掉这些重复计算 所有暴力递归均为思路，不代表可以解题，因为暴力递归及其消耗内存，很可能内存溢出，只是为了让大家了解，如果通过思考起来更简单的暴力递归，推导动态规划
- 有一堆物品，每件物品都有自己的重量w和价值v
- 我们有一个背包，背包最大装载重量为rest
- 求背包如何装载物品，让背包中物品价值最大
首先研究暴力递归方法 public class Main {
public static int process(int[] w,int[] v,int index,int rest){
if(rest < 0) return -1;//如果背包剩余空间小于0，表示根本放不下，返回-1表示放不下的状态
if(index == w.length) return 0;//如果index == w.length，说明已经没有物品了，是递归的退出条件
//有货也有空间
int p1 = process(w,v,index + 1,rest);//第一种状态，表示当前下标物品没有放进背包，所以当前背包容量rest无需减少
int p2 = -1;//用来保存物品放到背包的情况，默认是不成立
int p2Next = process(w,v,index + 1,rest - w[index]);//第二种状态，表示当前下标物品放入背包，rest需要减少
if(p2Next != -1){//如果第二种状态的方案返回不是-1，表示方案可行，那么给p2的价值增加
p2 = v[index] + p2Next;//增加当前物品的价值
}
return Math.max(p1,p2);//返回第一种状态和第二种状态的最大值
}
public static void main(String[] args) {
int[] w = {12,13,15,27,36,48};
int[] v = {10,5,27,58,100,100};
System.out.println(process(w,v,0,50));
}
}
进行动态规划
- 首先，我们发现，暴力递归过程中，始终发生变化的值只有两个，当前物品下标index和背包剩余空间rest
- 假设，我们再递归中，多次遇到当前物品下标是5，背包剩余空间是10的情况，那么我们就在第一次遇见这个情况时，将这个过程f(5,10)=x,保存起来，当第二次遇到，发现f(5,10)=x，已经有做过缓存，那么我们直接获取x结果，无需再次进入递归
- 所以我们用一个二维表来存储这些结果，想象用index当x轴坐标，用rest当y轴坐标（如果用数组，就是arr[ index ] [ rest ]）
- 那么我们需要规定二维表的大小，我们发现如果想要完全存储结果，只需要将二维表定义成arr[ 物品数量 ] [背包最大空间]，就完全可以存储所有结果
- 但是我们保留递归中，递归退出条件为index == w.length;这说明我们除了物品数量外，还用到了多于物品数量的一个值，来当做我们退出递归的条件，所以我们也要在二维表中存储，那么定义为arr[ 物品数量+1 ][背包最大空间]
- 同理，我们需要为背包最大空间这里，考虑0的情况，所以我们要定义为arr[ 物品数量+1 ] [ 背包最大空间 + 1]
- 好的动态规划，就是用已知信息，绘制二维表（当然根据不同问题，可能是一维表，那就更简单了），然后将结果返回，也就是不需要递归了，最常见的就是用两个for循环直接构建二维表，
- 我们已知，最终背包容量为0的情况，和index最后一行是0的情况，所以我们可以自下而上，利用已知的为0情况，构建出2维表
下面的代码，细心点你就会发现，暴力递归中，所有return的值，就是你动态规划时要往表结构中添加的值，而我们暴力递归从上到下，从右到左，生成的结构，恰好最下面和最左面是最终的固定值0.所以我们动态规划时，就从下到上，从左到右利用已知的条件0生成二维表即可 public class Main {
public static int process(int[] w,int[] v,int bag){
int N = w.length;
int[][] dp = new int[N+1][bag+1];//保存动态规划结果，默认值都是0，所以我们将二维表的所有0情况已经规划完毕
//接下来就是用动态规划，完成和暴力递归完全相同的功能
for(int index = N - 1;index >= 0 ;index--){//自下而上，依次遍历每一行，因为最后一行，是暴力递归时的出口0，我们刚刚初始化已经完成
for(int rest = 1;rest <= bag;rest++){//自左向右遍历每一列，同样，0已经初始完成，直接遍历1开始即可
dp[index][rest] = dp[index + 1][rest];//相当于暴力递归的p1，也就是当前物品不加入背包，而去思考下一个物品的情况，所以index+1
if(rest >= w[index]){//如果rest比当前物品所需容量大，那么表示当前物品可放入背包
//v[index]+dp[index+1][rest-w[index]] 相当于暴力递归的p2，存储当前物品放入背包，背包容量减少的情况
//然后就可以得到当前情况值，选出p1和p2中最大的内个
dp[index][rest] = Math.max(dp[index][rest],v[index]+dp[index+1][rest-w[index]]);
}
}
}
return dp[0][bag];//暴力递归最终返回结果，对应的就是二维表的右上角的元素
}
public static void main(String[] args) {
int[] w = {12,13,15,27,36,48};
int[] v = {10,5,27,58,100,100};
System.out.println(process(w,v,50));
}
}
2. 找钱问题
- 给定arr数组，所有值都为正数且不重复，代表一种面值的货币，不规定货币的数量
- 用变量aim，代表要找的钱数
- 求共有多少种找钱方式，利用不同货币数量，找同样的钱
- 一看题就可以猜出二维表纵坐标是硬币面值，横坐标是张数，值是钱的数量
- 具体分析
- 首先这道题，我们知道要组成钱（假设为rest）的大小，但是货币又没有要求
- 那么最好的办法就是，我们每次递归都用rest-当前面值，当rest==0时，表示达到要求
下面列出如何一步一步从暴力递归->记忆化搜索->精细化动态规划。以及3种算法所消耗时间 package com.company;
import java.util.Date;
public class Main {
public static int dfs(int arr[],int index,int rest){
if(rest < 0) return 0;//这句其实没用，因为后面for循环已经解决了这个问题，如果剩余的钱小于0，表示找的钱超了，那么返回0，表示这种方法不行
//如果钱不小于0，表示还有机会获取正确答案，我们判断idnex == arr.length，看看是否还有货币，如果相等，表示没有钱了
if(index == arr.length) return rest==0?1:0;//如果当前rest已经为0，表示满足要求，返回1，否则，因为已经没钱了，这种方法不行，返回0
int ways = 0;//记录方法数
//因为我们每张货币不规定数量，所以每张货币使用范围，就是0~n，但要满足n*货币面值=0;index--){//自下而上
for(int rest = 0;rest<=aim;rest++){//自左向右
//int ways = 0;
//for(int i =0;(arr[index]*i)<=rest;i++){
// ways+=dp1(arr,index+1,rest-(arr[index]*i),dp);
//}
//根据上面暴力递归，来推导dp2[index][rest]即可，但是这种会有枚举问题，就是比如我dp2[5][5]，我需要计算所有dp2[4][0....5]的值，
//但是这些值在dp2[5][4]的时候就已经算过了，所以这就重复计算，效率反而还不如用记忆化搜索来优化暴力递归
// for(int i = 0;(arr[index]*i)<=rest;i++){
// dp2[index][rest]=dp2[index][rest]+dp2[index+1][rest-(arr[index]*i)];
// }
//解决枚举问题,dp2[5][5]==dp2[5][4]+dp2[4][5]
dp2[index][rest] = dp2[index+1][rest];
if(rest - arr[index]>=0){//如果下标不越界
dp2[index][rest] += dp2[index][rest-arr[index]];
}
}
}
return dp2[0][aim];
}
public static void main(String[] args) {
int arr[] = {5,10,50,100};
int aim = 9900;
long start = new Date().getTime();
System.out.println(dfs(arr,0,aim));
long end = new Date().getTime();
System.out.println("所用时间（单位毫秒）"+(end-start));
int dp[][] = new int[arr.length+1][aim+1];//缓存表
for(int i = 0 ;i
7. KMP算法
- 解决模式串在文本串是否出现过，如果出现过，获取最早出现的位置的经典算法
- 常用于在一个文本串S内查找一个模式串P出现的位置，此算法由Donald Knuth、Vaughan Pratt、James H.Morris三人于1977年联合发表，故取三人姓氏命名此算法为Knuth-Morris-Pratt，简称KMP算法
- 利用之前判断过的信息，通过一个next数组，保存模式串中前后最常公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去大量计算时间
代码
- 运行效果
- 代码
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
//String str2 = "BBC";
int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
System.out.println("next=" + Arrays.toString(next));
int index = kmpSearch(str1, str2, next);
System.out.println("index=" + index); // 15了
}
//获取到一个字符串(子串) 的部分匹配值表
public static int[] kmpNext(String dest) {
//创建一个next 数组保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
//我们要依次遍历字符串，去掉上面字符串长度为1的A，循环第一次AB，第二次ABC，当后缀和前缀有相同的串时，进行记录，i表示串长度，j表示前后缀相同时，这个缀的长度
for(int i = 1, j = 0; i < dest.length(); i++) {
//当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
//直到我们发现 有 dest.charAt(i) == dest.charAt(j)成立才退出
//这是kmp算法的核心点
//比如i=4时，j=0.子串为ABCDA，此时A==A，退出循环-----比如i=5时，j=1，子串为ABCDAB，此时因为A==A上次比较过了，不用再比较，直接B==B，退出循环
while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j-1];
}
//当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
//A==A-----B==B
if(dest.charAt(i) == dest.charAt(j)) {
j++;
}
//next[4]=1;===next[5] == 2
next[i] = j;
}
return next;
}
//写出我们的kmp搜索算法
public static int kmpSearch(String str1, String str2, int[] next) {
//遍历
for(int i = 0, j = 0; i < str1.length(); i++) {
//需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
//KMP算法核心点, 可以验证...
//String str1 = "BBC ABCDAB ABCDABCDABDE";
// String str2 = "ABCDABD";
//匹配表next=[0, 0, 0, 0, 1, 2, 0]
//当i = 10,j = 6时，前面ABCDAB都匹配成功，但是现在空格比较D，不相等，此时说明不是子串
//此时进入循环，j = 2，比较空格和C，不相等，再进入循环
//j = 1,比较空格和B，不相等，再进入循环
//j = 0，条件不满足，退出循环
//下一次，将从空格后面继续匹配，避免前面比较过的，重复比较
while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j-1];
}
//
if(str1.charAt(i) == str2.charAt(j)) {
j++;
}
if(j == str2.length()) {//找到了 // j = 3 i
return i - j + 1;
}
}
return -1;
}
}
8. 贪心算法
- 贪心算法，就是找最优解，没有最优，只有更优
- 一般都是将数组、序列，按规则排序，然后递归或循环遍历，找到最优解
- 运行效果
- 代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class Test {
public static void main(String[] args) {
//创建广播电台,放入到Map
HashMap> broadcasts = new HashMap>();
//将各个电台放入到broadcasts
HashSet hashSet1 = new HashSet();
hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");
HashSet hashSet2 = new HashSet();
hashSet2.add("广州");hashSet2.add("北京");hashSet2.add("深圳");
HashSet hashSet3 = new HashSet();
hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");
HashSet hashSet4 = new HashSet();
hashSet4.add("上海");hashSet4.add("天津");
HashSet hashSet5 = new HashSet();
hashSet5.add("杭州");hashSet5.add("大连");
//加入到map
broadcasts.put("K1", hashSet1);broadcasts.put("K2", hashSet2);broadcasts.put("K3", hashSet3);broadcasts.put("K4", hashSet4);broadcasts.put("K5", hashSet5);
//allAreas 存放所有的地区
HashSet allAreas = new HashSet();
allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");
//创建ArrayList, 存放选择的电台集合
ArrayList selects = new ArrayList();
//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
HashSet tempSet = new HashSet();
//定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
//如果maxKey 不为null , 则会加入到 selects
String maxKey = null;
while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
//每进行一次while,需要
maxKey = null;
//遍历 broadcasts, 取出对应key
for(String key : broadcasts.keySet()) {
//每进行一次for
tempSet.clear();
//当前这个key能够覆盖的地区
HashSet areas = broadcasts.get(key);
tempSet.addAll(areas);
//求出tempSet 和 allAreas 集合的交集, 交集会赋给 tempSet
tempSet.retainAll(allAreas);
//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多
//就需要重置maxKey
// tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
if(tempSet.size() > 0 &&
(maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){
maxKey = key;
}
}
//maxKey != null, 就应该将maxKey 加入selects
if(maxKey != null) {
selects.add(maxKey);
//将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉
allAreas.removeAll(broadcasts.get(maxKey));
}
}
System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]
}
}
9.最小生成树算法
1. 普里姆（Prim）算法
- 修路问题的本质就是最小生成树（Minimum Cost Spanning Tree）问题，简称MST。
- 给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这就叫最小生成树
- N个顶点，一定有N-1条边
- 并且连通了全部顶点
- 这N-1条边，都在完全图中
- 求最小生成树的算法主要有普里姆算法和克鲁斯卡尔算法
普里姆（Prim）算法
- 求最小生成树，也就是在包含n个顶点的连通图中，找出只有n-1条边就连通了所有顶点的连通子图，也就是极小连通子图
- 算法思路如下：
- 设G=(V,E)是连通图，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
- 若从顶点a开始构建最小生成树，则从集合V中取出顶点a放入集合U中，标记顶点a的visited[a]=1表示已经访问过，如果不是第一次构建，那么选择一个没有访问过的，然后找权值最小的边
- 若集合V中的顶点b与集合U中顶点a之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点a加入集合U中，将边（a，b）加入集合D中，标记visited[b]=1表示b这个顶点也访问过了
- 重复步骤2，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边
代码 package com.yzpnb.test;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
//测试看看图是否创建ok
char[] data = new char[]{'A','B','C','D','E','F','G'};
int verxs = data.length;
//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
int [][]weight=new int[][]{
{10000,5,7,10000,10000,10000,2},
{5,10000,10000,9,10000,10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10000,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000},};
//创建MGraph对象
MGraph graph = new MGraph(verxs);
//创建一个MinTree对象
MinTree minTree = new MinTree();
minTree.createGraph(graph, verxs, data, weight);
//输出
minTree.showGraph(graph);
//测试普利姆算法
minTree.prim(graph, 1);//
}
}
//创建最小生成树->村庄的图
class MinTree {
//创建图的邻接矩阵
public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
int i, j;
for(i = 0; i < verxs; i++) {//顶点
graph.data[i] = data[i];
for(j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
//显示图的邻接矩阵
public void showGraph(MGraph graph) {
for(int[] link: graph.weight) {
System.out.println(Arrays.toString(link));
}
}
//编写prim算法，得到最小生成树
public void prim(MGraph graph, int v) {
//visited[] 标记结点(顶点)是否被访问过
int visited[] = new int[graph.verxs];
//visited[] 默认元素的值都是0, 表示没有访问过
// for(int i =0; i 权值:" + minWeight);
//将当前这个结点标记为已经访问
visited[h2] = 1;
//minWeight 重新设置为最大值 10000
minWeight = 10000;
}
}
}
class MGraph{
int verxs;//图的结点个数
char[] data;//存放结点数据
int[][] weight;//邻接矩阵
public MGraph(int verxs) {
this.verxs = verxs;
data = new char[verxs];
weight = new int[verxs][verxs];
}
}
2. 克鲁斯卡尔（Kruskal）算法
- 克鲁斯卡尔（Kruskal）算法，就是用来求加权连通图的最小生成树的算法
- 按照权值从小到大的顺序选择n-1条边，保证n-1条边不构成回路
- 首先构造一个只含n个顶点的森林，然后依权值从小到大从连通图中选择边加入到森林中，并使森林中不产生回路，直到森林变成一课树为止
如何判断是否构成回路
- 在将
加入到最小生成树R中之后，这几条边的顶点就都有了终点
- C的终点是F。
- D的终点是F。
- E的终点是F。
- F的终点是F。
- 终点
- 就是将加入到最小生成树R中的所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"
- 因此，接下来，虽然
是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将加入最小生成树的话，会形成回路。这就是判断回路的方式
- 我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路
代码 import java.util.Arrays;
public class Test {
//使用 INF 表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//克鲁斯卡尔算法的邻接矩阵
int matrix[][] = {
/*B*/
{ 0, 12, INF, INF, INF, 16, 14},
{ 12, 0, 10, INF, INF, 7, INF},
{ INF, 10, 0, 3, 5, 6, INF},
{ INF, INF, 3, 0, 4, INF, INF},
{ INF, INF, 5, 4, 0, 2, 8},
{ 16, 7, 6, INF, 2, 0, 9},
{ 14, INF, INF, INF, 8, 9, 0}};
//大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.
//创建KruskalCase 对象实例
KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
//输出构建的
kruskalCase.print();
kruskalCase.kruskal();
}
}
class KruskalCase{
private int edgeNum; //边的个数
private char[] vertexs; //顶点数组
private int[][] matrix; //邻接矩阵
//使用 INF 表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
//构造器
public KruskalCase(char[] vertexs, int[][] matrix) {
//初始化顶点数和边的个数
int vlen = vertexs.length;
//初始化顶点, 复制拷贝的方式
this.vertexs = new char[vlen];
for(int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边, 使用的是复制拷贝的方式
this.matrix = new int[vlen][vlen];
for(int i = 0; i < vlen; i++) {
for(int j= 0; j < vlen; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
//统计边的条数
for(int i =0; i < vlen; i++) {
for(int j = i+1; j < vlen; j++) {
if(this.matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
public void kruskal() {
int index = 0; //表示最后结果数组的索引
int[] ends = new int[edgeNum]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
//创建结果数组, 保存最后的最小生成树
EData[] rets = new EData[edgeNum];
//获取图中 所有的边的集合 ， 一共有12边
EData[] edges = getEdges();
System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12
//按照边的权值大小进行排序(从小到大)
sortEdges(edges);
//遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入
for(int i=0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点(起点)
int p1 = getPosition(edges[i].start); //p1=4
//获取到第i条边的第2个顶点
int p2 = getPosition(edges[i].end); //p2 = 5
//获取p1这个顶点在已有最小生成树中的终点
int m = getEnd(ends, p1); //m = 4
//获取p2这个顶点在已有最小生成树中的终点
int n = getEnd(ends, p2); // n = 5
//是否构成回路
if(m != n) { //没有构成回路
ends[m] = n; // 设置m 在"已有最小生成树"中的终点 [0,0,0,0,5,0,0,0,0,0,0,0]
rets[index++] = edges[i]; //有一条边加入到rets数组
}
}
// 。
//统计并打印 "最小生成树", 输出 rets
System.out.println("最小生成树为");
for(int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
//打印邻接矩阵
public void print() {
System.out.println("邻接矩阵为: n");
for(int i = 0; i < vertexs.length; i++) {
for(int j=0; j < vertexs.length; j++) {
System.out.printf("%12d", matrix[i][j]);
}
System.out.println();//换行
}
}
private void sortEdges(EData[] edges) {
for(int i = 0; i < edges.length - 1; i++) {
for(int j = 0; j < edges.length - 1 - i; j++) {
if(edges[j].weight > edges[j+1].weight) {//交换
EData tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
private int getPosition(char ch) {
for(int i = 0; i < vertexs.length; i++) {
if(vertexs[i] == ch) {//找到
return i;
}
}
//找不到,返回-1
return -1;
}
private EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];
for(int i = 0; i < vertexs.length; i++) {
for(int j=i+1; j = " + weight + "]";
}
}
10. 迪杰斯特拉算法（图数据结构的算法）
- 假设A、B、C、D、E、F、G，代表6个村庄，现在有6个邮差，从G出发，分别到ABCDEF六个村庄
- 各个村庄距离用边线表示权，例如A-B距离为5公里
- 如何计算出G村庄到其它各个村庄的最短距离？从其它点出发到各个点最短距离又是多少？
Digkstra迪杰斯特拉算法，是典型的最短路径算法 参考视频：https://www.bilibili.com/video/BV1QK411V7V4?from=search&seid=2723998752402923262&spm_id_from=333.337.0.0
- 用于计算一个结点到其它结点的最短路径，主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止
- 首先我们需要依次遍历所有顶点，第一个是必须是出发顶点，依次将可直接到达的顶点距离记录下来。不可达设置为65535
- 然后遍历剩下的顶点（贪心思想，每次拿到没访问过的，距离出发顶点最短的顶点），将前驱设置好，然后进行判断，如果它到达某个顶点，比记录的距离小，则更新（前驱的距离+自己到目标顶点的距离）
算法思路
- 指定出发顶点G，定义顶点集合V{A,B,C,D,E,F,G},定义G到V中各顶点距离构成的距离集合Dis{d1,d2,d3,d4,di…},Dis集合中记录G点到各顶点距离，自身记作0
- 从Dis中选择最小di，移出Dis集合，同时移出V集合中对应顶点vi，比如A。此时G到A为最短路径
- 更新Dis集合，比较G到V集合中顶点的距离值，与G点通过某个点（假设vi）到目标点（假设P）的距离值（经过某个顶点，到达目标点），保留值小的，同时更新顶点的前驱结点为它经过的点（P的前驱为vi）,保存在一个数组或集合中
- 重复2-3步骤，直到最短路径顶点为目标顶点结束
运行效果和代码
- 运行效果
- 代码
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
//结点
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
//邻接矩阵
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;// 表示不可以连接
matrix[0]=new int[]{N,5,7,N,N,N,2};
matrix[1]=new int[]{5,N,N,9,N,N,3};
matrix[2]=new int[]{7,N,N,N,8,N,N};
matrix[3]=new int[]{N,9,N,N,N,4,N};
matrix[4]=new int[]{N,N,8,N,N,5,4};
matrix[5]=new int[]{N,N,N,4,5,N,6};
matrix[6]=new int[]{2,3,N,N,4,6,N};
//创建 Graph对象
Graph graph = new Graph(vertex, matrix);
//测试, 看看图的邻接矩阵是否ok
graph.showGraph();
//测试迪杰斯特拉算法
graph.digkstra(6);
graph.showDijkstra();
}
}
class Graph{
private char[] vertex;//顶点数组
private int[][] matrix;//领接矩阵
private VisitedVertex visitedVertex;//已经访问过的节点
//构造器
public Graph(char[] vertex,int[][] matrix){
this.vertex = vertex;
this.matrix = matrix;
}
//显示图
public void showGraph(){
for (int[] link: matrix){
System.out.println(Arrays.toString(link));
}
}
public void digkstra(int index){
//获取访问顶点，初始化了需要的集合
this.visitedVertex = new VisitedVertex(vertex.length, index);
update(index);//更新index顶点到周围顶点的距离和前驱顶点
//更新剩余顶点到周围顶点的距离和前驱顶点
for(int j = 1;j < vertex.length;j++){
index = visitedVertex.updateArr();//选择并返回新的访问顶点
update(index);//更新index顶点到周围顶点的距离和前驱顶点
}
}
private void update(int index){
int len = 0;//与周围节点距离
//遍历邻接矩阵，只遍历和index顶点有关的，所以直接遍历index行即可
for(int j = 0;j
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）