算法分析 最差情况: 时间代价:e(n2) nT(m)=(n+1)7(n-1)+2cm-c 空间代价:e(n) 最佳情况 (nlog n 间 og n T(n)=o(nlogn) ■平均情况 时间代价;e(mogm 空间代价:e(ogm 举位▲张倍墙写 北大单张铭写 叔新有,命邮 算法分析(续 教材优化 不稳定 ■子数组小于某个长度(阈值 ■可能优化: n=16)时,不递归 n轴值选择 块与块之间有序 QS ■最后对整个数组进行一次插入排 小子串不递归 序 消除递归 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 优化的快速排序 *tdefine THRESHold 16 优化的快速排序 template <cass r class compare> //优化的快速排序类 mprovedQuickSorter<Record Compare> Sort(Record Array[l, int left, int right) /选择轴值,返回轴值下标 //Aray[]为待排序数组,订分别//为数组两端 t SelectPivot(int left, int right); 分割返回轴值位量 //先对序列进行递归排序 int Partition Record Array[l, int left, int right) //最后对整个序列进行一次直接插入排序 void DoSort( Record Array[,int left, int right); provedInsertsorter <Record, compar void Sort(Record Array[,int left, int right); sorter insert sorter SortArray, right-left+1); 北真大学张铭编写 盖哪张帖写 权新有,究 1414 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 79 nT n n T n cn c ( ) ( 1) ( 1) 2 = + −+ − Tn n n ( ) ( log ) = Θ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 80 算法分析 „ 最差情况： „ 时间代价： Θ(n2) „ 空间代价： Θ(n) „ 最佳情况： „ 时间代价：Θ(nlog n) „ 空间代价：Θ(log n) „ 平均情况： „ 时间代价：Θ(nlog n) „ 空间代价：Θ(log n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 81 算法分析（续） „ 不稳定 „ 可能优化： „ 轴值选择 „ RQS „ 小子串不递归 „ 消除递归 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 82 教材优化 „ 子数组小于某个长度（阈值 n=16）时，不递归 „ 块与块之间有序 „ 最后对整个数组进行一次插入排 序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 83 优化的快速排序 #define THRESHOLD 16 template <class Record,class Compare> class ImprovedQuickSorter:public Sorter<Record,Compare> { //优化的快速排序类 private: //选择轴值，返回轴值下标 int SelectPivot(int left, int right); //分割,返回轴值位置 int Partition(Record Array[], int left, int right); void DoSort(Record Array[],int left,int right); public: void Sort(Record Array[],int left,int right); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 84 优化的快速排序 template <class Record,class Compare> void ImprovedQuickSorter<Record,Compare>:: Sort(Record Array[], int left,int right) { //Array[]为待排序数组，i,j分别//为数组两端 //先对序列进行递归排序 DoSort(Array,left,right); //最后对整个序列进行一次直接插入排序 ImprovedInsertSorter<Record,Compare> insert_sorter; insert_sorter.Sort(Array,right-left+1); }