[电脑基础知识]数据结构9第八章：排序ppt课件

1、排序排序 主讲教师：李长云 班 级：信息系 教 室：多媒体数据构造数据构造顺序表的直接插入排序算法顺序表的直接插入排序算法如下： void zjcrpxs(int r，int n) /顺序表的直接插入排序int i，j，t； r0=min；for (i=2；i=n；i+) t=ri； j=i-1； while(tlink!=NULL) p=t-link； if(p-key)key) t-link=p-link；p-link=h；h=p； elseq=h；r=q-link； while(p-keyr-key) q=r；r=q-link； ifp=r t=p； else t-link=p-link

2、； p-link=r；q-link=p； return h； 二分插入排序算法二分插入排序算法如下： void rffpx(int r，int n) /二分插入排序 int i，j，m，t，w，x； for(i=1；in；i+) x=ri；t=0；w=i-1； while(t=w) m=t+w2； if(x=t；j- rj+1=rj； rt=x； 图 例图 例希尔排序的算法希尔排序的算法如下： void shellpx(int r，int n) /希尔排序 int x，i，j，k； k=n2； while(k=) for(i=k+1；i&(x.keyrj.key) rjk=rj；j-=

3、k； rj+k=x； k=k2； 图 例冒泡排序算法 冒泡排序算法如下： void qppx(int r，int n) /冒泡排序 int i，j，k，x； j=1；k=1； while (j) k=0； for(i=0；in-j；i+) if ri+1=wreturn；i=t；j=w；x=ri；do while(rj=x)&(jij-； if(ij)ri=rj；i+； while(rii) i+； ifijrj=ri；j-； while(ij)； ri=x； kspxdr，t，j-1； kspxd(r，j+1，w)； 图 例图 例快速排序的非递归算法 void kspxf(int r

4、，int n)/快速排序非递归算法 int k，t，w，i，j，x，s1，s2；k=0；t=0；w=n-1； dowhile(t=x)&(ij)j-； if(ij)ri=rj；i+； while(rii) i+； if(ij)rj=ri；j-；while(ij)； ri=x； if(i+1)0)t=s1k；w=s2k-；while(k|tw)； 直接选择排序的算法直接选择排序的算法如下： void zjxzpx(int r，int n) /直接选择排序 int i，j，k，x； for (i=0；in-1；j+) k=i； for(j=i+1，jn；j+ if(rjrk) k=j； i

5、f(i!=k) x=ri；ri=rk；rk=x； 树形选择排序树形选择排序图 例图 例堆排序图 例图 例堆的挑选法算法挑选法算法如下： int sift(int r，int t，int w) /用挑选法调整堆 int i，j，x；i=t； x=ri； j=2*i； while(j=w)ifjw)&(rj rj+1)j+； if(x；i-) sift(r，i，n)； for(i=n；i；i-) x=r1；r1=ri；ri=x； siftr，1，i-1； 归并排序算法void hbgc(int r，int h，int m，int w， int t) /将存于r数组中的两个首尾相接的有序子表

6、，合并成一个有序子表存于t数组中 int i，j，k； i=h；j=m+1；k=h-1； while(i=m)&(j=w) k+； if(rim while(j=w)t+k=rj+； else while(i=m) t+k=ri+； 完成一趟归并的算法完成一趟归并的算法如下void tgb(int s，int n， int r，int t)/趟归并 int i=1； while(i=n-2*s+1) hbgc(r，i，i+s-1，i+2*s-1，t)； i=i+2*s ifi(n-s+1) hbgc(r，i，i+s-1，n，t)； else while (i=n) ti=ri+； 二路

7、归并排序算法二路归并排序算法如下： llgbpx(int r，int n) /二路归并排序 int i，s=1； int tM； while(sn) tgb(s，n，r，t)；s*=2； if(sn)tgb(s，n，t，r)；s*=； else i=1；while (i=n)ri=ti+； 图 例基数排序算法 int jspx(JD r，int n，) /链式存储表示的基数排序 int i， j， k， t， p， rd， rg， f10， e10； for(i=1；in；i+) ri.link=i+1；rn.link=0；p=1；rd=1；rg=10； for (i=1；i=D；i+) fo

8、r(j=0；j)； 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； return p； 图 例图 例复习思索题 1.分别采用直接插入排序、快速排序和归并排序算法，对初始结点已按键值“根本有序陈列时，最省时间或最费时间的算法分别是哪个？在排序过程中，键值比较次数与初始结点陈列顺序无关的是哪个排序方法。 2设有5000个无序的结点，希望用最快的速度挑选出其中前10个最大键值的结点，在快速排序、堆排序和归并排序方法中，采用哪种方法最好？ 3. 对于给定的键值序列12，2，

9、16，30，8，28，4，10，分别写出直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、归并排序、堆排序和基数排序的过程，并算出比较次数和结点挪动次数。 复习思索题4. 判别以下序列能否是堆？假设不是堆，那么把它们调整成堆。 1100，85，98，77，80，60，82，40，20，10，66； 2100，98，85，82，80，77，66，60，40，20，10； 3100，85，40，77，80，60，66，98，82，10，20； 410，20，40，60，66，77，80，82，85，98，100； 5. 知k，k，kn是堆，试写一个算法将k，k，kn+1调整为堆。(提示：添加一个