一. 什么是冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。 —百度百科
形象的动画展示
![image](http://images.cnblogs.com/cnblogs_com/kkun/201111/201111301912294589.gif)
图一[图片来自网络]
关于冒泡排序的算法思想,我相信大家都已经很熟悉了,网上也有许多关于这个算法的实现。下面简单说一下
(从小到大排序)存在10个不同大小的气泡,由底至上地把较少的气泡逐步地向上升,这样经过遍历一次后,最小的气泡就会被上升到顶(下标为0),然后再从底至上地这样升,循环直至十个气泡大小有序。
在冒泡排序中,最重要的思想是两两比较,将两者较少的升上去
冒泡排序最坏情况的时间复杂度是O(n²)。
二. 冒泡排序算法实现
冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序
![image](http://upload.wikimedia.org/wikipedia/commons/0/06/Bubble-sort.gif)
图二[图片来自网络]
程序框架
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的位置以前已经有序,不需要后面的元素网上冒泡。所以我们记录下这个值,下面的算法只需要排这个元素之后的值就行了,进一步的优化了算法。
三.总结
在很多的地方介绍冒泡算法的时候,并没有出现第三种优化,虽然比较的趟数和优化二是一样的,但是,在待排序列中若有前部分已经有序,这样可以在一定程度上减少比较次数,不失为一种好的算法。