交换排序——冒泡排序

冒泡排序（Bubble sort）算法就像他的名字一样。Bubble，气泡冒出的过程，物理上气泡受压强原因，越来越大。

冒泡排序的概念：

冒泡排序通过两两比较相邻的关键字，如果发生逆序，则进行交换，从而使关键字大的记录如同气泡一样逐渐右移，上浮出去。

关键字小的逐渐下沉（左移）。

冒泡排序的原理：

1，待排序的记录存放在数组r[1...n]中。

首先将第一个记录和第二个记录进行比较，若为逆序，

（L.r[1].key>L.r[2].key）,则将二者位置更换，然后比较第二和第三个记录的关键字，以此类推。

直到n-1和n进行比较，上述是第一趟冒泡的过程，其结果是最大的关键字被安置到了最后的位置上。

2，然后第二遍冒泡，对前n-1个元素进行同样的操作，其结果是从关键词次大的存储在n-1上。

3，重复上述冒泡，第i趟是从r[1]到r[n-i+1],直到某一趟没有交换记录即可。

此时我们的序列已经完成了排序。

以一个例子演示：

待排序关键字序列{49，38，65，97，76，13，27，【49】}

49 38 65 97 76 13 27 【49】初始记录，以49为标记方便更直观的演示

38 49 65 76 13 27 【49】97 第一趟

38 49 65 13 27 【49】76 第二趟

38 49 13 27 【49】65 第三趟

38 13 27 49【49】 第四趟

13 27 38 49 第五趟

13 27 38 第六趟

理论上说有8个元素就要遍历八次，不过为了节省开支，我们加上判定条件，让他只要没有交换记录的操作，就代表完成排序

代码描述：

void BubbleSort(SqList &L){

m=L.length-1;flag=1;

while((m>0)&&(flag==1))

{flag=0;

for(j=1;j<=m;j++){

if(L.r[j].key>L.r[j+1].key){

flag=1;

t=L.r[j];L.r[j]=L.t[J+1];L.r[j+1]=t;

}

--m;

}

}

}

分析：

时间复杂度：

最好情况：初始即为正序，只进行一趟排序，只需要进行n-1次比较。

最坏情况：初始为逆序，需要n-1趟排序，总的关键字比较数为KCN和移动次数RMN（每次都要移动三次记录）：因为有辅助t空间做暂存记录，所以每次交换需要三次。

Kcn=求和（i-1）~n^2/2

RMN=求和（i-1）~3n^2/2

算法特点：

稳定排序，相同值不交换顺序

可以使用链式存储

移动次数较多，性能较差，当N较大时，不推荐使用。