数据结构与算法—教学课件15.pdf

数据结构与算法(八)张铭主讲采用教材:张铭,王腾蛟,赵海燕编写高等教育出版社,2008. 6 (“十一五”国家级规划教材).cn/pkujpk/course/sjjg张铭《数据结构与算法》2目录页张铭《数据结构与算法》内排序第八章大纲? 排序问题的基本概念? 插入排序(Shell 排序)? 选择排序(堆排序)? 交换排序– 冒泡排序– 快速排序? 归并排序? 分配排序和索引排序? 排序算法的时间代价?内排序知识点总结3目录页张铭《数据结构与算法》 排序算法的时间代价?简单排序算法的时间代价?排序算法的理论和实验时间?排序问题的下限4目录页张铭《数据结构与算法》 排序算法的时间代价?一个长度为n 的序列平均有n(n-1)/4 对逆置?任何一种只对相邻记录进行比较的排序算法的平均时间代价都是Θ(n2) 原因5目录页张铭《数据结构与算法》 排序算法的理论和实验时间算法最大时间平均时间最小时间辅助空间代价稳定性直接插入排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定冒泡排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定选择排序Θ(n2)Θ(n2)Θ(n2)Θ(1)不稳定6目录页张铭《数据结构与算法》 排序算法的理论和实验时间算法最大时间平均时间最小时间辅助空间稳定性Shell排序(3)Θ(n3/2)Θ(n3/2)Θ(n3/2)Θ(1)不稳定快速排序Θ(n2)Θ(nlogn)Θ(nlogn)Θ(log n)不稳定归并排序Θ(nlog n)Θ(nlogn)Θ(nlogn)Θ(n)稳定堆排序Θ(nlog n)Θ(nlogn)Θ(nlogn)Θ(1)不稳定桶式排序Θ(n+m)Θ(n+m)Θ(n+m)Θ(n+m)稳定基数排序Θ(d·(n+r))Θ(d·(n+r))Θ(d·(n+r))Θ(n+r)稳定7目录页张铭《数据结构与算法》 排序算法的理论和实验时间内排序第八章?n 很小或基本有序时插入排序比较有效?Shell 排序选择增量以3的倍数递减–需要保证最后一趟增量为1?综合性能快速排序最佳小结8目录页张铭《数据结构与算法》 排序算法的理论和实验时间内排序第八章测试环境?硬件环境–CPU:Intel P4 3G –内存:1G?软件环境–Windows XP–Visual C++ 《数据结构与算法》 排序算法的理论和实验时间内排序第八章//设置随机种子inlinevoidRandomize(){srand(1);}// 返回一个[0,n-1]之间的随机整数值inlineintRandom(intn){returnrand()%(n);}//产生随机数组ELEM *sortarray=newELEM[1000000];for(inti=0;i<1000000;i++)sortarray[i]=Random(32003);随机生成待排序数组10目录页张铭《数据结构与算法》 排序算法的理论和实验时间内排序第八章#include <>#define CLOCKS_PER_SEC 1000clock_ttstart=0;// 开始的时间// 初始化计时器voidSettime(){tstart=clock();}// 上次Settime() 之后经过的时间doubleGettime(){return(double)((double)clock()-(double)tstart) / (double)CLOCKS_PER_SEC;}时间测试