0123456789 基于数组的基数排序 0123456789 emplate <class Record> 按 count分配桶 oo2|3477789 class RadixSorter: public Sorter<Record, Compare> //基数排序类 收集2|26a4|8888 public: void Sort(Record array ll,int n, int 最终排序结果 min, int max); 22263141535859889 真大物单张写 template <class Record> //将 TempArray'中的位置依次分配给个桶 oid RadixSorter<Record>:: Sort(Record for G=1; jr; j++) Afray[], int n, int d, int r) Ln为数组长度,d为排序码数,为基数 将记录依次收集到 empArray? ntu]; Record* TempArray= new Record[n/临时 for G=n-1; j>=0; nt*cunt= new int[r//计数器 //取Aray订]的第位排序码 k=(Array]/Radix%or int Radix=1 /取Aray]的第位排序码 count[k]-∽//从k桶取出了一个记录 for〔i=1;i=di++)//分别对第个排序码分配 TempArray[count[kJ] Array u] for〔=0j<rj++) countS=0;//初始化 for〔=0jm;j++){//统计每桶记录 //将临时数组中的内容复制到Aray中 //取Aray[j]的第位排序码 or g=0; j<n; j++) k=(Array]/Radix%/or; Array] TempArray ]; count]++;//相应计数器加1 京大管息张铭编写 莉命究 张写 算法分析 算法分析(续) 空间代价: ■时间代价 临时数组,n a桶式排序:e(n+r) 『个计数器 ■d次桶式排序 ■总空间代价e(n+r) (d (n+rD) 真大带息学张铭端写 ,命究 北真大脆张铭编写23 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 133 0 1 2 3 4 5 6 7 8 9 第二趟：count 0 1 2 3 4 5 6 7 8 9 按 count分配桶： 收集： 最终排序结果： 22 26 31 41 53 58 59 88 97 22 26 31 41 53 58 59 88 97 0 0 2 1 1 3 0 0 1 1 0 0 2 3 4 7 7 7 8 9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 134 基于数组的基数排序 template <class Record> class RadixSorter:public Sorter<Record,Compare> { //基数排序类 public: void Sort(Record Array[],int n,int min,int max); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 135 template <class Record> void RadixSorter<Record>::Sort(Record Array[], int n,int d, int r) { //n为数组长度，d为排序码数，r为基数 Record *TempArray =new Record[n]; //临时 int* count= new int[r]; //计数器 int i,j,k; int Radix=1; //取Array[j]的第i位排序码 for (i=1; i<=d; i++) {// 分别对第i个排序码分配 for (j=0; j<r; j++) count[j] = 0; // 初始化 for (j=0; j<n; j++) { // 统计每桶记录数 //取Array[j]的第i位排序码 k=(Array[j] /Radix)%r; count[k]++; //相应计数器加1 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 136 // 将TempArray中的位置依次分配给r个桶 for (j=1; j<r; j++) count[j] = count[j-1] + count[j]; // 将记录依次收集到TempArray中 for (j=n-1; j>=0; j--) { //取Array[j]的第i位排序码 k=(Array[j] /Radix)%r; count[k]--; //从k桶取出了一个记录 TempArray[count[k]] = Array[j]; } // 将临时数组中的内容复制到Array中 for (j=0; j<n; j++) Array[j] = TempArray[j]; Radix*=r; } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 137 算法分析 „ 空间代价： „ 临时数组, n „ r个计数器 „ 总空间代价Θ(n+r) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 138 算法分析（续） „ 时间代价 „ 桶式排序：Θ(n+r) „ d次桶式排序 „ Θ(d ·(n+r))