冒泡排序
思想
同之前介绍的两种排序方式一样，冒泡排序也是最简单最基本的排序方法之一。冒泡排序的思想很简单，就是以此比较相邻的元素大小，将小的前移，大的后移，就像水中的气泡一样，最小的元素经过几次移动，会最终浮到水面上。
举例分析说明一下，如下数据：
2 7 4 6 9 1 首先比较最后两个数字，发现1比9小，于是前移
2 7 4 6 1 9 然后比较6和1
2 7 4 1 6 9 继续前移，然后是4和1
2 7 1 4 6 9 7和1比较
2 1 7 4 6 9 2和1
1 2 7 4 6 9 至此，第一趟冒泡过程完成，最小的元素1被移到第一个，不再参与后面的排序过程。下一趟冒泡过程同理，比较6和9，以此类推，最终得到结果。
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void
bubbleSort(
int
arr[],
int
n)
{
int
i,j,t;
for
(i=0;i<n-1;i++)
for
(j=0;j<n-i-1;j++)
if
(arr[j+1]<arr[j])
{
t=arr[j+1];
arr[j+1]=arr[j];
arr[j]=t;
}
}
|
测试代码如下：
冒泡排序是非常容易理解和实现，，以从小到大排序举例：
设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
按照定义很容易写出代码：
|
1
2
3
4
5
6
7
8
9
|
//冒泡排序1
void
BubbleSort1(
int
a[],
int
n)
{
int
i, j;
for
(i = 0; i < n; i++)
for
(j = 1; j < n - i; j++)
if
(a[j - 1] > a[j])
Swap(a[j - 1], a[j]);
}
|
下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//冒泡排序2
void
BubbleSort2(
int
a[],
int
n)
{
int
j, k;
bool
flag;
k = n;
flag =
true
;
while
(flag)
{
flag =
false
;
for
(j = 1; j < k; j++)
if
(a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag =
true
;
}
k--;
}
}
|
再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//冒泡排序3
void
BubbleSort3(
int
a[],
int
n)
{
int
j, k;
int
flag;
flag = n;
while
(flag > 0)
{
k = flag;
flag = 0;
for
(j = 1; j < k; j++)
if
(a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = j;
}
}
}
|
冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。
分析
因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。以此本算法的时间复杂度还是O(n*n)，也不能算是一个高效的算法。
细心分析不难发现，本算法还有可以优化的空间，若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的 原则，因此，冒泡排序过程可在此趟排序后终止。为此， 在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序 结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。这样可以减少不必要的比较。代码如下
int bubble_sort(vector<int> &v){
cout << "bubble sort:" << endl;
printline("before sort:", v);
bool exchange;
for (int i=0; i<v.size(); i++){
int temp = 0;
exchange = false;
for(int j=v.size()-1; j>0; j--){
if (v[j] < v[j-1]){
temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
exchange = true;
}
}
if (!exchange){
break;
}
}
printline("after sort:",v);
}
原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,
然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子。例子为从小到大排序,
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |
第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |
第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |
第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第四趟排序(外循环)无交换
第五趟排序(外循环)无交换
排序完毕,输出最终结果1 2 4 5 6 9
冒泡排序动画演示
来源：http://www.cnblogs.com/luchen927/archive/2012/02/28/2367708.html
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3145397.html，如需转载请自行联系原作者
