算法描述:
1.临近的数字两两进行比较,按照从小到大顺序进行交换,直到到达有序区域。
2.如果未排序区域非空，重复步骤1。
举个例子：以下是{5, 1, 12, -5, 16}的排序过程
排序过程
PS：博主还发现了一个非常好的算法可视化过程示例，请见1.
复杂度分析
时间：最优平均和最差都是O(n²)
空间：O(1).
是稳定的排序算法。
在前文的描述中，可以看到对于已经排序的数列而言，即最优情况下，O(n²)次的比较是不必要的。如果在某趟遍历过程中并没有发生任何的交换，则可以认为数列已经有序，程序可以终止。查看优化后的冒泡排序代码请参考2。
冒泡排序代码(未优化)
public void bubbleSort(int[] arr) {
int temp;
for (int j = arr.length - 1; j > 0; j--) {
for (int i = 0; i < j; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
冒泡排序代码(优化)
public void bubbleSort( int [] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
