排序算法

第十五讲排序算法主讲人张志刚1.选择排序选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。例1:输入序列数据按非减顺序输出.programxzpx;constn=7;vara:array[1..n]ofinteger;i,j,k,t:integer;beginwrite('Enterdate:');fori:=1tondoread(a[i]);writeln;fori:=1ton-1dobegink:=i;forj:=i+1tondoifa[j]a[k]thenk:=j;ifkithenbegint:=a[i];a[i]:=a[k];a[k]:=t;end;end;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end2.插入排序插入排序的基本思想:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置p，原来p后的元素一一向右移动一个位置,使得L[1..i]又是排好序的序列。例2:输入序列数据按非减顺序输出.programcrpx;constn=7;vara:array[1..n]ofinteger;i,j,k,t:integer;beginwrite('Enterdate:');fori:=1tondoread(a[i]);writeln;fori:=2tondobegink:=a[i];j:=i-1;while(ka[j])and(j0)dobegina[j+1]:=a[j];j:=j-1end;a[j+1]:=k;end;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.3.冒泡排序冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个记录是反序的,则进行交换,直到无反序的记录为止。例:输入序列数据按非减顺序输出。程序1:programmppx;constn=7;vara:array[1..n]ofinteger;i,j,k,t:integer;beginwrite('Enterdate:');fori:=1tondoread(a[i]);fori:=1ton-1doforj:=ndowntoi+1doifa[j-1]a[j]thenbegint:=a[j-1];a[j-1]:=a[j];a[j]:=tend;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.程序2：programmppx;constn=7;vara:array[1..n]ofinteger;i,j,k,t:integer;bool:boolean;beginwrite('Enterdate:');fori:=1tondoread(a[i]);i:=1;bool:=true;while(in)andbooldobeginbool:=false;forj:=ndowntoi+1doifa[j-1]a[j]thenbegint:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=trueend;i:=i+1;end;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.程序3：programmppx;constn=7;vara:array[1..n]ofinteger;i,j,k,t:integer;beginwrite('Enterdate:');fori:=1tondoread(a[i]);writeln;k:=n;whilek0dobeginj:=k-1;k:=0;fori:=1tojdoifa[i]a[i+1]thenbegint:=a[i];a[i]:=a[i+1];a[i+1]:=t;k:=i;end;end;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束.例:输入一组数据小到大排序.程序1:programkspv;constn=7;typearr=array[1..n]ofinteger;vara:arr;i:integer;procedurequicksort(varb:arr;s,t:integer);vari,j,x,t1:integer;begini:=s;j:=t;x:=b[i];repeatwhile(b[j]=x)and(ji)doj:=j-1;ifjithenbegint1:=b[i];b[i]:=b[j];b[j]:=t1;end;while(b[i]=x)and(ij)doi:=i+1;ifijthenbegint1:=b[j];b[j]:=b[i];b[i]:=t1;enduntili=j;b[i]:=x;i:=i+1;j:=j-1;ifsjthenquicksort(b,s,j);ifitthenquicksort(b,i,t);end;beginwrite('inputdata:');fori:=1tondoread(a[i]);writeln;quicksort(a,1,n);write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.程序2:programkspv;constn=7;typearr=array[1..n]ofinteger;vara:arr;i:integer;procedurequicksort(varb:arr;s,t:integer);vari,j,x:integer;begini:=s;j:=t;x:=b[i];repeatwhile(b[j]=x)and(ji)doj:=j-1;ifjithenbeginb[i]:=b[j];i:=i+1;end;while(b[i]=x)and(ij)doi:=i+1;ifijthenbeginb[j]:=b[i];j:=j-1;enduntili=j;b[i]:=x;i:=i+1;j:=j-1;ifsjthenquicksort(b,s,j);ifitthenquicksort(b,i,t);end;beginwrite('inputdata:');fori:=1tondoread(a[i]);writeln;quicksort(a,1,n);write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.希尔排序基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用：d1=ndiv2,di=di-1div2；i=2,3,4.....其中n为待排序序列的长度。程序1:(子序列是插入排序)programxepx;constn=7;typearr=array[1..n]ofinteger;vara:arr;i,j,t,d:integer;bool:boolean;beginwrite('inputdata:');fori:=1tondoread(a[i]);writeln;d:=n;whiled1dobegind:=ddiv2;forj:=d+1tondobegint:=a[j];i:=j-d;while(i0)and(a[i]t)dobegina[i+d]:=a[i];i:=i-d;end;a[i+d]:=t;end;end;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.程序2:(子序列是冒泡排序)programxepx;constn=7;typearr=array[1..n]ofinteger;vara:arr;i,temp,d:integer;bool:boolean;beginwrite('inputdata:');fori:=1tondoread(a[i]);writeln;d:=nwhiled1dobegind:=ddiv2;repeatbool:=true;fori:=1ton-ddoifa[i]a[i+d]thenbegintemp:=a[i];a[i]:=a[i+d];a[i+d]:=temp;bool:=falseend;untilbool;end;write('outputdata:');fori:=1tondowrite(a[i]:6);writeln;end.归并排序归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。1.二路归并例1:将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表L.programgb;constm=3;n=7;typearrl1=array[1..m]ofinteger;arrl2=array[1..n]ofinteger;arrl=array[1..m+n]ofinteger;vara:arrl1;b:arrl2;c:arrl;i,j,k,r:integer;beginwrite('Enterl1(sorted):');fori:=1tomdoread(a[i]);write('Enterl2(sorted):');fori:=1tondoread(b[i]);i:=1;j:=1;k:=0;while(i=m)and(j=n)dobegink:=k+1;ifa[i]=b[j]thenbeginc[k]:=a[i];i:=i+1;endelsebeginc[k]:=b[j];j:=j+1;end;end;ifi=mthenforr:=itomdoc[m+r]:=a[r];ifj=nthenforr:=jtondoc[n+r]:=b[r];writeln('Outputdata:');fori:=1tom+ndowrite(c[i]:5);writeln;end.2.归并排序programgbpx;constmaxn=7;typearr=array[1..maxn]ofinteger;vara,b,c:arr;i:integer;proceduremerge(r:arr;l,m,n:integer;varr2:arr);vari,j,k,p:integer;begini:=l;j:=m+1;k:=l-1;while(i=m)and(j=n)dobegink:=k+1;ifr[i]=r[j]thenbeginr2[k]:=r[i];i:=i+1endelsebeginr2[k]:=r[j];j:=j+1endend;ifi=mthenforp:=itomdobegink:=k+1;r2[k]:=r[p]end;ifj=nthenforp:=jtondobegink:=k+1;r2[k]:=r[p]end;end;proceduremergesort(varr,r1:arr;s,t:integer);vark:integer;c:arr;beginifs=tthenr1