sWap函数 template <class Record, class Compare> void Sorter<Record, Compare>:: swap(Record array ll,int i,int j //交换数组中的两个元素 Record TempRecord Arrayli]; Array[] Arraylji Array[]= TempRecordi 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 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 array int n) //输出数组内容 for(int i=Oii<n;i++) cout< <Arrayli]<<i cout<<endl 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 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) a选择排序( Selection sort) 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 7.2 三种Ｏ(n2)的简单排序 ◼ 插入排序(Insert Sort) ◼ 冒泡排序(Bubble Sort) ◼ 选择排序 (Selection Sort)
72.1插入排序 算法思想: 逐个处理待排序的记录,每个新 记录都要与前面那些已排好序的 记录进行比较,然后插入到适当 的位置。 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 7.2.1插入排序 ◼ 算法思想： ◼ 逐个处理待排序的记录，每个新 记录都要与前面那些已排好序的 记录进行比较，然后插入到适当 的位置
45‖34781234322964 13445‖781234322964 i=2344578‖1234322964 312344578‖34322964 i=4 34344578‖322964 5123234344578‖2964 =6 3234 44578‖64 i=71229323434456478
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20