算法
一、算法基础
- 时间复杂度：计算排序所花费的最大或者最少时间，以及平均花费时间
- 空间复杂度：计算排序时所需要消耗的临时空间
二、内容
- 冒泡排序
- 选择排序
- 插入排序
三、冒泡排序
算法思路：
1.比较相邻的元素，如果第一个比第二个大，就交换他们
int[] arr = {9,5,7,8,6,4,2,1,0,3};
for(int j = 0 ; j < arr.length - 1 ; j ++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
结果：
[5, 7, 8, 6, 4, 2, 1, 0, 3, 9]
2.继续重复两两比较，直到n轮
//冒泡排序
int[] arr = {9,5,7,8,6,4,2,1,0,3};
//1.比较两个相邻的值，直到把最大或者最小的放到数组的一端
//2.经过n轮重复，将完成最后排序工作
for(int i = 0 ; i < arr.length ; i ++){
for(int j = 0 ; j < arr.length - 1 ; j ++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
注意：只要不断的重复两两比较交换的行为，一定能完成排序
优化：
因为每一轮结束之后，最大的数值都会被移动到数组末尾，是故后续的比较不再需要重复比较已经排
序完成的内容
public class BubbleSort {
public static void main(String[] args) {
//冒泡排序
int[] arr = { 9, 5, 7, 8, 6, 4, 2, 1, 0, 3 };
//1.比较两个相邻的值，直到把最大或者最小的放到数组的一端
//2.经过n轮重复，将完成最后排序工作
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
四、选择排序
算法思路：
- 找到最小值所在的位置
- 要通过循环，不断更替最小值所在的位置
//选择排序
int[] arr = {9,5,7,8,6,4,2,1,0,3};
//1.找到最小的值所在的游标
int minIndex = 0;
//2.循环替换最小值游标
for(int i = 0 ; i < arr.length ; i ++){
//3.最小值所在位置对应的值进行比较，如果比他小，则替换游标
if(arr[i] < arr[minIndex]){
minIndex = i;
}
}
System.out.println("minIndex:" + minIndex);
- 把最小值要放到末排序的数组的首位/末尾
//选择排序
int[] arr = {9,5,7,8,6,4,2,1,0,3};
//1.找到最小的值所在的游标
int minIndex = 0;
//2.循环替换最小值游标
//3.找到未排序的数组的起始位置
int i = 0;
for(int j = 0 ; j < arr.length ; j ++){
//3.最小值所在位置对应的值进行比较，如果比他小，则替换游标
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
System.out.println("minIndex:" + minIndex);
//开始交换位置
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
System.out.println(Arrays.toString(arr));
结果：
minIndex:8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
阶段性结论：
选择排序是一个不稳定的排序算法，一轮排序只换一次
重复以上步骤，直到完成最终排序
//选择排序
int[] arr = {9,5,7,8,6,4,2,1,0,3};
//1.找到最小的值所在的游标
//2.循环替换最小值游标
//3.找到未排序的数组的起始位置
//4.重复这个步骤，直到排序结束
for(int i = 0 ; i < arr.length ; i ++){//i用于记录未排序数组的起始位置，随着轮数增加，往后推
移
int minIndex = i;//最小值的游标位置初值，是随着i的变化而变化的
for(int j = i ; j < arr.length ; j ++){//从i记录的未排序的起始位置开始
//3.最小值所在位置对应的值进行比较，如果比他小，则替换游标
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
System.out.println(Arrays.toString(arr));
五、插入排序
算法思路：
- 从第2位开始倒序排列
- 只要前面比我大，我就和他换位置
- 除非前面没有数，否则我就不会停
//插入排序
int[] arr = {1,2,3,5,6,7,4};
for(int j = arr.length-1 ; j > 0 && arr[j] < arr[j-1] ; j --){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
System.out.println(Arrays.toString(arr));
结果：
[1, 2, 3, 4, 5, 6, 7]
重复以上过程，直到排序完成
public class InsertSort {
public static void main(String[] args) {
//插入排序
int[] arr = {9,8,7,6,5,4,3,2,1,0};
for(int i = 1 ; i < arr.length ; i ++{
for(int j = i ; j > 0 && arr[j] < arr[j-1] ; j --){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}
六、作业
需求：
一个系统《学生成绩管理系统》
1.启动程序，控制台有一个选项列表
2.学生学号和成绩要一一对应
3.学生成绩录入后自然排序
4.学号不可重复，重复学号录入成绩，成绩自然覆盖
5.查看成绩是自然排序后的成绩列表
Scanner scanner = new Scanner(System.in);
System.out.println("欢迎使用学生管理系统。。。。。");
String[] studentCodeArr = new String[0];
double[] studentScoreArr = new double[0];
boolean flag = true;
while(flag){
System.out.print("1.录入学生学号 2.录入学生成绩 3.查看学生成绩 4.退出");
int opt = scanner.nextInt();
switch(opt){
case 1:
break;
case 2:
break;
case 3:
break;
case 4:
flag = false;
System.out.println("欢迎再次使用！");
break;
}
}