冒泡排序简介
冒泡排序是一种比较简单的排序算法。
它会遍历若干次要排序的数列。每次遍历时，它都会由前往后依次比较相邻两个数的大小。
若前者比后者大，则交换他们的位置。这样在一次遍历后，最大的元素就在数列的末尾了。
采用相同的方法再次遍历时，第二大的元素将被排列在最大元素之前。
重复此操作，直到整个数列都有序为止。
冒泡排序实现
下面以数列 a = {20, 40, 30, 10, 60, 50} 为例，演示冒泡排序的过程。
当 i = 5, j = 0 时，a[0] < a[1]。此时，不做任何处理。
当 i = 5, j = 1 时，a[1] > a[2]。因此，a[1] 和 a[2] 交换位置。
当 i = 5, j = 2 时，a[2] > a[3]。因此，a[2] 和 a[3] 交换位置。
当 i = 5, j = 3 时，a[3] < a[4]。此时，不做任何处理。
当 i = 5, j = 4 时，a[4] > a[5]。因此，a[4] 和 a[5] 交换位置。
第一趟排序完毕后，数列由 {20, 40, 30, 10, 60, 50} 变为 {20, 30, 10, 40, 50, 60}。
根据此方法，数列将在遍历 N-1 次后变得有序。但实际上，这一个数列在遍历到第三趟时就已经变得有序了，第四趟以及第五趟遍历中并没有任何数据交换。
为了提高冒泡排序的效率，可以添加一个标记，用以记录一趟遍历中是否发生了数据交换。若一趟遍历中没有发生数据交换，则表示数列已完成排序。
复杂度与稳定性
冒泡排序时间复杂度
假设被排序的数列中有 N 个数，遍历一趟的时间复杂度为 。
由于算法需要遍历 N-1 次，因此冒泡排序的时间复杂度为 。
冒泡排序稳定性
冒泡排序是稳定的算法，其满足稳定算法的定义，即假设在数列中存在 a[i] = a[j]，若 a[i] 在排序之前处在 a[j] 前面，并在排序之后仍处在 a[j] 前面，则该排序算法是稳定的。
代码实现
输入：arr为要排序数列，n为数列元素个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = n - 1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void optimized_bubbleSort(int arr[], int n) {
int i, j, temp, flag;
for (i = n - 1; i > 0; i--) {
flag = 0;
for (j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
}
}
if (flag == 0) {
break;
}
}
}