算法描述
- 依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
思路描述
第一趟排序将第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位。依次类推，每一趟比较次数减少1。
......
共需要n-1趟
排序效果如下图：
素材来源于网络收集
Java 代码实现
import java.util.Arrays;
/**
* @Author: Haotian
* @Date: 2019/11/19 15:43
* @Description: 冒泡排序
*/
public class Sort {
public static void main(String[] args) throws MyException {
//测试排序
int[] array = {2, 18, 1, 19, 16, 20};
bubbleSort( array );
}
/**
* 冒泡排序
*
* @param array 待排序数组
* @throws MyException 自定义的异常类
*/
private static void bubbleSort(int[] array) throws MyException {
//边界判断，保证程序健壮性
if (array == null || array.length == 0) {
throw new MyException( "the array is null or no element..." );
}
if (array.length == 1) {
return;
}
//冒泡开始
for (int i = 0; i < array.length; i++) {
// 若为 true，则表示此次循环没有进行交换，即待排序列已经有序，排序已然完成
boolean success = true;
//每次循环后最后一个数不再参与下一次排序，所以减一
for (int j = 0; j < array.length - i - 1; j++) {
//前一位数大于后一位数才进行交换
if (array[j] > array[j + 1]) {
//临时变量接收较大数
int temp = array[j];
//大变小
array[j] = array[j + 1];
//小变大
array[j + 1] = temp;
success = false;
}
}
//排序完成即可退出循环
if (success) {
break;
}
//控制台打印查看
System.out.println( "第" + (i + 1) + "轮后: " + Arrays.toString( array ) );
}
}
/**
* 自定义异常用于处理
*/
public static class MyException extends Exception {
public MyException(String message) {
super( message );
}
}
}
复杂度
-
时间复杂度：
两层循环，第1次遍历n次(n个元素)，第二次遍历n-1次，... 依次类推。因此，表达式如下：
时间复杂度
-
空间复杂度：
没有利用新的数组来帮助完成排序算法，因此认为其空间复杂度为O(1)
