cout<<"排序前:"<<endl void LinkRadix Sorter <Record>: Distribute( PrintArray(array,0);//输出原始序列 Record* Array, int first, int i,int r, taticQueue queue) H对策个排序码进行分配和收集,一共d超 for fint j=Or j<r j++queue].head=-1; for(int j=O; j<d; j++) while(frst!=-1)/对整个静态链分配 intk= Array[frst]keyv;//取第位 Distribute(Array first, j, r, queue) for(int a=O; a<i; a++)k= k/r; Collect(Array, first, j, r queue) k=k%/or: if (queuekk] head ==-1) cout<<"排序后:"<<endl PrintArray( Array, first);//输出排序后的结 else//否则加到子序列的尾部 Array[queuekk]tail.next first delete[] queue frst// first为尾部 first=Aray[ first]nex//继续下一个 北大脑张铭输写 大m张铭临写 Q哈 输出序列中所有内容 已收集到的最后一个记录 while(queuekk]head ==-1)k++i template <class Record> first queue k]head; last queuekk] tail; void LinkRadixSorter< Record> whille(k<r-1){∥/继续收集下一个非空队列 PrintArray (Record* Array int first //rst为静态链Aray中第一个记录的下标 hile(k<r-1 & queue[k] head==-1) /用来扫描整个链的指针 tmp first; if(queuekk] head!=-1) t while(tmp l=-1) Array last]. next queuekk]head last queue[k]. tai;y cout<<Aay[tmp]key<<"";/榆出记录 tmp Array[tmp]. next; 1 Aray[ ast].next=-1;//收集完毕 京大管息张铭编写 莉命究 北真大张写 77各种排序算法的理论和实 算法分析 验时间代价 空间代价 录大时平均时|最小时间辅助空稳定 n个记录空间 间代价性 直接插入排e(n2)e( 8(n)e()稳定 r个子序列的头尾指针 o(n +r) 法插入e(m)e(m)e( nlog n) e(1)稳定 时间代价 秉露要3录本身,只需要修改记 翼泡排序 n)em)e(m)e(1)稳定 e()糖定 o(d (n+r)) 选择排序 e(m2)e(n2)e(m2)e(1)不稳 真大带息学张铭端写 真知张写 2525 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 145 cout<<"排序前：" <<endl; PrintArray(Array, 0); //输出原始序列 //对第j个排序码进行分配和收集，一共d趟 for (int j=0; j<d; j++) { Distribute(Array, first, j, r, queue); Collect(Array, first, j, r, queue); } cout<<"排序后：" <<endl; PrintArray(Array, first);//输出排序后的结 果 delete[] queue; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 146 template <class Record> void LinkRadixSorter<Record>::Distribute( Record* Array,int first,int i,int r, StaticQueue* queue) { for (int j=0; j<r; j++) queue[j].head=-1; while (first != -1) {//对整个静态链分配 int k=Array[first].key; //取第i位 for (int a=0; a<i; a++) k= k/r; k=k%r; if (queue[k].head == -1) queue[k].head = first; else // 否则加到子序列的尾部 Array[queue[k].tail].next = first; queue[k].tail = first; //first为尾部 first = Array[first].next; //继续下一个 } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 147 template <class Record> void LinkRadixSorter<Record>::Collect (Record* Array, int& first, int i, int r, StaticQueue* queue) { int last, k=0; //已收集到的最后一个记录 while (queue[k].head == -1) k++; first = queue[k].head; last = queue[k].tail; while (k<r-1) { //继续收集下一个非空队列 k++; while (k<r-1 && queue[k].head==-1) k++; if (queue[k].head!= -1) { Array[last].next = queue[k].head; last = queue[k].tail; } } Array[last].next = -1; //收集完毕 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 148 输出序列中所有内容 template <class Record> void LinkRadixSorter<Record>:: PrintArray(Record* Array, int first) { //first为静态链Array中第一个记录的下标 int tmp; //用来扫描整个链的指针 tmp = first; while (tmp != -1) { cout << Array[tmp].key <<" ";//输出记录 tmp = Array[tmp].next; } cout << '\n'; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 149 算法分析 „ 空间代价 „ n个记录空间 „ r个子序列的头尾指针 „ Ｏ(n + r) „ 时间代价 „ 不需要移动记录本身，只需要修改记 录的next指针 „ Ｏ(d·(n+r)) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 150 7.7 各种排序算法的理论和实 验时间代价 不稳 定 Θ(n Θ(1) 2 Θ(n ) 2 Θ(n ) 2 选择排序 ) 改进的冒泡 Θ(n2) Θ(n2) Θ(n) Θ(1) 稳定 排序 冒泡排序 Θ(n2) Θ(n2) Θ(n2) Θ(1) 稳定 二分法插入 Θ(n2) Θ(n2) Θ(nlog n) Θ(1) 稳定 排序 直接插入排 Θ(n2) Θ(n2) Θ(n) Θ(1) 稳定 序 稳定 性 辅助空 间代价 平均时 最小时间 间 最大时 间 算法