template <class Record, class Compare> 算法分析 veidHeap Sorter <Record, Compare> bort(Record array, int n) //堆排序, Array[为待排数组,n为数组长度 建堆 Record record 删除堆顶:e(ogj) ;蹇堆 一次建堆n次删除堆顶 即堆顶 for(int i=O; i<n; i++) 总时间代价为e(川ogm) max heap. Remove Max(record); 空间代价为⊙(1) 北大脑张铭输写 真大物单张写 76分配排序和基数排序 761桶式排序 不需要进行纪录之间两两比较 ■事先知道序列中的记录都位于某 需要事先知道记录序列的一些具 个小区间段[O,m)内 体情况 ■将具有相同值的记录都分配到同 个桶中,然后依次按照编号从 桶中取出记录,组成一个有序序 列 京大管息张铭编写 莉命究 北真大张写 桶排序示意 桶式排序算法 待排数组:738961g12 template <class record> class Bucketsorter: public 第一越out22a522 Sorter<Record Compare> /桶式排序类 后继起始下标:回21444669 void Sort(Record Array[,int n, int max) 收集 8 真大带息学张铭端写 北真大脆张铭编写 1919 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 109 template <class Record,class Compare> void HeapSorter<Record,Compare>:: Sort(Record Array[], int n) { //堆排序，Array[]为待排数组，n为数组长度 Record record; MaxHeap< Record > max_heap = MaxHeap< Record >(Array,n,n); //建堆 // 依次找出剩余记录中的最大记录，即堆顶 for (int i=0; i<n; i++) max_heap.RemoveMax(record); } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 110 算法分析 „ 建堆：Θ(n) „ 删除堆顶:Θ(log i ) „ 一次建堆 ,n次删除堆顶 „ 总时间代价为Θ(nlog n) „ 空间代价为Θ(1) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 111 7.6 分配排序和基数排序 „ 不需要进行纪录之间两两比较 „ 需要事先知道记录序列的一些具 体情况 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 112 7.6.1 桶式排序 „ 事先知道序列中的记录都位于某 个小区间段[0，m)内 „ 将具有相同值的记录都分配到同 一个桶中，然后依次按照编号从 桶中取出记录，组成一个有序序 列 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 113 桶排序示意 0 2 1 1 0 0 1 1 2 1 0 2 3 4 4 4 5 6 8 9 1 1’ 2 3 6 7 8 8’ 9 0 1 2 3 4 5 6 7 8 2 待排数组： 第一趟count 后继起始下标： 收集： 7 3 8 9 6 18’ 1’ 2 0 1 2 3 4 5 6 7 8 9 10 7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 114 桶式排序算法 template <class Record> class BucketSorter:public Sorter<Record,Compare> { //桶式排序类 public: void Sort(Record Array[],int n,int max); };