冒泡排序算法
IT商界
引子：
记得上小学五年级在少年宫学BASIC时，学得非常吃力，每次要完成老师布置的作业都像登天一样难。那时我便给自己得出了一个结论：这辈子是没天分学电脑的……但命运就是这样作弄人，我现在的职业就是程序员，而且我在大学还不是学的计算机专业。
其实每个智力正常的人，都应该拥有用电脑进行程序设计的本领，但为什么很多人都只能徘徊在程序设计的大门之外呢？我想这绝对不是他们不够聪明(我很长一段时间也是这种状态)，只是还没找到将日常的思维方式转换成计算机的工作流的窍门。而这个窍门就是──算法(算法是在有限步骤内求解某一问题所使用的一组定义明确的规则)。算法的概念很广泛，这里主要是指程序算法。可以这么说，如果将写程序和练武功做比较的话，那算法对于写程序而言就是内功基础，乃编程根基之所在！就像同样的“内功心法”可以用不同的手法来表现一样，同一种算法也可以用C或Pascal等不同的语言来实现。好了，不废话了，从本月起，每月的第一期我们就会在这里修炼“内功”！
招式：冒泡排序算法
招式说明：
对已知序列
招式拆解及手法实现：
最简单的排序方法是冒泡排序法。这种方法的基本思路是，将待排序的元素看做是竖着排列的“气泡”，较小的元素比较轻，要往上浮。在冒泡排序法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素了，所以不必检查。
这样下来，第n遍处理时，不必检查第n高位置以上的元素，因为经过前面n-1遍的处理，它们已正确地排好序。这个算法可通过如下方法实现(这里使用了仿Pascal语言来实现)：
procedure BubbleSort(var L); //L为已知元素的序列
var
i,j; //两个临时变量，i记录每一遍处理过程中的最高位置，j记录处理过程中被检验的点的位置。
begin
for i:=First(L) to Last(L)-1 do //对于有N个元素的序列而言，只要N-1次的排序。 //其中First(L)和Last(L)分别表示线性表L的第一个元素和最 //后一个元素的位置
for j:=First(L) to Last(L)-i do //每轮排序都是从最下面一个元素开始到第(n-i)个元素
if L[j]>L[j+1] then //如果次序不对
swap(L[j],L[j+1]); // swap(x,y)交换变量x，y的值，交换L[j]和L[j+1]
end;
上面的算法将较大的元素看作较重的“气泡”，每次最大的元素会沉到最后。很容易看出该算法总共进行了n(n-1)/2次比较。如果其中Swap过程消耗的时间不多的话，那么主要的时间都消耗在比较上了，因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录，Swap过程要消耗大量的时间，因此有必要分析Swap执行的次数。显然冒泡算法在最坏情况下调用n(n-1)/2次Swap过程。我们假设已知序列的分布是均匀的，再考虑互逆的两个已知序列L1=k1,k2,..,kn和L2=kn,kn-1,..,k1。我们知道，如果ki>kj，且ki在表中排在kj前面，则在冒泡法排序时必定要将kj换到ki前面，即kj向前浮的过程中一定要穿过一次ki，这个过程要调用一次Swap。对于任意的两个元素ki和kj，假设ki>kj，那么在L1或者L2中必有一个是ki排在kj前面的。因此对于任意的两个元素ki和kj，在同时对L1和L2排序时，必须将这两个元素对调一次。n个元素中任取两个元素有C种取法，因此对于两个互逆序列进行排序，总共要调用C=n(n-1)/2次Swap，平均每个序列要调用n(n-1)/4次Swap。那么冒泡算法调用Swap的平均次数为n(n-1)/4。
其实我们还可以对冒泡算法做一些改进，如果某遍处理过程中没有进行元素交换，则说明排序工作已经完成。这样我们可以考虑用一个布尔变量来记录某遍处理中是否进行了记录交换，如果没有则终止处理。这样可以有效提高算法的执行效率。