int int compare类 class int intcompare t /比较两个整型记录大小 public: static bool It(int x, inty return x<yil static bool eq(int x,int y) ireturn x==yi] static bool gt(int x inty ireturn x>yil static bool le(int x,int y ireturn x<=Yil static bool ge(int nty return x>=Yi] 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 16
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 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;} };
sWap函数 template <class record, class Compare> void Sorter< Record, compare>:: swap(Record array lint i,int j) //交换数组中的两个元素 Record TempRecord Arraylili Array [i]= Array]; Array[]= TempRecord; 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 17
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 swap函数 template <class Record,class Compare> void Sorter<Record,Compare>:: swap(Record Array[],int i,int j) { //交换数组中的两个元素 Record TempRecord = Array[i]; Array[i] = Array[j]; Array[j] = TempRecord; }
PrintArray函数 template <class record, class Compare> void Sorter< Record, compare>:: PrintArray (Record arrayal int n) //输出数组内容 for(int i=O;i<n;i++) cout< <Arrayli]<< cout<<endi 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 18
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 PrintArray函数 template <class Record,class Compare> void Sorter<Record,Compare>:: PrintArray(Record Array[], int n) { //输出数组内容 for(int i=0;i<n;i++) cout<<Array[i]<<" "; cout<<endl; }
72三种O(n2)的简单排序 插入排序( Insert sort) 冒泡排序( Bubble sort) 选择排序( Selection sort) 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 19
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 7.2 三种Ｏ(n2)的简单排序 插入排序(Insert Sort) 冒泡排序(Bubble Sort) 选择排序(Selection Sort)
72.1插入排序 ■算法思想 算法演示 直接插入排序 优化的插入排序 带监视哨的插入排序 分法插入排序 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 20
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 7.2.1 插入排序 算法思想 算法演示 直接插入排序 优化的插入排序 带监视哨的插入排序 二分法插入排序