1.冒泡排序的定义
冒泡排序( Bubble Sort) 一种交换排序，两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
2.冒泡排序的流程
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
实例：
分析：
无序序列 { 4. 3. 1. 2, 5 }
第一趟排序：通过两两比较，找到第一小的数值 1 ，将其放在序列的第一位。
第二趟排序：通过两两比较，找到第二小的数值 2 ，将其放在序列的第二位。
第三趟排序：通过两两比较，找到第三小的数值 3 ，将其放在序列的第三位。
排序结束。
3.冒泡排序的代码实现
public class BubbleSort {
public static void bubbleSort(int[] array
) {
for (int i
= 0; i
< array
.length
- 1; i
++) {
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
;
}
}
}
}
public static void main(String
[] args
) {
int[] array
= {5, 9, 3, 8, 4, 6, 7};
bubbleSort(array
);
System
.out
.println("排序后的的数组（升序）：" + Arrays
.toString(array
));
}
}
输出结果
排序后的的数组（升序）：
[3, 4, 5, 6, 7, 8, 9]
4.算法分析
（1）冒泡排序算法的性能
（2）时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值，冒泡排序最好时间复杂度为O(N)。
若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，冒泡排序的最坏时间复杂度为O(N2)。
因此，冒泡排序的平均时间复杂度为O(N2)。
当数据越接近正序时，冒泡排序性能越好。
（3）算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间，所以相同元素的前后顺序并没有改变，冒泡排序是稳定的。
5.优化
加入标志性变量flag，用于标志某一趟排序过程中是否有数据交换，若无数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。优化后的冒泡排序：
public static void bubbleSort2(int[] array
) {
for (int i
= 0; i
< array
.length
- 1; i
++) {
boolean flag
= false;
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
;
flag
= true;
}
}
if (!flag
) {
break;
}
}
}
本人才疏学浅，若有错，请指出 谢谢！
