冒泡排序
基本介绍
通过对待排序序列从前往后(从下标较小的元素开始) 依次比较相邻元素的值, 若发现逆序, 则使较大的元素从前后移, 就像气泡一样往上冒
图解冒泡排序
冒泡排序.png
根据上图图示可以看出
- 一共进行数组的大小-1次大的循环
- 每一趟排序的次数在减少
V1.0 :为了方便理解 先用代码实现推演版的冒泡排序
/**
* @param
* @return
* @author cx
* @description 冒泡排序基础推演版
* @version v1.0 基础版
**/
public static void sort1(int array[]) {
int temp = 0; // 临时变量
// 第一趟排序 就是将最大的数字 排在最后
for (int i = 0; i < array.length - 1 - 0; i++) {
// 如果前一个数比后一个数大 则发生交换
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
System.out.println("第一趟排序过后数组为:" + Arrays.toString(array));
// 第二趟排序 就是将第二大的数字 排在倒数第二
for (int i = 0; i < array.length - 1 - 1; i++) {
// 如果前一个数比后一个数大 则发生交换
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
System.out.println("第二趟排序过后数组为:" + Arrays.toString(array));
// 第三趟排序 就是将第三大的数字 排在倒数第三
for (int i = 0; i < array.length - 1 - 2; i++) {
// 如果前一个数比后一个数大 则发生交换
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
System.out.println("第三趟排序过后数组为:" + Arrays.toString(array));
// 第四趟排序 就是将第四大的数字 排在倒数第四
for (int i = 0; i < array.length - 1 - 3; i++) {
/ 如果前一个数比后一个数大 则发生交换
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
System.out.println("第四趟排序过后数组为:" + Arrays.toString(array));
// 第五趟排序 就是将第五大的数字 排在倒数第五
for (int i = 0; i < array.length - 1 - 4; i++) {
// 如果前一个数比后一个数大 则发生交换
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
System.out.println("第五趟排序过后数组为:" + Arrays.toString(array));
}
V2.0: 根据上面基础版 可以看出 每次排序代码基本一致 可以在嵌套一个for循环搞定 于是有了如下代码
/**
* @param
* @return
* @author cx
* @description 冒泡排序基础进化版 时间复杂度 O(n^2)
* @version 2.0 基础进化版
**/
public static void sort2(int array[]) {
int temp = 0; // 临时变量
for (int j = 0; j < array.length - 1; j++) { // 排序轮数
// 第j趟排序 就是将最大的数字 排在最后
for (int i = 0; i < array.length - 1 - j; i++) {
// 如果前一个数比后一个数大 则发生交换
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
System.out.println("第" + (j + 1) + "趟排序过后数组为:" + Arrays.toString(array));
}
}
使用数据测试代码 运行如下
int[] array = {3,8, 9, -1, 5,6,7,10};
第1趟排序过后数组为:[3, 8, -1, 5, 6, 7, 9, 10]
第2趟排序过后数组为:[3, -1, 5, 6, 7, 8, 9, 10]
第3趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
第4趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
第5趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
第6趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
第7趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
上面代码已经在第一版的基础上进行了优化, 但是还是存在优化的空间, 就是8个数据,依照此法排序第4轮后就已经是一个有序数组了, 但是代码还是继续按照逻辑执行排序.... 造成了一些不必要的性能浪费 可以优化如下
V3.0
/**
* @param
* @return
* @author cx
* @description 因为在排序过程中 各元素不断接近自己的位置 [如果下一趟比较下来都没有经过交换 则说明序列有序]
* 因此在排序过程中 设立一个flag 标记是否进行过交换 从而减少不必要的比较 达到优化算法的效果
* @version v3.0 优化版
**/
public static void bubbleSort(int array[]) {
int temp = 0 ;
for (int j = 0; j < array.length - 1; j++) { // 循环的趟数
boolean sorted = false; // 提前终止变量
for (int i = 0; i < array.length - 1 - j; i++) { // 交换的次数
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
sorted = true; // 如果一次循环过后 都没有执行交换操作 说明元素已经有序
}
}
System.out.println("第" + (j + 1) + "趟排序过后数组为:" + Arrays.toString(array));
if (!sorted)break; // 如果 sorted变量为false 说明已经不再进行交换 break
}
}
使用数据测试代码 运行如下
int[] array = {3,8, 9, -1, 5,6,7,10};
第1趟排序过后数组为:[3, 8, -1, 5, 6, 7, 9, 10]
第2趟排序过后数组为:[3, -1, 5, 6, 7, 8, 9, 10]
第3趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
第4趟排序过后数组为:[-1, 3, 5, 6, 7, 8, 9, 10]
