7|63|68|6|26|4|6312】 士 基于静态链的基数排序 【)智衰内喜 u命【0 31 将分配出来的子序列存放在r个 q菇·u[2 (静态链组织的)队列中 u··[3 (b)第一趙分配 ■链式存储避免了空间浪费情况 ·●[T (c)第一趟收集4131226326|m86 北大脑张铭输写 qu·【 4312|6326|97|8686 q·u·【1 啁226 罪u·[3 静态队列定义 [4 class Node//结点类 public: nt key;//结点的关键码值 int next//下一个结点在数组中的下标 q日【·】 q·u·【◆ (d)第二趙分配 class StaticQueue//静态队列类 public: (e)第二趟收集结果22604|6」6a int head (最终结果 北真大张写 template <class record> 基于静态链的基数排序 LinkRadixSorter<Record>: Sort(Record* Array, int n, int d, intr) template <class Record> //n为数组长度,d为排序码个数,r为基数 class LinkRadixSorter t int first=0// first指向静态链中第一个记录 private: void Distribute(Record* Array int first, /存放r个桶的静态队列 int iint r; StaticQueue* queue)//分配 queue new StaticQueue[r]; id Collect(Record* Array int& first, /建链,初始为nex域指向下一个记录 int i, int r StaticQueue* queue); // for(int i=O; i<n; i++) void PrintArray( Record* A, int first);//输出 Array [i]. next =i+1; Aray[n-1]next=-1;/链尾next为空 void Sort(Record* Array int n, int d, int r); 食大弹张铭写 ,命究 北真大脆张铭编写24 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 139 基于静态链的基数排序 „ 将分配出来的子序列存放在r个 (静态链组织的)队列中 „ 链式存储避免了空间浪费情况 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 140 (a)初 始 链 表 内 容 queue[0] queue[1] queue[2] queue[3] queue[4] queue[5] queue[6] queue[7] queue[8] queue[9] 97 53 88 59 26 41 58 31 22 41 22 53 26 97 59 88 31 41 31 22 53 26 97 88 58 59 58 (c) 第一趟收集 (b)第一趟分配 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 141 queue[0] queue[1] queue[2] queue[3] queue[4] queue[5] queue[6] queue[7] queue[8] queue[9] (d)第 二 趟 分 配 22 31 41 97 26 88 22 26 31 41 53 58 59 88 97 53 58 59 41 31 22 53 26 97 88 58 59 (e) 第二趟收集结果 （最终结果） (d)第二趟分配 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 142 静态队列定义 class Node{ //结点类 public: int key; //结点的关键码值 int next; //下一个结点在数组中的下标 }; class StaticQueue{ //静态队列类 public: int head; int tail; }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 143 基于静态链的基数排序 template <class Record> class LinkRadixSorter { private: void Distribute(Record* Array,int first, int i,int r, StaticQueue* queue);//分配 void Collect(Record* Array, int& first, int i, int r, StaticQueue* queue);//收集 void PrintArray(Record* A, int first);//输出 public: void Sort(Record* Array,int n, int d, int r); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 144 template <class Record> void LinkRadixSorter<Record>::Sort(Record* Array, int n, int d, int r) { //n为数组长度，d为排序码个数，r为基数 int first=0; // first指向静态链中第一个记录 StaticQueue *queue; //存放r个桶的静态队列 queue = new StaticQueue[r]; // 建链，初始为next域指向下一个记录 for (int i=0; i<n; i++) Array[i].next = i+1; Array[n-1].next = -1; //链尾next为空