/桶式排序,Aray[]为待排序数组 ∥数组长度为n所有记录都位于区间[omax)上 /统计每个取值出现的次数 plate <class Record> for(i=O;i <n;i++) Array, int n,int max) it[Array [l++ int* TempArray= new record[n]/临时数组 /统计小于等于的元素个数 int* count= new int[max]//小于等于的个数 or (i=1;i<max;i++) int count[i]=count[i-1]+count [i]; for (i=O;in;i++ /按顺序输出有序序列 Temp Array[i]=Array[]; for(i=n-1;i>=0;i-) //所有计数器初始都为0 Array[--countTempArray[]]] for (i=O;i<max; i++) TempArray[i] count[i]=Oj 北大脑张铭输写 真大物单张写 算法分析 算法分析(续) 数组长度为n,所有记录区间[0m)上 空间代价: ■时间代价: m个计数器,长度为n的临时数 统计计数时:⊙(m+m) 组,e(m+ 输出有序序列时循环n次 稳定 总的时间代价为e(m+n) ■适用于m相对于n很小的情况 京大管息张铭编写 莉命究 北真大张写 762基数排序 基数排序 ■桶式排序只适合m很小的情况 假设长度为n的序列 当m很大时,可以将一个记录的 R=fro,r 记录的排序码K包含d个子排序码 值即排序码拆分为多个部分来进 行比较—基数排序 K=(k4k2,…,k1,k) 真大带息学张铭端写 ,命究 北真大脆张铭编写20 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 115 //桶式排序，Array[]为待排序数组 //数组长度为n, 所有记录都位于区间[0,max)上 template <class Record> void BucketSorter<Record>::Sort(Record Array[], int n,int max) { int* TempArray=new Record[n];//临时数组 int* count=new int[max];//小于等于i的个数 int i; for (i=0;i<n;i++) TempArray[i]=Array[i]; //所有计数器初始都为0 for (i=0;i<max;i++) count[i]=0; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 116 //统计每个取值出现的次数 for (i=0;i<n;i++) count[Array[i]]++; //统计小于等于i的元素个数 for (i=1;i<max;i++) count[i]=count[i-1]+count [i]; //按顺序输出有序序列 for (i=n-1;i>=0;i--) Array[--count[TempArray[i]]] = TempArray[i]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 117 算法分析 „ 数组长度为n, 所有记录区间[0,m)上 „ 时间代价： „ 统计计数时：Θ(n+m) „ 输出有序序列时循环n次 „ 总的时间代价为Θ(m+n) „ 适用于m相对于n很小的情况 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 118 算法分析（续） „ 空间代价： „ m个计数器，长度为n的临时数 组，Θ(m+n) „ 稳定 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 119 7.6.2 基数排序 „ 桶式排序只适合m很小的情况 „ 当m很大时，可以将一个记录的 值即排序码拆分为多个部分来进 行比较——基数排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 120 基数排序 „ 假设长度为n的序列 R={ r0，r1，…，rn-1 } 记录的排序码K包含d个子排序码 K=(kd-1，kd-2，…，k1，k0 )