定义：每一趟依次比较相邻的两个数，将小数放在前面，大数放在后面，直到一趟只剩下一个元素。
名字的由来：因为越小的元素会经由交换慢慢"浮"到数列的顶端。
基本思路
- 比较相邻的元素，如果第一个大于第二个，就交换它们的位置；
- 从开始第一对到最后一对，对每一对相邻的元素做同样的工作，这样在最后的元素应该是最大的元素；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤 1~3，直到排序完成。
运行轨迹
冒泡排序运行轨迹
代码实现
根据排序算法类的模板实现冒泡排序（提醒：点蓝字查看详情）
/**
* 冒泡排序
*
* @author TinyDolphin
* 2017/11/2 10:04.
*/
public class Bubble {
/**
* 排序实现
*
* @param arr 待排序数组
*/
public static void sort(Comparable[] arr) {
int length = arr.length;
for (int indexI = 0; indexI < length; indexI++) {
for (int indexJ = 0; indexJ < length - 1 - indexI; indexJ++) {
if (less(arr[indexJ + 1], arr[indexJ])) {
exch(arr, indexJ + 1, indexJ);
}
}
}
}
/**
* 比较两个元素的大小
*
* @param comparableA 待比较元素A
* @param comparableB 待比较元素B
* @return 若 A < B,返回 true,否则返回 false
*/
private static boolean less(Comparable comparableA, Comparable comparableB) {
return comparableA.compareTo(comparableB) < 0;
}
/**
* 将两个元素交换位置
*
* @param arr 待交换元素所在的数组
* @param indexI 第一个元素索引
* @param indexJ 第二个元素索引
*/
private static void exch(Comparable[] arr, int indexI, int indexJ) {
Comparable temp = arr[indexI];
arr[indexI] = arr[indexJ];
arr[indexJ] = temp;
}
/**
* 打印数组的内容
*
* @param arr 待打印的数组
*/
private static void show(Comparable[] arr) {
for (int index = 0; index < arr.length; index++) {
System.out.print(arr[index] + " ");
}
System.out.println();
}
/**
* 判断数组是否有序
*
* @param arr 待判断数组
* @return 若数组有序，返回 true，否则返回 false
*/
public static boolean isSort(Comparable[] arr) {
for (int index = 1; index < arr.length; index++) {
if (less(arr[index], arr[index - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[]{14, 23, 21, 17, 20, 49, 24, 77, 54, 47, 31};
sort(arr);
assert isSort(arr);
show(arr); //14 17 20 21 23 24 31 47 49 54 77
}
}
性能分析
其外层循环执行 N 次。内层循环最多的时候执行 N - 1 次，最少的时候执行1次，平均执行 (N+1)/2次。
所以循环体内的比较交换约执行 (N)(N + 1) / 2 = (N^2 - N)/2（其中N^2 表示N的平方）。按照计算复杂度的原则，去掉常数，去掉最高项系数，其复杂度为O(N^2)。
最佳情况 O(N) 、最差情况 O(N^2)、平均情况 O(n^2)
优化方案
第一种：记录每趟排序中最后一次进行交换的位置，作为下一趟比较结束的位置。
优化之后算法如下：
public static void sortPlus(Comparable[] arr) {
int indexI = arr.length - 1; // 第一趟结束的位置
while (indexI > 0) {
int pos = 0; // 由于记录交换的位置
for (int indexJ = 0; indexJ < indexI; indexJ++) {
if (less(arr[indexJ + 1], arr[indexJ])) {
pos = indexJ; // 记录最后一次交换的位置
exch(arr, indexJ + 1, indexJ);
}
}
indexI = pos; // 将 pos 作为下一趟结束的位置
}
}
第二种：传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们考虑利用在每趟排序中进行正反两向冒泡的方法，一次得到两个最终值（最大值 & 最小值），从而使排序趟数几乎减少一半。
优化之后算法如下：
public static void sortPlus2(Comparable[] arr) {
int low = 0;
int high = arr.length - 1; // 第一趟结束的位置
int indexI;
while (low < high) {
// 正向冒泡，找出最大值
for (indexI = low; indexI < high; ++indexI) {
if (less(arr[indexI + 1], arr[indexI])) {
exch(arr, indexI + 1, indexI);
}
}
--high; // 修改 low 值，前移一位
// 反向冒泡，找出最小值
for (indexI = high; indexI > low; --indexI) {
if (less(arr[indexI], arr[indexI - 1])) {
exch(arr, indexI, indexI - 1);
}
}
++low; // 修改 low 值，后移一位
}
}
三种方法耗时对比：
public static void main(String[] args) {
int length = 8000;// 万以下的级别
Integer[] arr = new Integer[length];
Integer[] arr2 = new Integer[length];
Integer[] arr3 = new Integer[length];
for (int index = 0; index < length; index++) {
arr[index] = new Random().nextInt(length) + 1;
}
//高效复制数组的方法
System.arraycopy(arr, 0, arr2, 0, arr.length);
System.arraycopy(arr, 0, arr3, 0, arr.length);
long start = System.currentTimeMillis();
sort(arr);
long end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
assert isSort(arr);
start = System.currentTimeMillis();
sortPlus(arr2);
end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
assert isSort(arr2);
start = System.currentTimeMillis();
sortPlus2(arr3);
end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
assert isSort(arr3);
}
测试结果：数据量一万以下级别
测试结果：数据量一万以上级别
结论：其第二种优化方案，是最可行的。第一种优化方案，在一万的数据量以下的情况下，是可行的。（不知道第一种优化，方案怎么了，难道是每趟多了两个复制语句？）
其中数组复制的最优方法来自：Java中数组复制的四种方法
注意：编译器默认不适用 assert 检测（但是junit测试中适用），所以要使用时要添加参数虚拟机启动参数 -ea 具体添加过程，请参照eclipse 和 IDEA 设置虚拟机启动参数
网友评论