pascal冒泡选择插入与快速排序.docx
《pascal冒泡选择插入与快速排序.docx》由会员分享，可在线阅读，更多相关《pascal冒泡选择插入与快速排序.docx（24页珍藏版）》请在冰点文库上搜索。
pascal冒泡选择插入与快速排序
冒泡排序BubbleSort
最简单的排序方法是冒泡排序方法。
这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。
在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。
所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。
如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。
显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。
在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。
一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
这个算法可实现如下。
procedureBubble_Sort（varL:
List）;
var
i,j:
position;
begin
1fori:
=First（L）toLast（L）-1do
2forj:
=First（L）toLast（L）-ido
3ifL[j]>L[j+1]then
4swap（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-DirectionalBubbleSort）。
设被排序的表中各元素键值序列为：
4836788850255406134592657745683
对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是L[4]和L[5]：
5067255134|406483592657683745888
显然，第3次扫描（i=3）结束后L[5]以后的序列都已经排好序了，所以下一次扫描不必到达Last（L）-i=11-4=7，即第2行的for循环j不必到达7，只要到达4-1=3就可以了。
按照这种思路，可以来回地进行扫描，即先从头扫到尾，再从尾扫到头。
这样就得到双向冒泡排序算法：
procedureBi-Directional_Bubble_Sort（varL:
List）;
var
low,up,t,i:
position;
begin
1low:
=First（L）;up:
=Last（L）;
2whileup>lowdo
begin
3t:
=low;
4fori:
=lowtoup-1do
5ifL[i]>L[i+1]then
begin
6swap（L[i],L[i+1]）;
7t:
=i;
end;
8up:
=t;
9fori:
=updowntolow+1do
10ifL[i]begin
11swap（L[i],L[i-1]）;
12t:
=i;
end;
13low:
=t;
end;
end;
算法利用两个变量low和up记录排序的区域L[low..up]，用变量t记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t所记录的最后一次交换记录的位置，并不断地缩小需要排序的区间，直到该区间只剩下一个元素。
直观上来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较轻气泡浮上来，依次反复，直到排序结束。
[参考算法]：
Pascal语言表述的冒泡排序算法
proceduresort;
vari,j,k:
integer;
begin
fori:
=ndownto1do
forj:
=1toi-1do
ifa[j]>a[i]thenbegin
a[0]:
=a[i];a[i]:
=a[j];a[j]:
=a[0];
end;
end;
选择排序SelectionSort
选择排序的基本思想是：
对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。
这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
当然，实际操作时，也可以根据需要，通过从待排序的记录中选择最大者与其首记录交换位置，按从大到小的顺序进行排序处理。
选择排序算法可实现如下。
procedureSelection_Sort（varL:
List）;
var
i,j,s:
position;
begin
1fori:
=First（L）toLast（L）-1do
begin
2s:
=i;
3forj:
=i+1toLast（L）do
4ifL[j]=j;//记录L[i..n]中最小元素的位置
5swap（L[i],L[s]）;//交换L[i],L[s]
end;
end;
算法Selection_Sort中里面的一个for循环需要进行n-i次比较，所以整个算法需要
次比较，显而易见，算法Selection_Sort中共调用了n-1次swap过程，即进行了n-1次交换。
因而，算法Selection_Sort的时间复杂性f（n）=O（n2）。
[参考算法]：
Pascal语言表述的选择排序算法
proceduresort;
vari,j,k:
integer;
begin
fori:
=1ton-1dobegin
k:
=i;
forj:
=i+1tondo
ifa[j]=j;
{找出a[I]..a[n]中最小的数与a[I]作交换}
ifk<>ithenbegin
a[0]:
=a[k];a[k]:
=a[i];a[i]:
=a[0];
end;
end;
end;
思考与练习：
完成并提交作业
下面是一选择算法的程序段：
begin
1fori:
=1ton-1do
begin
2min:
=i;
3forj:
=____tondo
4 ifL[j]=j; //选出最小元素的位置min
5if_____thenswap（L[i],L[s]）;//在什么条件下才交换记录?
end;
end;
（1）在____中填上正确的语句或表达式；
（2）若待排数据是3，1，2，4，5，整个算法需要进行多少次比较？
多少次交换？
插入排序InsertionSort
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。
第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。
要达到这个目的，我们可以用顺序比较的方法。
首先比较L[i]和L[i-1]，如果L[i-1]≤L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j（1≤j≤i-1），使得L[j]≤L[j+1]时为止。
简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。
图1演示了对4个元素进行直接插入排序的过程，共需要（a）,（b）,（c）三次插入。
图1对4个元素进行插入排序
在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。
所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。
如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。
另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。
下面的算法中将对当前位置进行判断。
插入排序算法如下：
procedureSelection_Sort（varL:
List）;
var
i,j:
position;
v:
ElementType;
begin
1fori:
=First（L）+1toLast（L）do
begin
2v:
=L[i];
3j:
=i;
4while（j<>First（L））and（L[j-1]begin
5L[j]:
=L[j-1];//移动元素
6j:
=j-1;
end;
7L[j]:
=v;//插入元素
end;
end;
下面考虑算法Insertion_Sort的复杂性。
对于确定的i，内while循环的次数为O（i），所以整个循环体内执行了∑O（i）=O（∑i），其中i从2到n。
即比较次数为O（n2）。
如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了∑（i-1）=n（n-1）/2次。
由此可知，最坏情况下，Insertion_Sort要比较O（n2）次。
如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。
经过分析可知，平均情况下第5行要执行n（n-1）/4次，分析方法与冒泡排序的分析相同。
如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下（当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面的算法比较复杂）：
注意：
在下面的算法中链表L增加了一个哨兵单元，其中的元素为-∞，即线性表L的第一个元素是L^.next^
procedureSelection_Sort_II（varL:
PList）;
var
i,j,tmp:
Position;
begin
1ifL^.next=nilthenexit;//如果链表L为空则直接退出
2i:
=L^.next;//i指向L的第一个元素，注意，L有一个哨兵元素，因此L^.next^才是L的第一个元素
3whilei^.next<>nildo
begin
4tmp:
=i^.next;//tmp指向L[i]的下一个位置
5j:
=L;
6while（j<>i）and（tmp^.data>=j^.next^.data）do//从前向后找到tmp的位置，tmp应该插在j后面
7j:
=j^.next;
8ifj<>ithen//j=i说明不需要改变tmp的位置
begin
9i^.next:
=tmp^.next;//将tmp从i后面摘除
10tmp^.next:
=j^.next;//在j后面插入tmp
11j^.next:
=tmp;
end
12elsei:
=i^.next;//否则i指向下一个元素
end;
end;
上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。
插入法虽然在最坏情况下复杂性为O（n2），但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。
许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。
这里是一个用JavaApplet制作的插入排序演示程序。
[参考算法]：
Pascal语言表述的插入排序算法
procedureinsert_sort（k,m:
word）;
{k为当前要插入的数，m为插入位置的指针}
vari:
word;p:
0..1;
begin
p:
=0;
fori:
=mdownto1do
ifk=a[i]thenexit;
repeat
Ifk>a[m]thenbegin
a[m+1]:
=k;p:
=1;
end
elsebegin
a[m+1]:
=a[m];dec（m）;
end;
untilp=1;
end;{insert_sort}
*主程序中为：
a[0]:
=0;
forI:
=1tondoinsert_sort（b[I],I-1）;
思考与练习：
完成并提交作业
试对前述的插入排序、冒泡排序、选择排序进行速度比较。
快速排序QuickSort
我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω（nlogn）计算时间。
如果我们能设计一个需要O（n1ogn）时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。
许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要O（nlogn）时间。
这个算法是由
算法的基本思想
快速排序的基本思想是基于分治策略的。
对于输入的子序列L[p..r]，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理：
▪分解（Divide）：
将待排序列L[p..r]划分为两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
具体可通过这样的途径实现：
在序列L[p..r]中选择数据元素L[q]，经比较和移动后，L[q]将处于L[p..r]中间的适当位置，使得数据元素L[q]的值小于L[q+1..r]中任一元素的值。
▪递归求解（Conquer）：
通过递归调用快速排序算法，分别对L[p..q]和L[q+1..r]进行排序。
▪合并（Merge）：
由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序，即自然合并。
这个解决流程是符合分治法的基本步骤的。
因此，快速排序法是分治法的经典应用实例之一。
算法的实现
算法Quick_Sort的实现：
注意：
下面的记号L[p..r]代表线性表L从位置p到位置r的元素的集合，但是L并不一定要用数组来实现，可以是用任何一种实现方法（比如说链表），这里L[p..r]只是一种记号。
procedureQuick_Sort（p,r:
position;varL:
List）;
const
e=12;
var
q:
position;
begin
1ifr-p<=ethenInsertion_Sort（L,p,r）
//若L[p..r]足够小则直接对L[p..r]进行插入排序
elsebegin
2q:
=partition（p,r,L）;
//将L[p..r]分解为L[p..q]和L[q+1..r]两部分
3Quick_Sort（p,q,L）;//递归排序L[p..q]
4Quick_Sort（q+1,r,L）;//递归排序L[q+1..r]
end;
end;
对线性表L[1..n]进行排序，只要调用Quick_Sort（1,n,L）就可以了。
算法首先判断L[p..r]是否足够小，若足够小则直接对L[p..r]进行排序，Sort可以是任何一种简单的排序法，一般用插入排序。
这是因为，对于较小的表，快速排序中划分和递归的开销使得该算法的效率还不如其它的直接排序法好。
至于规模多小才算足够小，并没有一定的标准，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈值。
经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p<=e=12即L[p..r]的规模不大于12时，直接采用插入排序法对L[p..r]进行排序。
当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序（其实还剩两个元素时就已经在Partition函数中排好序了），只要把第1行的if语句改为ifp=rthenexitelse...。
这就是通常教科书上看到的快速排序的形式。
注意：
算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。
因此下面在partition函数里加了限制条件，避免q=r情况的出现。
算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：
1.在L[p..r]中选择一个支点元素pivot;
2.对L[p..r]中的元素进行整理，使得L[p..q]分为两部分L[p..q]和L[q+1..r]，并且L[p..q]中的每一个元素的值不大于pivot，L[q+1..r]中的每一个元素的值不小于pivot，但是L[p..q]和L[q+1..r]中的元素并不要求排好序。
快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求L[p..q]和L[q+1..r]中的元素排好序。
函数partition可以实现如下。
以下的实现方法是原地置换的，当然也有不是原地置换的方法，实现起来较为简单，这里就不介绍了。
functionpartition（p,r:
position;varL:
List）:
position;
var
pivot:
ElementType;
i,j:
position;
begin
1pivot:
=Select_Pivot（p,r,L）;//在L[p..r]中选择一个支点元素pivot
2i:
=p-1;
3j:
=r+1;
4whiletruedo
begin
5repeatj:
=j-1untilL[j]<=pivot;
//移动左指针，注意这里不能用while循环
6repeati:
=i+1untilL[i]>=pivot;
//移动右指针，注意这里不能用while循环
7ifi8elseifj<>rthenreturnj//返回j的值作为分割点
9elsereturnj-1;//返回j前一位置作为分割点
end;
end;
该算法的实现很精巧。
其中，有一些细节需要注意。
例如，算法中的位置i和j不会超出A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为while则要注意当L[i]=L[j]=pivot且i另外，最后一个if..then..语句很重要，因为如果pivot取的不好，使得Partition结束时j正好等于r，则如前所述，算法Quick_Sort会无限递归下去；因此必须判断j是否等于r，若j=r则返回j的前驱。
以上算法的一个执行实例如图1所示，其中pivot=L[p]=5：
图1Partition过程的一个执行实例
Partition对L[p..r]进行划分时，以pivot作为划分的基准，然后分别从左、右两端开始，扩展两个区域L[p..i]和L[j..r]，使得L[p..i]中元素的值小于或等于pivot，而L[j..r]中元素的值大于或等于pivot。
初始时i=p-1，且j=i+1，从而这两个区域是空的。
在while循环体中，位置j逐渐减小，i逐渐增大，直到L[i]≥pivot≥L[j]。
如果这两个不等式是严格的，则L[i]不会是左边区域的元素，而L[j]不会是右边区域的元素。
此时若i在j之前，就应该交换L[i]与L[j]的位置，扩展左右两个区域。
while循环重复至i不再j之前时结束。
这时L[p..r]己被划分成L[p..q]和L[q+1..r]，且满足L[p..q]中元素的值不大于L[q+1..r]中元素的值。
在过程Partition结束时返回划分点q。
寻找支点元素select_pivot有多种实现方法，不同的实现方法会导致快速排序的不同性能。
根据分治法平衡子问题的思想，我们希望支点元素可以使L[p..r]尽量平均地分为两部分，但实际上这是很难做到的。
下面我们给出几种寻找pivot的方法。
1.选择L[p..r]的第一个元素L[p]的值作为pivot；
2.选择L[p..r]的最后一个元素L[r]的值作为pivot；
3.选择L[p..r]中间位置的元素L[m]的值作为pivot；
4.选择L[p..r]的某一个随机位置上的值L[random（r-p）+p]的值作为pivot；
按照第4种方法随机选择pivot的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。
下面是一个快速排序的JavaApplet演示程序，该程序使用第一种pivot选择法，即选L[p]为pivot，因此Partition过程作了一些简化，与我们这里的Partition过程实现方法不同，但功能相同。
该程序是针对用数组实现的线性表，用C语言实现的。
[参考算法]：
Pascal语言表述的快速排序算法
proceduresort（l,r:
integer）;
vari,j,mid:
integer;
begin
i:
=l;j:
=r;mid:
=a[（l+r）div2];
{将当前序列在中间位置的数定义为中间数}
升级会员 