冒泡排序
冒泡排序的基本思想：通过对待排序序列从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部。因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志swap判断元素是否进行过交换。从而减少不必要的比较。
冒泡排序.gif
冒泡排序示例:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 状态 |
|---|---|---|---|---|---|---|---|---|
| 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49' | 初始状态 |
| 38 | 49 | 65 | 76 | 13 | 27 | 49' | 97 | 第一趟 |
| 38 | 49 | 65 | 13 | 27 | 49' | 76 | 97 | 第二趟 |
| 38 | 49 | 13 | 27 | 49' | 65 | 76 | 97 | 第三趟 |
| 38 | 13 | 27 | 49 | 49' | 65 | 76 | 97 | 第四趟 |
| 13 | 27 | 38 | 49 | 49' | 65 | 76 | 97 | 第五趟 |
| 13 | 27 | 38 | 49 | 49' | 65 | 76 | 97 | 第六趟 |
代码：
public static void main(String[] args) {
int[] s = { 49, 38, 65, 97, 76, 13, 27, 49 };
new BubbleSort().bubble_Sort(s);
for (int i = 0; i < s.length; i++) {
System.out.printf("%d ", s[i]);
}
}
void bubble_Sort(int[] s) {
if (s.length < 2) {
return;
}
for (int i = 0; i < s.length; i++) {
boolean swap = false;
for (int j = 1; j < s.length; j++) {
if (s[j] < s[j - 1]) {
int temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
swap = true;
}
}
if (!swap) {
break;
}
}
}
输出：
13 27 38 49 49 65 76 97
冒泡排序的效率分析
| 排序算法 | 平均时间性能 | 最好时间性能 | 最坏时间性能 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 |  |
 |
|
 |
稳定 |
- 从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为(n-1)次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为 n(n-1)/2，移动次数为3n(n-1)/2，因此冒泡排序算法的时间复杂度为O(2n)。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。
- 因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。
