写在前边的话：今天记录一下关于算法中冒泡排序的一些理解和心得。
主要分为以下3个方面介绍
- 冒泡排序的思想
- 分析
- 标准实现方式
- 优化
- 时间复杂度
冒泡排序的思想
1：给定一个具有N位数据的数组,从起始位置依次与其后一位数据进行 “两两比较”，“若当前值比其后一位值要小(大)，则交换2者的数据”。
2：“继续从下一位开始此操作”，直至计算出最小(大)值(这样一趟下来，必能找出一个最小(大)值)。
3：重复上述操作N-1次，直到数组中所有数据满足降(升)序为止。
分析
- 冒泡排序的话是 两两比较，即当前值与其下一位。
- swap操作。
- swap操作结束之后，继续移动指针到下一位，重复前两次操作。
- 有N个数据，就需要执行N-1次循环。因为一趟循环走下来，只能确立一个最小(大)值。
标准实现方式
public static void main(String[] args){
Integer[] array1 = createRandomArray();
Integer[] array3 = Arrays.copyOf(array1, array1.length);
bubbleSort2(array1);
Util.print(array1);
test(array3);
Util.print(array3);
}
/**
* 冒泡排序
* @param src 数据源
*/
private static void bubbleSort2(Integer[] src){
Util.checkSrc(src);
for(int end = 0; end < src.length - 1; end++){ //n-1次循环
for(int j = 0; j < src.length - 1 - end; j++){ //只比较从0开始，到第n-end数
if(src[j] > src[j + 1]){ //两两比较(不直接与最后一个比较)
int temp = src[j];
src[j] = src[j + 1];
src[j + 1] = temp;
}
}
}
｝
/**
* 对数器(采用系统提供的排序算法，绝对正确)
* @param src 数据源
*/
private static void test(Integer[] src){
Arrays.sort(src);
}
/**
* 返回随机创建的一维数组
*/
private static Integer[] createRandomArray(){
int count = 20;
int base = 100;
Integer[] arrays = new Integer[count];
for(int i = 0; i < arrays.length; i++){
arrays[i] = (int)(Math.random() * base);
}
return arrays;
}
查看下log
Result:8---13---20---28---31---36---45---50---51---51---54---57---58---60---65---71---76---89---90---97
Result:8---13---20---28---31---36---45---50---51---51---54---57---58---60---65---71---76---89---90---97
优化
/**
* 冒泡排序(优化冒泡-1)
* @param src 数据源
*/
private static void bubbleSort2_1(Integer[] src){
Util.checkSrc(src);
//作用:如果内部循环(swap循环)执行完事之后,再判断是否需要执行下次循环。
//1:此值为false,表明 该序列已然是有序数列,不再继续后续操作,此方法执行结束(eg:2,4,5,6,10)。
//2:此值为true,表明 当前循环执行了swap操作,此次循环操作不能保证 该序列是有序的,需要再次循环判断一下(eg:3,1,2,5,6)。
boolean flag = true; //方法是否需要继续执行标记
for(int i = 0; i < src.length - 1 && flag; i++){ //n-1次循环
flag = false;
for(int j = 0; j < src.length - 1 - i; j++){ //只比较从0开始，到第n-end数
if(src[j] > src[j + 1]){ //两两比较
int temp = src[j];
src[j] = src[j + 1];
src[j + 1] = temp;
flag = true;
}
if(!flag){
break;
}
Util.print(src, "Sort2-1--第:" + i + "循环" + "--j:" + j + "---");
}
}
}
public static void main(String[] args){
//Integer[] array1 = createRandomArray();
Integer[] array1 = {3, 1, 2, 6, 7, 20};
Integer[] array2 = Arrays.copyOf(array1, array1.length);
Integer[] array3 = Arrays.copyOf(array1, array1.length);
System.out.println("数据源：" + Arrays.toString(array1) + "---------------------------------");
bubbleSort2(array1);
Util.print(array1 , "Sort-Nomal");
System.out.println("------------------------------------------------------");
bubbleSort2_1(array2);
Util.print(array2 , "Sort-Better");
System.out.println("------------------------------------------------------");
test(array3);
Util.print(array3, "Result");
}
查看log
数据源：[3, 1, 2, 6, 7, 20]---------------------------------
Sort2--第:0循环--j:0---:1---3---2---6---7---20
Sort2--第:0循环--j:1---:1---2---3---6---7---20
Sort2--第:0循环--j:2---:1---2---3---6---7---20
Sort2--第:0循环--j:3---:1---2---3---6---7---20
Sort2--第:0循环--j:4---:1---2---3---6---7---20
Sort2--第:1循环--j:0---:1---2---3---6---7---20
Sort2--第:1循环--j:1---:1---2---3---6---7---20
Sort2--第:1循环--j:2---:1---2---3---6---7---20
Sort2--第:1循环--j:3---:1---2---3---6---7---20
Sort2--第:2循环--j:0---:1---2---3---6---7---20
Sort2--第:2循环--j:1---:1---2---3---6---7---20
Sort2--第:2循环--j:2---:1---2---3---6---7---20
Sort2--第:3循环--j:0---:1---2---3---6---7---20
Sort2--第:3循环--j:1---:1---2---3---6---7---20
Sort2--第:4循环--j:0---:1---2---3---6---7---20
Sort-Nomal:1---2---3---6---7---20
------------------------------------------------------
Sort2-1--第:0循环--j:0---:1---3---2---6---7---20
Sort2-1--第:0循环--j:1---:1---2---3---6---7---20
Sort2-1--第:0循环--j:2---:1---2---3---6---7---20
Sort2-1--第:0循环--j:3---:1---2---3---6---7---20
Sort2-1--第:0循环--j:4---:1---2---3---6---7---20
Sort2-1--第:1循环--j:0---:1---2---3---6---7---20
Sort2-1--第:1循环--j:1---:1---2---3---6---7---20
Sort2-1--第:1循环--j:2---:1---2---3---6---7---20
Sort2-1--第:1循环--j:3---:1---2---3---6---7---20
Sort-Better:1---2---3---6---7---20
------------------------------------------------------
Result:1---2---3---6---7---20
时间复杂度
结论:O(n^2)
分析:
假如有n=5个数要排序，总共需要执行n-1=4次循环操作
第1次：需要比较n-1=4次
第2次：需要比较n-2=3次
第3次：需要比较n-3=2次
第4次：需要比较n-4=1次
总共执行的次数是多少呢？
我们发现这个有点像求 “1+2+3+...+100”，这不就是等差数列吗？
那么整个执行的次数应该为:(n-1+n-2+...+2+1)=n^2/2
所以“冒泡排序的时间复杂度为 O(n^2)”
