排序算法PPT课件

.,1,排序算法专题,甘肃省白银市平川区第三中学张民辉,.,2,主要内容:,一、选择排序,二、插入排序,三、冒泡排序,四、合并排序,五、快速排序,七、计数排序,六、桶排序,其它的排序：堆排序，留在后面介绍,.,3,排序就是把一组无序的关键字，通过算法变成一组有序的关键字。,一、选择排序,算法思想：对于一组关键字K1,K2,Kn,首先从K1,K2,Kn中选择最小值,假如它是Ki,则将Ki与K1对换,然后从K2,K3,Kn中选择最小值Ki,再将Ki与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1、Kn中选择最小值Ki将Ki与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成.即:在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。,.,4,举例：对下面一组关键字，要求按照从大到小排序a1a2a3a4a5a6a71328749,9123748,从A1到a7找最大的数,9812347,从A2到a7找最大的数,9871234,从A3到a7找最大的数,9874123,从A4到a7找最大的数,9874312,从A5到a7找最大的数,9874321,从A6到a7找最大的数,9874321,排序结束,.,5,for(i=1;iai)a0=ai;ai=aj;aj=a0;,核心代码,该算法缺点就是元素交换的次数太多。改进算法：for(i=1;i=n;i+)k=i;for(j=i+1;j=k;j-)aj+1=aj;ak=m;,程序采用了边读入边插入的方法。兰色部分为后面元素后移。,.,8,三、冒泡排序,算法思想：让j取1至n-1,将rj与rj+1比较,如果rjrj+1,则把记录rj与rj+1交换位置,否则不进行交换.最后是rn-1与rn比较，关键字较小的记录就换到rn的位置上,到此第一趟冒泡结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的最后.(2)让j取1至n-2,重复上述的比较对换操作,最终rn-1之中存放的是剩余n-1个记录(rn除外)中关键字最小的记录.(3)让j取1至2,经过一系列对联对比交换之后,r3之中是剩余若干记录中关键字最小的记录.(4)让j取1至1,将r1与r2对比,把关键字较小的记录交换到r2之中。至此，经过n-1次冒泡，r1到rn中的数就成了有序的数。,.,9,举例：对下面一组关键字，要求按照从大到小排序a1a2a3a4a5a6a71328749,3287491,3874921,第一趟,第二趟,第三趟,第四趟,第五趟,第六趟,排序结束,8749321,8794321,8974321,9874321,9874321,.,10,for(inti=1;in;i+)for(intj=1;j=n-i;j+)if(ajn;for(inti=1;iai;mergesort(1,n);for(inti=1;i=n;i+)coutai;coutendl;system(pause);return0;,.,14,五、快速排序,在待排序的n个记录中任取一个记录(通常取第一个记录)，把该记录放入最终位置后，整个数据区间被此记录分割成两个子区间。所有关键字比该记录关键字小的放置在前子区间中,所有比他大的放置在后子区间中，并把该记录排在这个两个子区间的中间，这个过程称为一趟快速排序。之后对所有的两个子区间分别重复上述过程,直至每个子区间内只有一个记录为止。一趟快排的做法：设两个指示器i和j，他们的初值分别为指向无序区中的第一个和最后一个记录。假设无序区中记录为Rst，则i的初值为s,j的初值为t，首先将Rmid移至临时变量tmp中作为基准，令j自t起向左扫描直至Rjtmp时，将Ri移至j所指的位置上，依次重复直至i=j，此时所有Rk(k=s,s+1,j-1)的关键字都小于tmp而所有Rk(k=j+1,j+2,t)的关键字必大于tmp，则可将tmp中的记录移至i所指位置Ri，它将无序中记录分割成Rsj-1和Rj+1t，以便分别进行排序。,.,15,voidqsort(intx,inty)inttmp;inth=x,r=y;tmp=a(h+r)/2);while(htmp)r-;if(hh)qsort(h,y);return;,核心代码：,.,16,六、桶排序,基本思想：若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。注：桶排序不是基于关键字值比较的排序。,例：对1、3、5、7、2、0、60、100、40、60排序,思路：用上述待排序的数，作为数组下标。对于上面的数，定义一个A101,数组开始每个元素的值为0。在读入数据的过程中，如果读入1令a1加1，读入3，令a3加1，依此处理。得到一个数组A。然后，i从0到100进行如下处理：for(inti=0;i0)coutin;for(i=1;itmp;atmp+;for(i=0;i0)/可能有多个相同的关键字couti;ai-;coutn;/输入nfor(i=1;iai;memset(c,0,sizeof(c);for(i=1;i=n;i+)/类似桶排序cai+;for(i=2;i=n;i+)/统计比i小的数的个数ci+=ci-1;,.,1