第3课 排序问题

排序排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。排序问题是一个十分重要的问题，并且排序的方法有很多种：例子：输入20个数，将它们按照从高到低的次序排列以后输出。方法一：选择排序选择排序的基本思想：首先从要进行排序的数中选择最大的一个数，将它放在第一个位置，然后从剩下的数中选择最大的放在第二个位置，如此继续，直到最后剩下的两个数中选出较大的数放在倒数第二个位置，剩下的一个数放在最后完成排序。具体操作：对需要排序的数据序列进行n-1遍的处理，第1遍处理是将L[2..n]中每一个元素与L[1]比较，最大者与L[1]交换位置，第2遍处理是将L[3..n]中每一个元素与L[2]比较，最大者与L[2]交换位置，......，第i遍处理是将L[i+1..n]中每一个元素与L[i]比较，最大者与L[i]交换位置。算法：1、输入20个数到数组a中；2、用外循环确定每一个数，需要循环19次；(Fori:=1to19do)3、用内循环实现确定数与后面所有数的比较和交换；Forj：=i+1to20do4、输出结果。Ifa[i]a[j]为了理解，我们以6个数为例来进行说明：a[1]a[2]a[3]a[4]a[5]a[6]457123547123745123745123745123745123第一趟结束754123754123754123754123第二趟结束754123754123754123第三趟结束754123754123第四趟结束754123第五趟结束参考程序如下：Programexample(input,output)；Vara:array[1..20]ofreal；temp:real；i,j:integer；BeginFori:=1to20do{读入20个元素}read(a[i])；Fori:=1to19do{从第一个到倒数第二个依次确定每个数}Forj：=i+1to20do{确定的数与它后面所有的数进行比较}Ifa[i]a[j]ThenBegintemp:=a[i]；a[i]：=a[j]；a[j]:=tempEnd；Fori:=1to20do{输出排序后的结果}Beginwrite(a[i])；Ifimod5=0{控制每行输出5个数据}ThenwritelnEnd；End.上面的程序每次交换两个元素需要执行3个语句，过多的交换必定要花费许多时间，我们做一下改进，就是在内循环中先找出最大值元素的下标，在内循环结束时才考虑是否要交换。改进的选择程序如下：Programexample(input,output)；Vara:array[1..20]ofreal；temp:real；i,j,k:integer；{添加了一个中间存放下标的变量k}BeginFori:=1to20do{读入20个元素}read(a[i])；Fori:=1to19do{从第一个到倒数第二个依次确定每个数}Begink:=i；Forj：=i+1to20do{比较之后仅将下标交换给变量k}Ifa[i]a[j]Thenk:=j；IfikThenBegintemp:=a[i]；a[i]：=a[k]；a[k]:=tempEnd；End；Fori:=1to20do{输出排序后的结果}write(a[i])；End.例子：输入20个数，将它们按照从高到低的次序排列以后输出。方法二：冒泡排序冒泡排序的基本思想：依次比较相邻的两个数，将较大的数放在前面，较小的数放在后面。即首先比较第1个数和第2个数，将大的放在前面小的放在后面，然后比较第2个数和第3个数，仍将大的放在前面小的放在后面，如此继续，直到比较最后两个数，大的放在前面小的放在后面，此时第一趟结束，在最后的数必定是最小的数。重复以上步骤，只是最后不用比较最后两个数，这一趟比第一趟少了一步，依次继续下去，直到最后一趟，只比较第一对数，大的放在前面小的放在后面，从而完成排序。由于在排序过程中总是大数往前放，小数往后放，相当于气泡往上升，所以叫冒泡排序。算法：1、输入20个数到数组a中；2、用外循环实现将最小的数置后，需要循环19次；(Fori:=1to19do)3、用内循环实现相邻两位数的置换；Forj：=1to20-ido4、输出结果。Ifa[j]a[j+1]a[1]a[2]a[3]a[4]a[5]a[6]457123547123574123574123574213574231第一趟结束754231754231754231754321第二趟结束754321754321754321第三趟结束754321754321第四趟结束754321第五趟结束为了理解，我们以6个数为例来进行说明：参考程序如下：Programexample(input,output)；Vara:array[1..20]ofreal；temp:real；i,j:integer；BeginFori:=1to20do{读入20个元素}read(a[i])；Fori:=1to19do{从最后一个到第二个依次确定每个数}Forj：=1to20-ido{实现相邻两位数的置换}Ifa[j]a[j+1]ThenBegintemp:=a[j]；a[j]：=a[j+1]；a[j+1]:=tempEnd；Fori:=1to20do{输出排序后的结果}Beginwrite(a[i])；Ifimod5=0ThenwritelnEnd；End.上面的这三种程序的比较次数都是190次，因为19+18+17+…+1=((19+1)/2)*19=190次在上面冒泡排序的例子中，我们可以看到，在比较完第二趟之后，数组已经排好序，但计算机并不知道，它还要继续进行第三、第四、第五趟。我们可以做一下改进，如果在某一趟的比较中没有发现任何数据交换，则知道已排好序，可以不用再进行比较了，因此第三趟还需要进行，第四趟、第五趟比较则是不必要的。最完美的是这样一种情况，如果读入的数是排好序的，则只需要进行一趟比较（19次）就可以了，而不用进行19趟（190次）比较了。为了标志在比较的过程中是否发生了数据交换，我们可以定义一个布尔型的变量flag，以此来判断是否有数据交换。循环中先把flag置为true，如果有数据交换，在交换之后将flag置为false，最后判断如果flag仍为true，则说明已经排好顺序，循环退出，输出结果。由于不确定到底循环多少次，我们可以使用repeat语句。改进的选择程序如下：Programexample(input,output)；Vara:array[1..20]ofreal；temp:real；i,j:integer；flag:boolean；{添加了一个标志变量flag}BeginFori:=1to20do{读入20个元素}read(a[i])；i:=1；Repeat{不确定需要循环多少次,所以用Repeat语句}Flag:=true；Forj：=1to20-ido{实现相邻两位数的置换}Ifa[j]a[j+1]ThenBegintemp:=a[j]；a[j]：=a[j+1]；a[j+1]:=tempflag:=falseEnd；i:=i+1；Untilflag；Fori:=1to20do{输出排序后的结果}write(a[i])；End；End.例子：输入20个数，将它们按照从高到低的次序排列以后输出。方法三：插入排序插入排序的基本思想:从第2个数开始取出,从其前一个元素向前依次和它比较,如果遇到比它小的,就将小的数据向后移动一个位置,从而插入到它前面已经排好序的数列中去。如此继续，每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。比如:a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]573461982取出第2个数753461982取出第3个数753461982取出第4个数754361982取出第5个数765431982取出第6个数765431982取出第7个数976543182取出第8个数987654312取出第9个数987654321参考程序如下：Programexample(input,output)；Vara:array[1..20]ofreal；t:real；{定义一个用于放置取出元素的变量}i,j:integer；BeginFori:=1to20do{读入20个元素}read(a[i])；Fori:=2to20do{从第二个数开始取出}Begint:=a[i]；j:=i-1；while(j0)and(a[j]t)do{依次将它前面比它小的数向后移动一个位置}begin问题：条件可不可以写成(a[j]t)and(j0)，为什么？a[j+1]:=a[j]；j:=j-1；end；a[j+1]:=t；{遇到不比它小的数之后，将取出的数据放置在此数之后}end；Fori:=1to20do{输出排序后的结果}write(a[i])；End.以上三种方法比较简单，属于简单排序。下面介绍一种比较复杂的高级排序方法：例子：输入20个数，将它们按照从高到低的次序排列以后输出。方法四：快速排序算法快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的左右两部分，其中一部分的所有数据都比另外一部分的所有数据要小，而另一部分的所有数据都比前一部分的所有数据要大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，直到每一个待处理的序列的长度为1,处理结束。具体操作：假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。比如：A[1]A[2]A[3]A[4]A[5]A[6]A[7]49386527761397一趟快速排序之后97766549132738一趟快速排序的算法是：1）设置两个变量I、J，排序开始的时候I：=1，J：=N；2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；3）从J开始向前搜索，即由后开始向前搜索（J:=J-1），找到第一个大于X的值，两者交换；4）从I开始向后搜索，即由前开始向后搜索（I:=I+1），找到第一个小于X的值，两者交换；5）、重复第3、4步，直到I=J；例如：待排序的数组A的值分别是：（初始关键数据X：=49）A[1]A[2]A[3]A[4]A[5]A[6]A[7]49386527761397从后搜，交换前I=1;J=7；交换后I=2;J=797386527761349从前搜，交换前I=2;J=7；交换后I=2;J=697496527761338从后搜，交换前I=2;J=6；交换后I=3;J=597766513492738从前搜，交换前I=3;J=5；交换后I=4;J=597766549132738从后搜，当I=4;J=4结束经过一趟快速排序之后的结果是：97766549132738，即所有大于49的数全部在49的前面，所有小于49的数全部在49的后面。一趟快速排序的程序段：x:=a[i];repeatwhile(a[j]x)and(ji)do{从后往前搜索比x大的数}j:=j-1;ifjithen{找到比x大的数后和前面的数进行交换}beginw:=a[i];a[i]:=a[j];a[j]:=w;i:=i+1;{交换之后i的值应该增加，定位到后一个}end;while(a[i]x)and(ij)do{从前往后搜索比x小的数}i:=i+1;ifijthenbeginw:=a[j];a[j]:=a[i];a[i]:=w;j:=j-1;{交换之后j的值应该减少，定位到前一个}enduntili=j;整个快速排序过程的实现：利用分治思想（即大化小的策略）可进一步对分开的两组数据再次分别进行快速排序，照此继续，直到分组对象只有一个数据为止。我们可以将一趟快速排序写成过程，快速排序就是递归调用此过程。在上面的例子中，以4