排序算法的分类(续) 分治排序 快速排序( Quicksort 归并排序( Mergesort) 堆排序( Heapsort) 分配排序( Binsort 北京大学信息学院 版权所有,转载或翻印必究 Page 11
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 排序算法的分类（续） ◼ 分治排序 ◼ 快速排序(Quicksort) ◼ 归并排序(Mergesort) ◼ 堆排序(Heapsort) ◼ 分配排序 (Binsort)
排序算法的衡量标准 时间代价:记录的比较和交换次 数 空间代价 算法的复杂度 北京大学信息学院 版权所有,转载或翻印必究 Page 12
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 排序算法的衡量标准 ◼ 时间代价：记录的比较和交换次 数 ◼ 空间代价 ◼ 算法的复杂度
总的排序类 template <class Record, class compare> class Sorter//总排序类 protected: /交换数组中的两个元素 static void swap(Record arrayal,int i,int Di public: //对数组Aray进行排序 void Sort(Record arrayllint ni /输出数组内容 void PrintArray ( record arrayal, int ni Fi 北京大学信息学院 版权所有,转载或翻印必究 Page 13
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 总的排序类 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类是用来比较记录的 排序码,把它单独定义成模板参 数,是为了方便针对不同类型的 排序码进行比较。为了简便起见, 我们只讨论整数排序的例子。 北京大学信息学院 版权所有,转载或翻印必究 Page 14
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 Compare类 ◼ Compare类是用来比较记录的 排序码，把它单独定义成模板参 数，是为了方便针对不同类型的 排序码进行比较。为了简便起见， 我们只讨论整数排序的例子
int intcompare类 class int_intcomparet /比较两个整型记录大小 public static bool It (int x,inty return x<yi] static bool eq (int x, inty return X==Yi] static bool gt(int x,int y ireturn x>Vi static bool le(int x y return x<=yil static bool ge(int x, int y freturn x>=Yil 北京大学信息学院 版权所有,转载或翻印必究 Page 15
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 int_intCompare 类 class int_intCompare{ //比较两个整型记录大小 public: static bool lt(int x,int y) {return x<y;} static bool eq(int x,int y) {return x==y;} static bool gt(int x,int y) {return x>y;} static bool le(int x,int y) {return x<=y;} static bool ge(int x,int y) {return x>=y;} };