一. 什么是冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。 —百度百科
形象的动画展示
图一[图片来自网络]
关于冒泡排序的算法思想，我相信大家都已经很熟悉了，网上也有许多关于这个算法的实现。下面简单说一下
（从小到大排序）存在10个不同大小的气泡，由底至上地把较少的气泡逐步地向上升，这样经过遍历一次后，最小的气泡就会被上升到顶（下标为0），然后再从底至上地这样升，循环直至十个气泡大小有序。
在冒泡排序中，最重要的思想是两两比较，将两者较少的升上去
冒泡排序最坏情况的时间复杂度是O(n²)。
二. 冒泡排序算法实现
冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序
图二[图片来自网络]
程序框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
using namespace std;
void print(int* pData, int count){
for (int i = 0; i< count; i++) {
cout << pData[i] << " ";
}
cout << endl;
}
void BubbleSort(int* pData, int count);
int main()
{
int data[] = {1,2,3,4,5,10,9,8,7,6};
BubbleSort(data, 10);
}
|
1. 未优化算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void BubbleSort(int* pData, int count)
{
int temp;
int counter=0;
for (int i = 1; i < count; i++)
{
for (int j = count - 1; j >= i; j--)
{
counter++;
if (pData[j] < pData[j - 1])
{
temp = pData[j - 1];
pData[j - 1] = pData[j];
pData[j] = temp;
}
}
cout << "第 "<< i <<"次:"<<endl;
print(pData, count);
cout << "----------------------------" << endl;
}
cout<<"运算次数 "<<counter<<endl;
}
|
结果：
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
| 第 1次:
1 2 3 4 5 6 10 9 8 7
----------------------------
第 2次:
1 2 3 4 5 6 7 10 9 8
----------------------------
第 3次:
1 2 3 4 5 6 7 8 10 9
----------------------------
第 4次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 5次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 6次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 7次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 8次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 9次:
1 2 3 4 5 6 7 8 9 10
----------------------------
运算次数 45
|
运算总次数为45次，很明显可以看出第5次就已经有序，没有必要往下，于是有了以下优化。
2. 设置flag
设置flag的目的就是，倘若这一次排序过程中未出现元素互换的操作，即说明这次排序的上一次已经有序了，已经没有必要再往下继续。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void BubbleSort(int* pData, int count)
{ bool flag =true;
int temp;
int counter=0;
for (int i = 1; i < count &flag; i++)
{
flag = false;
for (int j = count - 1; j >= i; j--)
{
counter++;
if (pData[j] < pData[j - 1])
{
temp = pData[j - 1];
pData[j - 1] = pData[j];
pData[j] = temp;
flag = true;
}
}
cout << "第 "<< i <<"次:"<<endl;
print(pData, count);
cout << "----------------------------" << endl;
}
cout<<"运算次数 "<<counter<<endl;
}
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 第 1次:
1 2 3 4 5 6 10 9 8 7
----------------------------
第 2次:
1 2 3 4 5 6 7 10 9 8
----------------------------
第 3次:
1 2 3 4 5 6 7 8 10 9
----------------------------
第 4次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 5次:
1 2 3 4 5 6 7 8 9 10
----------------------------
运算次数 35
|
这次的总趟数比上次要少。其实我们还可以在总比较次数上继续优化。
3. 进一步优化
进一步优化的目的是如果排序序列中前排部分有序（从下往上冒泡），我们在做某次冒泡过程中发现在某个位置以上部分都已经有序了，我们也没有必要再继续往上比较了，这比第二种算法比较次数还要少一些。虽然要满足一些特定条件才会减少次数。就是因为这种算法在很多书籍，博客等一些讲冒泡时都未曾指出，所以将这种算法的思路予以说明。
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
| void BubbleSort(int* pData, int count)
{
int temp;
int ptr = count;
int counter=0;
int round = 0;
for (int i = 1; i < count;)
{
for (int j = count - 1; j >=i; j--)
{
counter++;
if (pData[j] < pData[j - 1])
{
temp = pData[j - 1];
pData[j - 1] = pData[j];
pData[j] = temp;
ptr=j;
}
}
i = i==ptr?count:ptr;
cout << "第 "<< ++round <<"次:"<<endl;
print(pData, count);
cout << "----------------------------" << endl;
}
cout<<"运算次数 "<<counter<<endl;
}
|
以下是实验结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 第 1次:
1 2 3 4 5 6 10 9 8 7
----------------------------
第 2次:
1 2 3 4 5 6 7 10 9 8
----------------------------
第 3次:
1 2 3 4 5 6 7 8 10 9
----------------------------
第 4次:
1 2 3 4 5 6 7 8 9 10
----------------------------
第 5次:
1 2 3 4 5 6 7 8 9 10
----------------------------
运算次数 19
|
可以看出虽然比较趟数和优化2一样但是比较次数减少了16次，因为在元素6的位置以前已经有序，不需要后面的元素网上冒泡。所以我们记录下这个值，下面的算法只需要排这个元素之后的值就行了，进一步的优化了算法。
三.总结
在很多的地方介绍冒泡算法的时候，并没有出现第三种优化，虽然比较的趟数和优化二是一样的，但是，在待排序列中若有前部分已经有序，这样可以在一定程度上减少比较次数，不失为一种好的算法。