基于静态链的基数排序（C++）    基于链表的实现主要是将分配出来的子序列存放在r个（静态链组织的）队列中，在数组中设置next段。 #include <iostream>using namespace std;const int N=20;const int r=10; //节点类class Node{public: int key; int next;}; //静态队列类class StaticQueue{public: int head; int tail;}; 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);}; template<class Record>void LinkRadixSorter<Record>::Sort(Record* Array,int n,int d,int r){ int first=0; StaticQueue* queue; queue=new StaticQueue[r]; for(int i=0;i<n;i++)  Array[i].next=i+1; Array[n-1].next=-1; cout<<"排序前"; cout<<endl; PrintArray(Array,0); for(int j=0;j<d;j++) {  Distribute(Array,first,j,r,queue);  Collect(Array,first,j,r,queue); } cout<<"排序后:"; cout<<endl; PrintArray(Array,first); delete[] queue;} //分配过程，A中存放待排序纪录，first为静态链中的第一个纪录，i为当前处理的//子码位置，r为基数 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;  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=Array[first].next; }} 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;} template <class Record>void LinkRadixSorter<Record>::PrintArray(Record* Array,int first){ int tmp; tmp=first; while(tmp!=-1) {  cout<<Array[tmp].key<<" ";  tmp=Array[tmp].next; } cout<<'\n';} int main(){  Node  array[N]; int n=10,d; cout<<"写入要输入数的位数："; cin>>d; cout<<"输入十个数字"<<endl; for(int i=0;i<10;i++)  cin>>array[i].key; LinkRadixSorter<Node> A; A.Sort(array,n,d,r); return 0;} 在vc6.0中实现编译运行的。

评论