程序设计-排序算法

《程序设计-排序算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、冒泡排序算法在解释冒泡排序算法之前，先来介绍把10个数（放在数组A中）中最大的那个数放在最后位置上的一种算法。算法描述如下：（1）从数组A[1]到A[10]，把相临的两个数两两进行比较。即A[1]和A[2]比较，比较完后A[2]再与A[3]比较，……最后是A[9]和A[10]比较。(2)在每次进行比较的过程中，如果前一个数比后一个数大，则对调两个数，也就是说把较大的数调到后面，较小的调到前面。比如在第一次的比较中，如果A[1]比A[2]大则A[1]和A[2]的值就互换。下图用6个数据来说明以上的

2、算法。假设6个数据是：A[]=574386A[1]A[2]A[3]A[4]A[5]A[6]574386第一次，A[1]=5和A[2]=7比较，7>5，不进行对调。574386第二次，A[2]=7和A[3]=4比较，4<7，进行对调，那么第二次比较完后的数据是547386547386第三次，A[3]=7和A[4]=3比较，3<7，进行对调，那么第三次比较完后的数据是543786543786第四次，A[4]=7和A[5]=8比较，8>7,不进行对调。543786第五次，A[6]=6和A[5]=8比较

3、，6<8，进行对调，那么第五次也就是最后一次的结果是543768由上例可以看出，对于6个数，排好一个数（最大的数）需要进行5次比较，可以推断出，对于N个数，一趟需要N-1次比较操作， 上述算法已经把N个数中最大的数放到了A[N]中，再重复上述算法，把A[1]到A[N-1]中最大的数放到A[N-1]中，这样A[N-1]中存放的就是第二大的数，接着把A[1]到A[N-2]中最大的数放到A[N-2]中，……最后把A[1]到A[2]中大的那个数放到A[2]中，每重复一次两两比较后，比较的范围就朝前移动一

4、个位置，此算法经过N-1次就完成了A[1]到A[N]中的的数由小到大的排列。注意：如果要由大到小排列则在比较时前一个数比后一个数小就进行对调，方法相反。由此可以看出，冒泡法的基本思想就是：在待排序的数据中，先找到最小（大）的数据将它放到最前面，再从第二个数据开始，找到第二小（大）的数据将它放到第二个位置，以此类推，直到只剩下最后一个数为止。这种排序方法在排序的过程中，是小的数就如气泡一样逐层上浮，而使大的数逐个下沉，于是就形象地取名为冒泡排序，又名起泡排序。冒泡排序可用图3所示的流程图表示：  

5、 开始J：=1I：=1    N A[I]>A[I+1]A[I]与A[I+1]对调YI：=I+1   I>N--JNY　J：=J+1　NJ>N--1Y结束 图3冒泡排序算法程序流程图程序举例：程序要求：从键盘输入十个数，然后按从小到大的顺序输出。程序代码：programbubble(input,output);constn=10;typecolarr=array[1..n]ofinteger;vara:colarr;t,i,j:integer;beginwriteln(‘INPUT10integ

6、ernum:’);forI:=1tondoread(a[I]);readln;forj:=1ton-1doforI:=1ton-jdoifa[I]>a[I+1]thenbegint:=a[I];a[I]:=a[I+1];a[I+1]:=tend;writeln(‘OUTPUTnewnum:’);forI:=1tondobeginwrite(a[I]:4);ifImod5=0thenwritelnend;end.程序运行结果如下：input10integernum:{提示输入10个数}762321

7、19181016513{假如输入的数据}outputnewnum:{冒泡排序后输出结果}56710131618192123　选择排序算法在介绍选择排序法之前先介绍一种把最小的数放在第一个位置上的算法，当然也可以用前面所讲的冒泡排序法，现在我们改用一种新的算法：其指导思想是先并不急于调换位置，先从A[1]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A[P]和A[1]对调，这时A[1]到A[10]中最小的数据就换到了最前面的位置。算法的步骤如下：1）、先假设A[1]中的数最

8、小，记下此时的位置P=1；2）、依次把A[P]和A[I]（I从2变化到10）进行比较，每次比较时，若A[I]的数比A[P]中的数小，则把I的值赋给P，使P总是指向当前所扫描过的最小数的位置，也就是说A[P]总是等于所有扫描过的数最小的那个数。在依次一一比较后，P就指向10个数中最小的数所在位置，即A[P]就是10个数中最小的那个数；3）把A[P]和A[1]的数对调，那么最小的数就在A[1]中去了，也就是在最前面了。如果现在重复此算法，但每重复一次，进行比较的数列范围就向后移动一个位置。即第二遍比