pascal-冒泡选择插入与快速排序81550

《pascal-冒泡选择插入与快速排序81550》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、冒泡排序BubbleSort最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，

2、第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。procedureBubble_Sort(varL:List);vari,j:position;begin1fori:=First(L)toLast(L)-1do2forj:=First(L)toLast(L)-ido3ifL[j]>L[j+1]then4swap(L[j],L[j+1]);//交换L[j]和L[j+1]end;上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中First(L)和Last(L)

3、分别表示线性表L的第一个元素和最后一个元素的位置，swap(x,y)交换变量x,y的值。上述算法简单地将线性表的位置当作整数用for循环来处理，但实际上线性表可能用链表实现；而且上述算法将线性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。容易看出该算法总共进行了n(n-1)/2次比较。如果swap过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录，则Swap过程要消耗大量的时间，因此有必要分析swap执行的

4、次数。显然算法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排

5、序时，总共需要将这两个元素对调一次。n个元素中任取两个元素有Cn2种取法，因此对于两个互逆序列进行排序，总共要调用Cn2=n(n-1)/2次Swap，平均每个序列要调用n(n-1)/4次Swap。那么算法Bubble_Sort调用Swap的平均次数为n(n-1)/4。可以对冒泡算法作一些改进，如果算法第二行的某次内循环没有进行元素交换，则说明排序工作已经完成，可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换，如果没有则终止外循环。冒泡法的另一个改进版本是双向扫描冒泡法（Bi-DirectionalBubbleSort

6、）。设被排序的表中各元素键值序列为：4836788850255406134592657745683对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是L[4]和L[5]：5067255134

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

8、reBi-Directional_Bubble_Sort(varL:List);varlow,up,t,i:position;begin1low:=First(L);up:=Last(L);2whileup>lowdobegin3t:=low;4fori:=lowtoup-1do5ifL[i]>L[i+1]thenbegin6swap(L[i],L[i+1]);7t:=i;end;8up:=t;9fori:=updowntolow+1do10ifL[i]

9、=i;end;13low:=t;end;end;算法利用两个变量low和up记录排序的区域L[low..up]，用变量t记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t所记录的最后一次交换记