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

排序,主讲教师：李长云 班 级：信息系 教 室：多媒体,数据结构,顺序表的直接插入排序算法,顺序表的直接插入排序算法如下： void zjcrpxs(int r，int n) /顺序表的直接插入排序 int i，j，t； r0=min； for (i=2；i=n；i+) t=ri； j=i-1； while(trj) rj+1=rj-； rj+1=t； ,图 例,单链表表示的直接插入排序算法,用单链表表示的直接插入排序算法如下： JD* zjcrpxl(JD *h)/用单链表表示的直接插入排序 JD *t，*p，*r，*q； if(h!=NULL)t=h； while (t-link!=NULL) p=t-link； 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； else t-link=p-link； p-link=r；q-link=p； return h；,二分插入排序算法,二分插入排序算法如下： void rffpx(int r，int n) /二分插入排序 int i，j，m，t，w，x； for(i=1；i=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-=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+1ri） k+；x=ri；ri=ri+1；ri+1=x； j+；,图 例,快速排序的递归算法,快速排序的递归算法如下： void kspxd(int r，int t，int w) /快速排序递归算法 int i，j，k，x； if（t=w）return； i=t；j=w；x=ri； do while(rj=x)&(ji）j-； if(ii) i+； if（ij）rj=ri；j-； while(ij)； ri=x； kspxd（r，t，j-1）； kspxd(r，j+1，w)；,图 例,图 例,快速排序的非递归算法,void kspxf(int r，int n)/快速排序非递归算法 int k，t，w，i，j，x，s1，s2；k=0；t=0；w=n-1； dowhile(t=x)&(ii) i+； if(i0)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； if(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) if（jw)&(rj rj+1)j+； if(xrj) ri=rj；i=j；j*=2； else j=w+1； ri=x； ,堆排序的算法,下面给出堆排序的算法。 void dpx(int r，int n) /堆排序 int i，x； for(i=n2；i；i-) sift(r，i，n)； for(i=n；i；i-) x=r1；r1=ri；ri=x； sift（r，1，i-1）； ,归并排序算法,void hbgc(int r，int h，int m，int w， int t) /将存于r数组中的两个首尾相接的有序子表，合并成一个有序子表存于t数组中 int i，j，k； i=h；j=m+1；k=h-1； while(im） 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 if（i(n-s+1) ） hbgc(r，i，i+s-1，n，t)； else while (i=n) ti=ri+；,二路归并排序算法,二路归并排序算法如下： 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；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； return p； ,图 例,图 例,复习思考题,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调整为堆。