思想
- 依次比较相邻的两个数据，如果前面的比后面的大，就将其交换
- 这样交换一轮之后，整个序列中最大的就“沉”到了最后面的位置
- 重复上述过程，依次把第二大、第三大...的数字放到后面的位置。
代码
1
2
3
4
5
6
7
8
9
10
11
| void BubbleSort(int a[], int len) {
for (int i = 0; i < len; i++) {//一共需要遍历len轮
for (int j = 0; j < len -1-i; j++) {//后面的len-1个数据
if (a[j] > a[j + 1]) {
int temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
}
|
接下来可以优化一下，上面的程序中一共进行了N轮比较，其实如果有一趟没有发生交换就说明这时候每两个相邻数据都已经呈现前边比后边小的状态了，此时已经达到有序状态了，所以后面就无需再继续比较了
改进代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void BubbleSort(int a[], int len) {
int flag = 1;
for (int i = 0; i < len; i++) {//一共需要遍历len轮
int flag = 0;//用来记录本轮是否发生交换
for (int j = 0; j < len - 1 - i; j++) {//后面的len-1个数据
if (a[j] > a[j + 1]) {
int temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
flag = 1;//本轮发生交换了
}
}
if (flag == 0) {//如果本轮未发生交换，跳出
break;
}
}
}
|
还可以进一步优化，假设有100个数的数组，只有前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
一般地，冒泡排序在进行过程中，也会出现后面已经排好了的情况，所以如果记录一下有序的位置，下一次就可以不用向后遍历了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void BubbleSort(int a[], int len) {
int k ;//用于记录从那个数据开始之后的数据为
int flag = len-1;//用于几率从哪个数据开始之后的数据有序
while (flag > 0) {
k = flag;//计算到k之前
flag = 0;//用于记录本轮是否有交换
for (int j = 0; j < k; j++) {//后面的len-1个数据
if (a[j] > a[j + 1]) {
int temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
flag = j;//本轮交换了，更新交换位置
}
}
}
}
|
总结一下冒泡排序的关键点就是相邻元素两两比较交换，执行N轮，如果有某一轮没有发生交换说明已经有序，停止；记录下每一轮交换停止的位置，这之后的数据时有序的，下一轮无需考察。
时间复杂度
\(O(n^2)\)