冒泡排序算法

冒泡排序算法 在解释冒泡排序算法之前，先来介绍把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个数据来说明以上的算法。 假设6个数据是：A[]=5 7 4 3 8 6 A[1] A[2] A[3] A[4] A[5] A[6] 5 7 4 3 8 6 第一次，A[1]=5和A[2]=7比较，7>5，不进 行对调。 5 7 4 3 8 6 第二次，A[2]=7和A[3]=4比较，4<7，进行对调， 那么第二次比较完后的数据是5 4 7 3 8 6 5 4 7 3 8 6 第三次，A[3]=7和A[4]=3比较，3<7，进行对调， 那么第三次比较完后的数据是5 4 3 7 8 6 5 4 3 7 8 6 第四次，A[4]=7和A[5]=8比较，8>7,不进行对调。 5 4 3 7 8 6 第五次，A[6]=6和A[5]=8比较，6<8，进行对调， 那么第五次也就是最后一次的结果 是 5 4 3 7 6 8 由上例可以看出，对于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]中， 每重复一次两两比较后，比较的范围就朝前移动一个位置，此算法经过N-1次就完成了 A[1]到A[N]中的的数由小到大的排列。 由此可以看出，冒泡法的基本思想就是：在待排序的数据中，先找到最小（大）的 数据将它放到最前面，再从第二个数据开始，找到第二小（大）的数据将它放到第二个 位置，以此类推，直到只剩下最后一个数为止。这种排序方法在排序的过程中，是小的 数就如气泡一样逐层上浮，而使大的数逐个下沉，于是就形象地取名为冒泡排序，又名 起泡排序。 冒泡排序可用图3所示的流程图表示： 开 始 J：=1 I：=1 N A[I]>A[I+1] A[I]与A[I+1]对调 Y I：=I+1 I>N--J N Y J：=J+1 N J>N--1 Y 结 束 图3 冒泡排序算法程序流程图 程序举例： 程序要求： 从键盘输入十个数，然后按从小到大的顺序输出。 程序代码： program bubble(input,output); const n=10; type colarr=array[1..n] of integer; var a:colarr; t,i,j:integer; begin writeln(‘INPUT 10 integer num:’); for I:=1 to n do read(a[I]); readln; for j:=1 to n-1 do for I:=1 to n-j do if a[I]>a[I+1] then begin t:=a[I];a[I]:=a[I+1];a[I+1]:=t end; writeln(‘OUTPUT new num:’); for I:=1 to n do begin write(a[I]:4); if I mod 5=0 then writeln end; end. 程序运行结果如下： input 10 integer num: {提示输入10个数} 7 6 23 21 19 18 10 16 5 13 {假如输入的数据} output new num: {冒泡排序后输出结果} 5 6 7 10 13 16 18 19 21 23 在介绍选择排序法之前先介绍一种把最小的数放在第一个位置上的算法，当然也 可以用前面所讲的冒泡排序法，现在我们改用一种新的算法：其指导思想是先并不急于 调换位置，先从A[1]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A[P]和A[1]对调，这时A[1]到A[10]中最小的数据就换到了最前面的位置。 算法的步骤如下： 1）、先假设A[1]中的数最小，记下此时的位置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]中去了，也就是在最前面了。 如果现在重复此算法，但每重复一次，进行比较的数列范围就向后移动一个位置。 即第二遍比较时范围就从第2个数一直到第N个数，在此范围内找最小的数的位置P， 然后把A[P]与A[2]对调，这样从第2个数开始到第N个数中最小数就在A[2]中了，第 三遍就从第3个数到第N个数中去找最小的数，再把A[P]与A[3]对调……此过程重复 N-1次后，就把A数组中N个数按从小到大的顺序排好了。这种排序的方法就是 J>N--1 。以上算法可以用图4表示： J：=1 P：=J I>N A[I]X N N I:= I+1 I>N--1 Y N Y A[J]:=A[J-1] ;=A[I] J=I J:=J--1 J:=N+1 A[I]：=X 结 束 图5 插入排序算法程序流程图 按照上述流程图写出的代码如下： program charu(input,output); var a:array[1..11] of integer; x,I,j,n:integer; f:Boolean; Begin {给数组赋一个已经排序好的初值,设A[1]到A[10]分别等于1到 10} For I:=1 to 10 do A[I]:=I； Writeln(‘数组原来的排列值是：’)； For I:=1 to 10 do write（a[I]:4）; Writeln; Writeln(‘输入一个整数:’); Readln(x); F:=false; I：=0；N：=10； Repeat I:=I+1; If a[I]>x then f:=ture; Until I>n or f=ture; J:=n+1; While j<>I do begin A[j]:=a[j-1]; J:=j-1 End; A[I]:=x; Writeln(‘ 插入一个数后的数组排列值是:’); For I:=1 to n+1 do Write(a[I]:4) End. 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排 序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的 所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个 排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个 数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它 后面，这个过程称为一趟快速排序。一趟快速排序的算法是： 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]： 49 38 65 97 76 13 27 进行第一次交换后： 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找X的值，65>49,两者交换，此时I：=3 ) 进行第三次交换后： 27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找49,两者交换，此时J：=4 ) 此时再执行第三不的时候就发现I=J，从而结束一趟快速排序，那么经过一趟 快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。 快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对 前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最 后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过 程如图6所示： 初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序 {13} 27 {38} 结束 结束 {49 65} 76 {97} 49 {65} 结束 结束 图6 快速排序全过程 1、设有N（假设N=10）个数，存放在S数组中； 2、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]； 3、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进 行快速排序直到分组对象只有一个数据为止。 如具体数据如下，那么第一躺快速排序的过程是： 数组下标： 1 2 3 4 5 6 7 8 9 10 45 36 18 53 72 30 48 93 15 36 I J （1） 36 36 18 53 72 30 48 93 15 45 （2） 36 36 18 45 72 30 48 93 15 53 （3） 36 36 18 15 72 30 48 93 45 53 （4） 36 36 18 15 45 30 48 93 72 53 （5） 36 36 18 15 30 45 48 93 72 53 通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1..5]和S[6..10]分别进行 快速排序。程序代码如下： program kuaisu(input,output); const n=10; var s:array[1..10] of integer; k,l,m:integer; procedure qsort(lx,rx:integer); var I,j,t:integer; Begin I:lx;j:rx;t:s[I]; Repeat While (s[j]>t) and (j>I) do Begin k:=k+1; j:=j-1 end; if I End.