排序算法1.ppt

排序算法及应用排序算法及应用为什么要学排序数据获取后通常需要进行处理，处理后的数据其目的是便于人们的应用。数据处理方法有多种，通常有数据的排序，查找，插入，删除，归并等操作。排序就显得极为重要。本章重点介绍数据排序的几种方法。什么是排序？什么是排序？排序是处理数据过程中一种很常用的运算，是将一组原本无序的数据元素，通过一定的方法，按照某个域的值（关键字）递增或递减的次序重新排列的过程。排序的目的之一是为了方便查找：对无序数据进行查找的时间复杂度为O(n)；在排序的基础上进行查找，其时间复杂度为O(logn)。排序的分类：排序的分类：根据排序过程中是否使用外存储器，可以把排序分为外排序和内排序。下面主要讨论几种常见的内排序算法：选择排序、冒泡排序、插入排序、快速排序和堆排序。什么是稳定性？当待排序的数值或记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。如果序列中关键字相同的多个记录经过某种排序方法进行排序之后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例如：有一组记录的关键字为（23，85，72，58，23，40），其中关键字同为23的记录有两个（为了区分，后一个23带有下划线），如果一种排序算法使排序后的结果是（23，23，40，58，72，85），则此方法是稳定的；如果另一种排序算法使排序后的结果是（23，23，40，58，72，85），则此方法是不稳定的，1.选择排序选择排序是一种简单的排序方法。其基本思想是：把待排序的n个元素看作一个有序部分和一个无序部分。开始时有序部分为空，无序部分包含n个元素。排序时每次从无序部分中选出最小的元素，把它与无序部分的第一个元素交换位置，那么该元素必大于（或等于）有序部分中的所有元素，从而使有序部分元素个数增1，无序部分元素个数减1。经过n-1次选择和交换后，有序部分有n-1个元素，无序部分只有1个元素，且该元素大于（或等于）有序部分中的所有元素，整个排序过程结束。初始关键字：2252204119024218542231第一趟排序后：4122022519024218542231第二趟排序后：4142225190242185220231第三趟排序后：4142185190242225220231第四趟排序后：4142185190242225220231第五趟排序后：4142185190220225242231第六趟排序后：4142185190220225242231第七趟排序后：4142185190220225231242排序过程演示programselectsort;constmx=10000;vard:array1.mxoflongint;n,i,j,k,t:longint;beginreadln(n);fori:=1tondoread(di);fori:=1ton-1dobegink:=i;forj:=i+1tondo/dk为di.dn的最小元素ifdjdkthenk:=j;t:=dk;dk:=di;di:=t;/交换end;fori:=1tondowriteln(di);end.可见，选择排序的时间复杂度为O(n2)的，需要进行n*(n-1)/2次比较和n-1次交换。优化：分析上面的排序过程可以发现，如果di是di.dn中的最小值，即k=i,那么不需要交换dk和di。programselectpro;constmx=10000;vard:array1.mxoflongint;n,i,j,k:longint;beginreadln(n);fori:=1tondoread(di);fori:=1ton-1dobegink:=i;forj:=i+1tondo/dk为di.dn的最小元素ifdjdkthenk:=j;ifkithen/交换beginj:=dk;dk:=di;di:=j;end;end;fori:=1tondowriteln(di);end.可见，选择排序至多需要n-1次交换。2.冒泡排序冒泡排序也是一种简单的排序方法。其基本思想是：通过相邻元素相邻元素之间的比较和交换使较小的元素逐渐从后向前移动，就像水底的气泡一样逐渐向上冒。具体过程如下：首先比较dn和dn-1，若dndn-1，则交换，使较小的元素前移，较大的元素后移；接着比较dn-1和dn-2，以此类推，直到比较d2和d1并使较小的元素前移，第一趟排序结束,则d1为最小的元素。然后在d2.dn间进行第二趟排序，使第二小元素前移到d2位置；n-1趟排序后，整个冒泡排序结束。初始关键字：2252204119024218542231不交换d8和d7：2252204119024218542231交换d7和d6：2252204119024242185231交换d6和d5：2252204119042242185231交换d5和d4：2252204142190242185231不交换d4和d3：2252204142190242185231交换d3和d2：2254122042190242185231交换d2和d1：4122522042190242185231排序过程演示第一趟排序后：4122522042190242185231第二趟排序后：4142225220185190242231第三趟排序后：4142185225220190231242第四趟排序后：4142185190225220231242第五趟排序后：4142185190220225231242第六趟排序后：4142185190220225231242第七趟排序后：4142185190220225231242programmaopaosort;constmx=10000;vard:array1.mxoflongint;n,i,j,k:longint;beginreadln(n);fori:=1tondoread(di);fori:=1ton-1doforj:=n-1downtoidoifdj+1djthenbegin/相邻元素交换k:=dj;dj:=dj+1;dj+1:=k;end;fori:=1tondowriteln(di);end.可见，其时间复杂度也是O(n2)的。不难发现，如果某趟排序中没有发生交换，就意味着任意两个相邻元素都是有序的，那么全部元素就已经有序了。所以该算法可以改进如下：programmaopao1;constmx=10000;vard:array1.mxoflongint;n,i,j,k:longint;sorted:boolean;/是否有序beginreadln(n);fori:=1tondoread(di);sorted:=false;i:=1;whilenotsorteddobeginsorted:=true;/假定已有序forj:=n-1downtoidoifdj+10)and(djk)dobegindj+1:=dj;j:=j-1;end;dj+1:=k;end;fori:=1tondowriteln(di);end.可见，其时间复杂度为O(n2)，需要至多n*(n-1)/2次、至少n-1次比较，至多n*(n-1)/2次、至少0次的移动。可以通过折折半查找半查找的方法来确定新元素在有序部分中的位置，以提高效率。4.桶排序桶排序 桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值（当然也可以装入若干个值），顺序输出各桶的值，将得到有序的序列。例：输入n个0到100之间的不相同整数，由小到大排序输出。program ex_1;var b:array0.100 of integer;k:0.100;i:integer;Begin readln(n);write(Enter date:(0-100);for i:=0 to 100 do bi:=0;/初始化 for i:=1 to n do begin read(k);bk:=bk+1;/将关键字等于k的值全部装入第k桶中 end;writeln(Output data:);for i:=0 to 100 do while bi0 do begin write(i:6);bi:=bi-1 end;/输出排序结果 writeln;end.5.快速排序快速排序是一种基于分治策略的排序方法。其基本思想是：首先从待排序区间（初始时为1.n）中选取一个元素(方便起见，一般是选取区间内的第一个元素)作为基准元素，然后从两端向中间依次进行比较和交换，把位于基准元素之前且比基准元素大的交换到后面，把位于基准元素之后且比基准元素小的交换到前面，直至基准元素位于前后两部分的交界处。这样前面部分的所有元素都小于等于基准元素，后面部分的所有元素均大于等于基准元素，基准元素的所在位置就是排序后的最终位置。然后再对基准元素的前后两个区间分别进行快速排序，直至每个区间为空或只包含一个元素，整个快速排序结束。排序过程演示初始关键字：2252204119024218542231(1.8)225(6)4222041190185(1.5)242231(7.8)231(7)242(8)41(1)42(2)220190185(3.5)185190(3.4)220(5)185(3)190(4)取首快排programquicksort1;constmx=10000;varn,i:longint;d:array1.mxoflongint;procedureqsort(head,tail:longint);varx,i,j:longint;beginx:=dhead;i:=head;j:=tail;whileijdobeginwhile(i=x)doj:=j-1;di:=dj;while(ij)and(di=x)doi:=i+1;dj:=di;end;di:=x;ifheadj-1thenqsort(head,j-1);ifi+1tailthenqsort(i+1,tail);end;beginreadln(n);fori:=1tondoread(di);qsort(1,n);fori:=1tondowriteln(di);end.更优秀的快排取中快排ProcedureQs(l,r:longint);Vari,j,x,y:longint;Begini:=l;j:=r;x:=a(l+r)div2;repeatwhileaixdoinc(i);whilexj)thenbeginy:=ai;ai:=aj;aj:=y;inc(i);dec(j);end;untilij;ifljthenQs(l,j);ifirthenQs(i,r);End;随机化快排proceduresort(l,r:longint);vari,j,x,y:longint;begini:=l;j:=r;x:=arandom(r-l+1)+l;repeatwhileaixdoinc(i);whilexj)thenbeginy:=ai;ai:=aj;aj:=y;inc(i);j:=j-1;end;untilij;ifljthensort(l,j);ifirthensort(i,r);end;理想情况下，基于分治策略的二等分，快速排序的时间复杂度为O(nlogn)，但如果基准元素不能将整个区间平均的分成两个大小相等的区间，实际的时间复杂度会更大。例如当基准元素每次都把大区间s.t分成一个空的区间和一个含有（t-s）个元素的区间时，其时间复杂度退化为O(n2)。对于这一现象，可以采用随机选择基准元素的方法加以改进：随机选择区间ds.t中的元素dr作为基准元素，如果drds，则交换dr和ds，然后进行快速排序。这样，快速排序的时间复杂度退化的概率会大大降低。6.归并排序归并排序将两个或两个以上有序的数列(或有序表)，合并成一个仍然有序的数列(有序表)，这种操作称为归并操作。这样的方法经常用于多个有序的数据文件归并成一个有序的数据文件。若将两个有序表合并成一个有序表则称为二路归并，同理，有三路归并、四路归并等。二路归并比较简单，所以我们只讨论二路归并。例如有两个有序表:(7，10，13，15)和(4，8，19，20)，归并后得到的有序表为:(4，7，8，10，13，15，19，20)。归并过程为:比较Ai和Aj的大小，若AiAj，则将第一个有序表中的元素Ai复制到Rk中，并令i和k分别加1，即使之分别指问后一单元，否则将第二个有序表中的元素Aj复制到Rk中，并令j和k分别加1;如此循环下去，直到其中的一个有序表取完,然后再将另一个有序表中剩余的元素复制到R中从下标k到下标t的单元.二路归并算法描述为二路归并算法描述为(As,t中的数据由小到大合并到中的数据由小到大合并到Rs,t中中):proceduremerge(s,m,t);/两个有序表As,m和Am+1,t合并成一个有序表Rs,tBegin/s是第一个有序表起点位置，m+1是第二个有序表的起点(1)i:=s;j:=m+1;k:=s;/i和j分别指向二个有序表的头部(2)while(i=m)and(j=t)doifAi=AjthenRk:=Ai;i:=i+1;k:=k+1elseRk:=Aj;j:=j+1;k:=k+1;(3)whilei=mdoRk:=Ai;i:=i+1;k:=k+1;/复制第一路剩余(4)whilej=tdoRk:=Aj;j:=j+1;k:=k+1;/复制第二路剩余end;归并排序(Mergesort)就是利用归并操作把一个无序表排列成一个有序表的过程。二路归并排序的过程是首先把待排序区间（即无序表）中的每一个元素都看作为一个有序表，则n个元素构成n个有序表，接着两两归并（即第一个表同第二个表归并，第三个表同第四个表归并，），得到n/2个长度为2的有序表（最后一个表的长度可能小于2），称此为一趟归并，然后再两两有序表归并，得到n/2/2个长度为4的有序表（最后一个表的长度可能小于4），如此进行下去，直到归并第log2n趟后得到一个长度为n的有序表为止。归并排序算法我们用递归实现，先把待排序区间s,t以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间s,t。对左右子区间的排序与原问题一样，所以我们可以调用同样的子程序，只是区间大小不一样。归并排序程序如下：归并排序程序如下：program ex_2;var a,r:array1.10000 of integer;/a是待排序数组，是待排序数组，r是临时数组是临时数组 n,i:integer;procedure mergesort(s,t:integer);/对对s,t区间的无序数据进行归并排序区间的无序数据进行归并排序var m,i,j,k:integer;begin if s=t then exit;/若区间只有一个数据就不用排了若区间只有一个数据就不用排了 m:=(s+t)div 2;/取区间的中点取区间的中点 mergesort(s,m);/以中点二分，对左边了区间进行排序以中点二分，对左边了区间进行排序 mergesort(m+1,t);/以中点二分，对右边了区间进行排序以中点二分，对右边了区间进行排序 i:=s;/以下是一次归并（合并）操作以下是一次归并（合并）操作 j:=m+1;k:=s;while(i=m)and(j=t)do /二个子序列从小大到合并，直到有一列结束二个子序列从小大到合并，直到有一列结束 begin if ai=aj then begin rk:=ai;inc(i);inc(k);end else begin rk:=aj;inc(j);inc(k);end;end;while i=m do /把左边子序列剩余的元素接入进来把左边子序列剩余的元素接入进来 begin rk:=ai;inc(i);inc(k);end;while jajthenbeginm:=ai;ai:=aj;aj:=m;end;ifai=ajthenai:=0;end;fori:=1tondoifai0thenk:=k+1;writeln(k);fori:=1tondoifai0thenwrite(ai,);close(input);close(output);End.例二车厢重组（车厢重组（carry.pas）【问题描述问题描述】在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。【输入文件输入文件】输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。【输出文件输出文件】一个数据，是最少的旋转次数。【输入样例输入样例】carry.in44321【输出样例输出样例】carry.out6就是按照先序或者后序，将最小的放在最左边，不用管途中的任何情况，然后就移动次小的，再移动更小的，直到将倒数第二个移动到位后，最后一个也移好了。所以，可以将这种思想看成是冒泡排序的一个变形把。代码constmax=10000;vara:array1.maxoflongint;m,n,s,i,j,p:longint;beginassign(input,carry.in);reset(input);assign(output,carry.out);rewrite(output);s:=0;read(m);fori:=1tomdoread(ai);fori:=1tom-1doforj:=1tom-idoifajaj+1thenbeginp:=aj;aj:=aj+1;aj+1:=p;s:=s+1;end;write(s);close(input);close(output);end.例三军事机密军事机密(Secret.pas)【问题描述问题描述】军方截获的信息由n（n=30000）个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。【输入格式输入格式】第一行n，接着是n个截获的数字，接着一行是数字k，接着是k行要输出数的序号。【输出格式输出格式】k行序号对应的数字。【输入样例输入样例】Secret.in5121112612373243【输出样例输出样例】Secret.out7123121考虑NlogN的排序varn,i,k:word;a:array1.30000oflongword;procedureqsort(l,r:longword);varpl,pr,m,t:longword;beginpl:=l;pr:=r;m:=a(l+r)shr1;repeatwhileaplmdodec(pr);ifplpr;ifpllthenqsort(l,pr);end;qsortbeginmainassign(input,secret.in);reset(input);assign(output,secret.out);rewrite(output);readln(n);fori:=1tondoread(ai);qsort(1,n);readln(k);fori:=1tokdobeginreadln(n);writeln(an);end;close(input);close(output);end.谢谢！