算法——algorithm
递归——recursion——俄罗斯套娃
递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。
递归需要遵守的重要规则
- 执行一个方法时，就创建一个新的受保护的独立空间(栈帧空间)
- 方法的局部变量是独立的，不会相互影响, 比如n变量；如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
- 递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了。
- 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
场景
- 打印问题
- 阶乘问题
- 走迷宫回溯
- 8皇后问题
- 球和篮子的问题
- 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等
递归示例
递归调用方法图解分析
递归.png
代码示例
public class Recursion {
//递归打印
public static void recursionPrint(int n) {
if (n > 1) {
recursionPrint(n - 1);
}
System.out.println("n=" + n);
}
/**
* n=1
* n=2
* n=3
* n=4
* n=5
*/
//递归实现阶乘
public static int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);//5*4*3*2*1
} else {
return 1;
}
}
//阶乘结果为：120
public static void main(String[] args) {
//recursionPrint(5);
//阶乘结果为：120
System.out.println("阶乘结果为："+factorial(5));
}
}
递归回溯走迷宫代码示例
注：在没有使用算法求最短路径时，最短路径的选择与我们代码中行走的策略有关。
代码示例
/**
* 迷宫原始图：
* 1 1 1 1 1 1 1 1 1 1
* 1 0 0 0 0 0 0 0 0 1
* 1 0 0 0 0 0 0 0 0 1
* 1 0 0 0 0 0 0 0 0 1
* 1 0 1 0 1 1 1 1 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 1 1 1 1 1 1 1 1 1
* --------------------------------
* 走出迷宫路径：
* 1 1 1 1 1 1 1 1 1 1
* 1 2 0 0 0 0 0 0 0 1
* 1 2 0 0 0 0 0 0 0 1
* 1 2 2 2 0 0 0 0 0 1
* 1 3 1 2 1 1 1 1 0 1
* 1 3 1 2 0 0 0 0 0 1
* 1 3 1 2 0 0 0 0 0 1
* 1 3 1 2 0 0 0 0 0 1
* 1 3 1 2 2 2 2 2 2 1
* 1 1 1 1 1 1 1 1 1 1
* --------------------------------
* 走出迷宫最短路径：
* 1 1 1 1 1 1 1 1 1 1
* 1 2 2 2 2 2 2 2 2 1
* 1 0 0 0 0 0 0 0 2 1
* 1 0 0 0 0 0 0 0 2 1
* 1 0 1 0 1 1 1 1 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 1 1 1 1 1 1 1 1 1
*/
public class Maze {
public static void main(String[] args) {
int[][] maze = buildMaze();
System.out.println("走出迷宫路径：");
walkMaze(maze, 1, 1);
// System.out.println("走出迷宫最短路径：");
// walkMazeShortcut(maze, 1, 1);
printMaze(maze);
}
/**
* 约定大于配置
* 创建二维数组模拟迷宫
* 使用1表示墙，四周置墙
*/
public static int[][] buildMaze() {
int[][] maze = new int[10][10];
for (int i = 0; i < maze.length; i++) {
//对第0和第9行设置1表示墙
maze[0][i] = 1;
maze[9][i] = 1;
//对第0和第9列设置1表示墙
maze[i][0] = 1;
maze[i][9] = 1;
//设置其他障碍
if (3 < i) {
maze[i][2] = 1;
}
if (i > 3) {
maze[4][i] = 1;
if (i == 8) {
maze[4][i] = 0;
}
}
}
System.out.println("迷宫原始图：");
printMaze(maze);
System.out.println("--------------------------------");
return maze;
}
/**
* 使用递归回溯找路
*
* @param maze 地图
* @param //x坐标
* @param //y坐标
* @return 找到路返回true，否则false
* x,y表示地图位置坐标，最开始位置置为(1,1)
* 约定，从坐标1,1走到8,8表示走出迷宫
* //注意因为我们定义的数组是10,10,最外层的坐标9,9已经被标记为墙，则应该设置终点为8,8才能达到，否则永远都走不通
* //值1表示墙，2表示走完迷宫的路，3表示走不通 0表示没走过
* 寻路策略：先向下->右->上->左
*/
public static boolean walkMaze(int[][] maze, int x, int y) {
if (maze[8][8] == 2) {
return true;
} else {
if (maze[x][y] == 0) {
maze[x][y] = 2;
//向下找,行增加，x+1
if (walkMaze(maze, x + 1, y)) {
return true;
//右
} else if (walkMaze(maze, x, y + 1)) {
return true;
//上
} else if (walkMaze(maze, x - 1, y)) {
return true;
//左
} else if (walkMaze(maze, x, y - 1)) {
return true;
} else {
//走不通
maze[x][y] = 3;
return false;
}
} else {
//不为0的情况
return false;
}
}
}
//修改策略达到最短路径
public static boolean walkMazeShortcut(int[][] maze, int x, int y) {
if (maze[8][8] == 2) {
return true;
} else {
if (maze[x][y] == 0) {
maze[x][y] = 2;
//右
if (walkMazeShortcut(maze, x, y + 1)) {
return true;
//向下找,行增加，x+1
} else if (walkMazeShortcut(maze, x + 1, y)) {
return true;
//上
} else if (walkMazeShortcut(maze, x - 1, y)) {
return true;
//左
} else if (walkMazeShortcut(maze, x, y - 1)) {
return true;
} else {
//走不通
maze[x][y] = 3;
return false;
}
} else {
//不为0的情况
return false;
}
}
}
public static void printMaze(int[][] maze) {
for (int[] intRow : maze) {
for (int column : intRow) {
System.out.printf("%d\t", column);
}
System.out.println();
}
}
}
八皇后问题——回溯算法
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法（一共有92种）。
八皇后.png
思路分析
八皇后2.png
说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
代码实现——本质上就是暴力匹配
/**
* 0 4 7 5 2 6 1 3
* 0 5 7 2 6 3 1 4
* 0 6 3 5 7 1 4 2
* 0 6 4 7 1 3 5 2
* 1 3 5 7 2 0 6 4
* 1 4 6 0 2 7 5 3
* 1 4 6 3 0 7 5 2
* 1 5 0 6 3 7 2 4
* 1 5 7 2 0 3 6 4
* 1 6 2 5 7 4 0 3
* 1 6 4 7 0 3 5 2
* 1 7 5 0 2 4 6 3
* 2 0 6 4 7 1 3 5
* 2 4 1 7 0 6 3 5
* 2 4 1 7 5 3 6 0
* 2 4 6 0 3 1 7 5
* 2 4 7 3 0 6 1 5
* 2 5 1 4 7 0 6 3
* 2 5 1 6 0 3 7 4
* 2 5 1 6 4 0 7 3
* 2 5 3 0 7 4 6 1
* 2 5 3 1 7 4 6 0
* 2 5 7 0 3 6 4 1
* 2 5 7 0 4 6 1 3
* 2 5 7 1 3 0 6 4
* 2 6 1 7 4 0 3 5
* 2 6 1 7 5 3 0 4
* 2 7 3 6 0 5 1 4
* 3 0 4 7 1 6 2 5
* 3 0 4 7 5 2 6 1
* 3 1 4 7 5 0 2 6
* 3 1 6 2 5 7 0 4
* 3 1 6 2 5 7 4 0
* 3 1 6 4 0 7 5 2
* 3 1 7 4 6 0 2 5
* 3 1 7 5 0 2 4 6
* 3 5 0 4 1 7 2 6
* 3 5 7 1 6 0 2 4
* 3 5 7 2 0 6 4 1
* 3 6 0 7 4 1 5 2
* 3 6 2 7 1 4 0 5
* 3 6 4 1 5 0 2 7
* 3 6 4 2 0 5 7 1
* 3 7 0 2 5 1 6 4
* 3 7 0 4 6 1 5 2
* 3 7 4 2 0 6 1 5
* 4 0 3 5 7 1 6 2
* 4 0 7 3 1 6 2 5
* 4 0 7 5 2 6 1 3
* 4 1 3 5 7 2 0 6
* 4 1 3 6 2 7 5 0
* 4 1 5 0 6 3 7 2
* 4 1 7 0 3 6 2 5
* 4 2 0 5 7 1 3 6
* 4 2 0 6 1 7 5 3
* 4 2 7 3 6 0 5 1
* 4 6 0 2 7 5 3 1
* 4 6 0 3 1 7 5 2
* 4 6 1 3 7 0 2 5
* 4 6 1 5 2 0 3 7
* 4 6 1 5 2 0 7 3
* 4 6 3 0 2 7 5 1
* 4 7 3 0 2 5 1 6
* 4 7 3 0 6 1 5 2
* 5 0 4 1 7 2 6 3
* 5 1 6 0 2 4 7 3
* 5 1 6 0 3 7 4 2
* 5 2 0 6 4 7 1 3
* 5 2 0 7 3 1 6 4
* 5 2 0 7 4 1 3 6
* 5 2 4 6 0 3 1 7
* 5 2 4 7 0 3 1 6
* 5 2 6 1 3 7 0 4
* 5 2 6 1 7 4 0 3
* 5 2 6 3 0 7 1 4
* 5 3 0 4 7 1 6 2
* 5 3 1 7 4 6 0 2
* 5 3 6 0 2 4 1 7
* 5 3 6 0 7 1 4 2
* 5 7 1 3 0 6 4 2
* 6 0 2 7 5 3 1 4
* 6 1 3 0 7 4 2 5
* 6 1 5 2 0 3 7 4
* 6 2 0 5 7 4 1 3
* 6 2 7 1 4 0 5 3
* 6 3 1 4 7 0 2 5
* 6 3 1 7 5 0 2 4
* 6 4 2 0 5 7 1 3
* 7 1 3 0 6 4 2 5
* 7 1 4 2 0 6 3 5
* 7 2 0 5 1 4 6 3
* 7 3 0 2 5 1 6 4
* 一共有92种摆放方法
* 一共有92种摆放方法一共判断了15720次
*/
public class Queen {
public static void main(String[] args) {
Queen queen = new Queen(8);
queen.showQueenMagic();
System.out.printf("一共有%d种摆放方法", queen.getCount());//92
System.out.printf("一共判断了%d次",queen.getJudgeCount());//15720
}
//表示玩的是几个皇后
private int max;
////对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
private int[] arr;
//累计摆放方法数
private int count;
//一共判断了多少次
private int judgeCount;
public int getJudgeCount() {
return judgeCount;
}
public int getCount() {
return count;
}
public Queen(int max) {
this.max = max;
arr = new int[max];
}
public void showQueenMagic() {
//从第1个皇后开始放置
check(0);
}
/**
* n表示放置第n个皇后
* check是每一次递归时，进入check方法都会有 for (int i = 0; i < max; i++)循环，因此会有回溯
* 回溯就在于我们每次都把符合排列的八皇后摆法打印出来，然后程序继续往下走，当第8个皇后摆放完毕到max时已经没有其他的成功结果后，就会回溯到第7个皇后的下一个摆放位置，
* 继续往下深入，当第7个皇后也摆放测试到max位置结束后，就会回溯到第6个皇后摆放位置的下一个，一直到第一个皇后从第1位摆放到第max位
* @param n
*/
public void check(int n) {
//表示进来判断是n如果等于max比如8，则表示目前进来判断的是第九个皇后
//也就是说第八个皇后已经放置好了
if (n == max) {
print();
count++;
return;
}
//依次在0到max中摆放皇后，判断是否冲突
for (int i = 0; i < max; i++) {
//表示对第n个皇后的放置位置从0开始放置，并进行校验位置放置是否满足条件
arr[n] = i;
if (judgePlaceIsOk(n)) {
//满足则继续摆放第n+1个皇后
check(n + 1);
}
//不满足则进入i++继续判断，继续往下摆放
}
}
//n表示放置第n个皇后,他放置的位置与之前的0到n-1位皇后的位置进行比对是否冲突
public boolean judgePlaceIsOk(int n) {
judgeCount++;
for (int i = 0; i < n; i++) {
//斜率k=(y1-y2)/(x1-x2) ，而当两个点在同一个斜线上时k=1，这时候得出(y1-y2) = (x1-x2)
//arr[i] == arr[n]表示在同一列上
//Math.abs(i - n) == Math.abs(arr[i] - arr[n]) 表示在同一斜线上
//同一行不需要对比，因为我们上面的for循环只在不同行上，因此一定不会在同一行上
if (arr[i] == arr[n] || Math.abs(i - n) == Math.abs(arr[i] - arr[n])) {
return false;
}
}
return true;
}
private void print() {
for (int q : arr) {
System.out.printf("%d\t", q);
}
System.out.println();
}
}
扩展：
行差等于列差，表示45°，说明在同一个斜向上。
斜率k=(y1-y2)/(x1-x2) ，而当两个点在同一个斜线上时k=1，这时候得出(y1-y2) = (x1-x2) 。
斜率k=1时的直线： y=x+b，线与x轴夹角为+45度。
排序——Sort Algorithm
排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。
排序的分类
- 内部排序——内存
指将需要处理的所有数据都加载�到内部存储器中进行排序。
- 外部排序——借助外存
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。
常见的排序算法分类
排序.png
衡量一个程序(算法)执行时间的两种方法
事后统计的方法
这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。
事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优.
时间复杂度——Ｏ( f(n) ) —— Time Complexity
时间频度——T(N)
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为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²)。
时间复杂度.png
计算时间复杂度的方法
用常数1代替运行时间中的所有加法常数（ 忽略常数项） T(n)=3n²+7n+6 => T(n)=3n²+7n+1
修改后的运行次数函数中，只保留最高阶项 （忽略低次项） T(n)=3n²+7n+1 => T(n) = 3n²
去除最高阶项的系数（忽略系数） T(n) = 3n² => T(n) = n² => O(n²)
常见的时间复杂度(10种)
- 常数阶O(1)
- 对数阶O(log2^n)
- 线性阶O(n)
- 线性对数阶O(nlog2^n)
- 平方阶O(n^2)
- 立方阶O(n^3)
- k次方阶O(n^k)
- 指数阶O(2^n)
- n的阶乘Ο(n!)
- n的指数阶O(n^n)
常见的算法时间复杂度由小到大排列
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(n^k) ＜Ο(2^n) ＜Ο(n!)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低.
时间复杂度2.png
对数阶O(log2^n)
对数就是指数的相反操作。
x= loga^n （a>0,a≠1）,x叫做以a为底的n的对数，a为底数，n为真数。
我们要求 log2^1024，其实就是求2的几次方=1024，也就是10。
或者，log22=1,我们可以这样计算：log21024=log22+log22+log22+log22+log22+log22+log22+log22+log22+log22=
1+1+1+1+1+1+1+1+1+1=10
log327=3，因为33=27。注意下面i=i*3,则O(log3^n)
对数阶.png
扩展
线性阶O(n)
单层的for循环就是线性阶。
线性阶.png
线性对数阶O(nlogn)
时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
线性对数阶.png
平方阶O(n²)
两层for循环嵌套就是平方阶
平方阶.png
平均时间复杂度和最坏时间复杂度
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致，和算法有关.
时间复杂度3.png
空间复杂度——Space Complexity
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法、基数排序就属于这种情况。
在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
冒泡排序——Bubble Sort——O(n^2)
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化：
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在
排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。
public class BubbleSort {
public static void main(String[] args) {
int[] array = {1, 15, -2, 67, 100, 3, 29};
// int[] array = {1,2,3,46,5};//[1, 2, 3, 5, 46]
System.out.println("排序前：");
System.out.println(Arrays.toString(array));
bubbleSort(array);
System.out.println("排序后：");
System.out.println(Arrays.toString(array));
//[-2, 1, 3, 15, 29, 67, 100]
//测试十万数据冒泡排序耗时
int[] arrTest = new int[10_0000];
for (int i = 0; i < arrTest.length; i++) {
//Math.random()产生0-1之间的随机数，再乘以一百万，产生0-十万之间的随机数，
// 注意要对(Math.random()*10_0000)加括号再强转int类型，否则得到的永远是0
arrTest[i] = (int)(Math.random()*10_0000);
}
long start = System.currentTimeMillis();
bubbleSort(arrTest);
long end = System.currentTimeMillis();
System.out.println("十万数据冒泡排序耗时:"+(end-start));
/**
* 排序前：
* [1, 15, -2, 67, 100, 3, 29]
* 排序后：
* [-2, 1, 3, 15, 29, 67, 100]
* 十万数据冒泡排序耗时:13658
*/
}
/**
* 冒泡排序：时间复杂度 O(n^2)
* @param array
*/
public static void bubbleSort(int[] array) {
//当新的一轮冒泡没有发生交换时我们认为以及排序好了，跳出循环
boolean swapFlag = false;
//一共循环rray.length-1次，因为是两个数比较，最后一次只有一个数，不需要
for (int j = 0; j < array.length-1; j++) {
/**
* 从冒泡排序的规律上看，第一次比较array.length - 1次,
* 第二次一共比较了array.length - 1 -1次，因为最后一个数已经通过冒泡到了最后一个位置，
* 无需再与最后一个数比较，因此减少了一次比较的过程，以此类推，则每次冒泡都减少了j次比较，
* j从0开始。
*/
for (int i = 0; i < array.length - j - 1; i++) {
//如果要从大到小排序则改变比较规则即可
if (array[i] > array[i + 1]) {
int temp = 0;
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapFlag = true;
}
}
if (!swapFlag) {
break;
} else {
//重置swapFlag，进行新一轮的判断
swapFlag = false;
}
}
}
//注意这里不能提取方法，因为是值传递，数组元素不会发生改变，如果要提取方法则要直接传入数组array进行操作才行，数组才是引用传递
private static void swap(int x, int y) {
int temp = 0;
temp = x;
x = y;
y = temp;
}
}
选择排序——Select Sort——O(n^2)
选择排序，顾名思义，如果我们是按从小到大对数组进行排序，那么从数组第一位开始遍历到最后一个元素，从中选择出最小的元素与第一位进行交换，这样第一位就得到了最小的那个数；第二位就是从第二个元素开始比较，选出最小的放在第二位，以此类推。
选择排序思想:
选择排序（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次，得到一个按排序码从小到大排列的有序序列。
image.png
image.png
//选择排序
public class SelectSort {
public static void main(String[] args) {
int [] arr = {101, 34, 119, 1, -1, 90, 123};
//创建要给80000个的随机的数组
// int[] arr = new int[80000];
// for (int i = 0; i < 80000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
// Date data1 = new Date();
// SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
// String date1Str = simpleDateFormat.format(data1);
// System.out.println("排序前的时间是=" + date1Str);
selectSort(arr);
// Date data2 = new Date();
// String date2Str = simpleDateFormat.format(data2);
// System.out.println("排序前的时间是=" + date2Str);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
//选择排序
public static void selectSort(int[] arr) {
//在推导的过程，我们发现了规律，因此，可以使用for来解决
//选择排序时间复杂度是 O(n^2)
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]; // 重置min
minIndex = j; // 重置minIndex
}
}
// 将最小值与arr[i]交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
/**
* 排序前
* [101, 34, 119, 1, -1, 90, 123]
* 排序后
* [-1, 1, 34, 90, 101, 119, 123]
*/
}
其他
解决从其他地方拿到的文件编码有问题导致的乱码问题处理方法
解决方法就是用记事本打开该文件，再另存为一份新的文件，修改保存的文件格式，比如修改为UTF-8编码格式，再把该文件拷贝到想要的项目中或者复制过来即可。
编码问题.png
网友评论