基础算法的动态视图
关键点
-
在代码上要关注两个for循环的本质是什么
-
结合动图分析代码结构
/**
* 冒泡排序
* @param array
*/
public static void bubbleSort(int[] array){
if(array.length == 0){
return;
}
for(int i=0;i<array.length;i++){
// 每一次都减少i个元素
for(int j=0;j<array.length-1-i;j++){
// 若相邻的两个元素比较后，前一个元素大于后一个元素，则交换位置。
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
//Array工具类直接用sort方法比较香
冒泡排序实例：
package com.array;
import java.util.Arrays;
/**
* 测试冒泡排序
* @author Lucifer
*/
public class TestBubbleSort {
public static void main(String[] args) {
int[] values = {3,1,6,2,9,0,7,4,5,8};
int temp = 0;
for (int j = 0; j < values.length -1; j++){
boolean flag = true;
for (int i = 0; i < values.length - 1 - j; i++){
//因为到最后以为索引是9如果写判断会出现索引10就会出现报错
if (values[i] > values[i + 1]){
temp = values[i];
values[i] = values[i + 1];
values[i + 1] = temp;
flag = false;
}
// System.out.println(Arrays.toString(values));
}
/*如果不再发生交换，说明后面也不会发送交换了。直接跳出不在执行循环*/
if (flag){
System.out.println("Finish");
break;
}
System.out.println("######");
}
System.out.println(Arrays.toString(values));
}
}
/*
一次for循环只能找到最大的9并且放到后面，前面的数不会进行再次排序判断。
所以外层要在套一层for循环去实现前面的数的排序
事实上在外层循环也就是j = 5的时候排序已经排好了。
后面的进行的循环是多余的，可以进行优化
优化方法：
1.在每次大循环的时候建一个布尔变量
2.利用布尔量进行判断
1.如果在小循环中数值还发生交换，认为没有排序好，继续执行外层循环
2.如果在小循环中数值不发生交换了，认为排序好了，不再执行外层循环---break
*/