基本思想
冒泡排序 (Bubble Sort) 是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
思路分析
将 [ 7, 9, 5, 1, 3 ] 实现升序排序步骤如下：
- 第一趟：第一个元素到最后一个元素之间两两比较，大的元素往后移，这样下来就找到了最大元素。
- 第二趟：第一个元素到倒数第二个元素之间两两比较，大的元素后移，这样下来就找到了第二大的元素。
- 第三趟、第四趟如上步骤。
- 当第四趟步骤结束之后，后面的四个元素都找到了相应的位置，相应而言 1 也找到了位置，排序结束。
小结：
- 一共进行了
元素个数 - 1趟排序。 - 每一趟排序的次数都逐渐减少。
- 优化：如果在某一趟中，元素没有发生过任何交换，那么可以提前终止排序流程。
代码实现
Java 代码：
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {7, 9, 5, 1, 3};
System.out.println(" == 排序前 == ");
System.out.println(Arrays.toString(arr));
// 总共进行 (arr.length - 1) 趟排序
for (int i = 0; i < arr.length - 1; i++) {
// 每一趟比较 (arr.length - i - 1) 次
for (int j = 0; j < arr.length - i - 1; j++) {
// 如果前面的数比后面的数，则交换位置
if (arr[j] > arr[j + 1]) {
int tem = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tem;
}
}
System.out.println(" == 第 " + (i + 1) + " 次排序 == ");
System.out.println(Arrays.toString(arr));
}
}
}
控制台输出：
== 排序前 ==
[7, 9, 5, 1, 3]
== 第 1 次排序 ==
[7, 5, 1, 3, 9]
== 第 2 次排序 ==
[5, 1, 3, 7, 9]
== 第 3 次排序 ==
[1, 3, 5, 7, 9]
== 第 4 次排序 ==
[1, 3, 5, 7, 9]
冒泡排序的优化
如果在某一趟中，元素没有发生过任何交换，那么可以提前终止排序流程。
思路：
- 添加一个标识，整个标识用来判断当前这一趟是否交换过数据，如果没有交换过，直接结束排序。
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {7, 1, 2, 3, 4};
System.out.println(" == 排序前 == ");
System.out.println(Arrays.toString(arr));
// 总共进行 (arr.length - 1) 趟排序
for (int i = 0; i < arr.length - 1; i++) {
// 标识变量，标识是否进行交换，交换的时候将该值设置成 true
boolean flag = false;
// 每一趟比较 (arr.length - i - 1) 次
for (int j = 0; j < arr.length - i - 1; j++) {
// 如果前面的数比后面的数，则交换位置
if (arr[j] > arr[j + 1]) {
// 将标识设置为 true
flag = true;
int tem = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tem;
}
}
System.out.println(" == 第 " + (i + 1) + " 次排序 == ");
System.out.println(Arrays.toString(arr));
if (!flag) {
// 如果上面没有发生过交换，说明排序已经结束
break;
}
}
}
}
控制台输出：
== 排序前 ==
[7, 1, 2, 3, 4]
== 第 1 次排序 ==
[1, 2, 3, 4, 7]
== 第 2 次排序 ==
[1, 2, 3, 4, 7]
说明：在第二趟排序的时候，元素之间没有交换的，说明排序完成，结束排序操作。
冒泡算法分析
时间复杂度：
- 最坏的情况，时间复杂度为：
(n-1)+(n-2)+(n-3)+...+n=n*(n-1)/2= O(n^2) - 最好的情况，时间复杂度位：
O(n)
空间复杂度：O(1)
算法稳定性：稳定