分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(n^2)
最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 稳定
原理
它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
步骤
- 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现
public class BubbleSort {
void sort(Integer[] array){
// 每次最大元素就像气泡一样"浮"到数组的最后
for (int i = 0; i < array.length - 1 ; i++){
// 依次比较相邻的两个元素,使较大的那个向后移
for(int j = 0; j < array.length - 1 - i;j++){
// 判断是否当前位置的数值大于下一个位置的数值，如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
if (array[j] > array[j+1]){
//交换
Tool.exchange(array,j,j+1);
}
}
}
}
public static void main(String[] args){
Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
BubbleSort sort = new BubbleSort();
sort.sort(a);
System.out.println("array by BubbleSort is " + Tool.arrayToString(a));
}
}
public class Tool {
public static <T> String arrayToString(T[] array){
StringBuilder builder = new StringBuilder("[");
for (int i = 0; i < array.length; i++){
T item = array[i];
builder.append(item + "");
if (i != array.length - 1){
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
public static <T> void exchange(T[] array, int i, int j){
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
实现结果：
array by BubbleSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]
