北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第七章 内排序

排序的稳定性 ■稳定性 存在多个具有相同排序码的记录 排序后这些记录的相对次序保持不变 例如,341234′0896 0812343496稳定! 0812343496—不稳定! 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 11

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 排序的稳定性 „ 稳定性 „ 存在多个具有相同排序码的记录 „ 排序后这些记录的相对次序保持不变 „ 例如，34 12 34’ 08 96 „ 08 12 34 34’ 96——稳定！ „ 08 12 34’ 34 96——不稳定！

排序算法的衡量标准 时间代价:记录的比较和移动次数 空间代价 算法本身的繁杂程度 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 12

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 排序算法的衡量标准 „ 时间代价：记录的比较和移动次数 „ 空间代价 „ 算法本身的繁杂程度

7.13常用类和函数 总的排序类 Compare类 Swap函数 PrintArray函数 北京大学信息学院张铭编写 版权所有,转载或翻印必究 3

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 7.1.3 常用类和函数 „ 总的排序类 „ Compare类 „ Swap函数 „ PrintArray函数

总的排序类 template <class record, class compare> class sorter【//总排序类 protected: /交换数组中的两个元素 static void swap(Record arrayllint i,int j; public. //对数组Aray进行排序 void Sort (Record arrayal,int n; /输出数组内容 void PrintArray(record array, int n; 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 14

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 总的排序类 template <class Record,class Compare> class Sorter{ //总排序类 protected: //交换数组中的两个元素 static void swap(Record Array[],int i,int j); public: //对数组Array进行排序 void Sort(Record Array[],int n); //输出数组内容 void PrintArray(Record array[], int n); };

Compare类 Compare类是用来比较记录的 排序码 模板参数,方便针对不同类型的 排序码进行比较 为了简便起见,本教材讨论整数 排序的例子 北京大学信息学院张铭编写 版权所有,转载或翻印必究 15

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 Compare类 „ Compare类是用来比较记录的 排序码 „ 模板参数，方便针对不同类型的 排序码进行比较 „ 为了简便起见，本教材讨论整数 排序的例子