电脑基础知识数据结构9排序.ppt

排序,主讲教师：李长云班级：信息系教室：多媒体,数据结构,顺序表的直接插入排序算法,顺序表的直接插入排序算法如下：voidzjcrpxs(intr，intn)/顺序表的直接插入排序inti，j，t；r0=min；for(i=2；ilink；if(p-key)key）)t-link=p-link；p-link=h；h=p；elseq=h；r=q-link；while(p-key）（r-key）)q=r；r=q-link；if（p=r）t=p；elset-link=p-link；p-link=r；q-link=p；returnh；,二分插入排序算法,二分插入排序算法如下：voidrffpx(intr，intn)/二分插入排序inti，j，m，t，w，x；for(i=1；i=t；j-）rj+1=rj；rt=x；,图例,图例,希尔排序的算法,希尔排序的算法如下：voidshellpx(intr，intn)/希尔排序intx，i，j，k；k=n2；while(k=)for(i=k+1；i）&(x.keyrj.key)rjk=rj；j-=k；rj+k=x；k=k2；,图例,冒泡排序算法,冒泡排序算法如下：voidqppx(intr，intn)/冒泡排序inti，j，k，x；j=1；k=1；while(j)）k=0；for(i=0；i=x)&(ji）j-；if(ii)i+；if（ij）rj=ri；j-；while(i）|（tw）)；,直接选择排序的算法,直接选择排序的算法如下：voidzjxzpx(intr，intn)/直接选择排序inti，j，k，x；for(i=0；in-1；j+)k=i；for(j=i+1，jn；j+if(rjrk)k=j；if(i!=k)x=ri；ri=rk；rk=x；,树形选择排序,树形选择排序,图例,图例,堆排序,图例,图例,堆的筛选法算法,筛选法算法如下：intsift(intr，intt，intw)/用筛选法调整堆inti，j，x；i=t；x=ri；j=2*i；while(j=w)if（jw)&(rj；i-)x=r1；r1=ri；ri=x；sift（r，1，i-1）；,归并排序算法,voidhbgc(intr，inth，intm，intw，intt)/将存于r数组中的两个首尾相接的有序子表，合并成一个有序子表存于t数组中inti，j，k；i=h；j=m+1；k=h-1；while(im）while(j=w)t+k=rj+；elsewhile(i=m)t+k=ri+；,完成一趟归并的算法,完成一趟归并的算法如下voidtgb(ints，intn，intr，intt)/趟归并inti=1；while(i=（n-2*s+1）)hbgc(r，i，i+s-1，i+2*s-1，t)；i=i+2*sif（i(n-s+1)）hbgc(r，i，i+s-1，n，t)；elsewhile(i=n)ti=ri+；,二路归并排序算法,二路归并排序算法如下：llgbpx(intr，intn)/二路归并排序inti，s=1；inttM；while(sn)tgb(s，n，r，t)；s*=2；if(sn)tgb(s，n，t，r)；s*=；elsei=1；while(i=n)ri=ti+；,图例,基数排序算法,intjspx(JDr，intn，)/链式存储表示的基数排序inti，j，k，t，p，rd，rg，f10，e10；for(i=1；i)；j=0；while(fj=)j=j+1；p=fj；t=ej；for(k=j+1；k0)rt.link=fk；t=ek；rt.link=0；rg*=10；rd*=10；returnp；,图例,图例,复习思考题,1.分别采用直接插入排序、快速排序和归并排序算法，对初始结点已按键值“基本有序”排列时，最省时间或最费时间的算法分别是哪个？在排序过程中，键值比较次数与初始结点排列顺序无关的是哪个排序方法。2设有5000个无序的结点，希望用最快的速度挑选出其中前10个最大键值的结点，在快速排序、堆排序和归并排序方法中，采用哪种方法最好？3.对于给定的键值序列12，2，16，30，8，28，4，10，分别写出直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、归并排序、堆排序和基数排序的过程，并算出比较次数和结点移动次数。,复习思考题,4.判断下列序列是否是堆？若不是堆，则把它们调整成堆。（1）100，85，98，77，80，60，82，40，20，10，66；（2）100，98，85，82，80，77，66，60，40，20，10；（3）100，85，40，77，80，60，66，98，82，10，20；（4）10，20，40，60，66，77，80，82，85，98，100；5.已知k，k，kn是堆，试写一个算法将k，k，kn+1调整为堆。(提示：增加一个kn+1后，应从叶子向根方向调整)。6.一个线性表元素由正整