Pages

Monday, May 16, 2011

比较排序算法——冒泡排序(Bubble Sort)


最简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而 要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正 确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。

显然,处理一遍之后,“最轻”的元素就浮到了最高位 置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不 必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序。这个算法可实现如下。

procedure Bubble_Sort(var L:List);
var
i,j:position;
begin
1 for i:=First(L) to Last(L)-1 do
2  for j:=First(L) to Last(L)-i do
3     if L[j]>L[j+1] then
4           swap(L[j],L[j+1]);   //交换L[j]和L[j+1]
end;

上述算法将较大的元素看作较重的气泡,每次最大的元素沉到表尾。其中First(L)和Last(L)分别表示线性表L的第一个元素和最后一个元素的位 置,swap(x,y)交换变量x,y的值。上述算法简单地将线性表的位置当作整数用for循环来处理,但实际上线性表可能用链表实现;而且上述算法将线 性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明,所有的算法都用这种简化方式表达。

容易看出该算法总共进行了n(n-1)/2次比较。如果swap过程消耗的时间不多的话,主要时间消耗在比较上,因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录,则Swap过程要消耗大量的时间,因此有必要分析swap执行的次数。

显然算法Bubble_Sort在最坏情况下调用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中ki排在kj前面,或者L2在中ki排在kj前面,两者必居其一。因此对于任意的两个元素ki和kj,在对L1和L2排序时,总共需要将这两个元素对调一次。n个元素中任取两个元素有Cn2 种取法,因此对于两个互逆序列进行排序,总共要调用Cn2 =n(n-1)/2次Swap,平均每个序列要调用n(n-1)/4次Swap。那么算法Bubble_Sort调用Swap的平均次数为n(n-1)/4。

可以对冒泡算法作一些改进,如果算法第二行的某次内循环没有进行元素交换,则说明排序工作已经完成,可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换,如果没有则终止外循环。

冒泡法的另一个改进版本是双向扫描冒泡法(Bi-Directional Bubble Sort)。设被排序的表中各元素键值序列为:

483 67 888 50 255 406 134 592 657 745 683

对该序列进行3次扫描后会发现,第3此扫描中最后一次交换的一对纪录是L[4]和L[5]:

50 67 255 134 | 406 483 592 657 683 745 888

显然,第3次扫描(i=3)结束后L[5]以后的序列都已经排好序了,所以下一次扫描不必到达Last(L)-i=11-4=7,即第2行的for 循环j不必到达7,只要到达4-1=3就可以了。按照这种思路,可以来回地进行扫描,即先从头扫到尾,再从尾扫到头。这样就得到双向冒泡排序算法:

procedure Bi-Directional_Bubble_Sort(var L:List);
var
low,up,t,i:position;
begin
1  low:=First(L);up:=Last(L);
2  while up>low do
    begin
3     t:=low;
4     for i:=low to up-1 do
5       if L[i]>L[i+1] then
          begin
6           swap(L[i],L[i+1]);
7           t:=i;
          end;
8     up:=t;
9     for i:=up downto low+1 do
10      if L[i]< L[i-1] then
          begin
11          swap(L[i],L[i-1]);
12          t:=i;
          end;
13    low:=t;  
    end;
end;

算法利用两个变量low和up记录排序的区域L[low..up],用变量t 记录最近一次交换纪录的位置,4-7行从前向后扫描,9-12行从后向前扫描,每次扫描以后利用t所记录的最后一次交换记录的位置,并不断地缩小需要排序的区间,直到该区间只剩下一个元素。

直观上来看,双向冒泡法先让重的气泡沉到底下,然后让轻的气泡浮上来,然后再让较大气泡沉下去,让较轻气泡浮上来,依次反复,直到排序结束。冒泡排序法 和双向冒泡排序法是原地置换排序法,也是稳定排序法,如果算法Bubble_Sort中第3行的比较条件L[j]>L[j+1]改为 L[j]>= L[j+1],则不再是稳定排序法。

No comments:

Post a Comment