#include<iostream> using namespace std;

template <typename T>struct Node{ T key;

}; template <typename T>class Orderedlist{ int maxsize; int last; Node<T> slist[100]; public: Orderedlist(){last=0;maxsize=100;} int Length() const{return last+1;}//计算表长度 void Mergesort(); void MergePass(Node<T> *b,int len); void Merge(Node<T> *b,int low,int mid,int high); bool Insert(Node<T> & elem,int i); void print(); }; template <typename T> bool Orderedlist<T>::Insert(Node<T> & elem ,int i){ if (i<0||i>last+1||last==maxsize-1) return false; else{ for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; last++; return true; } } template <typename T> void Orderedlist<T>::print(){ int i; for(i=0;i<last;i++){ cout<<slist[i].key<<'\t'; if(i%8==7) cout<<endl; } cout<<endl; } template<typename T> void Orderedlist<T>::Mergesort(){ int len=1; Node<T> b[100]; while(len<last){ MergePass(b,len); len=2*len; for(int i=0;i<last;i++) slist[i]=b[i]; } } template <typename T> void Orderedlist<T>::MergePass(Node<T> *b,int len){ int i,j; i=0; while(i+2*len<last){ Merge(b,i,i+len-1,i+2*len-1); i= i+2*len; } if(i+len<last) Merge(b,i,i+len-1,last-1); else for(j=i;j<last;j++) b[j]=slist[j]; } template <typename T> void Orderedlist<T>::Merge(Node<T> *b,int low,int mid,int high){ int i,j,k; i=low; j=mid+1; k=low; while((i<=mid)&&(j<=high)){ if(slist[i].key<=slist[j].key) b[k++]=slist[i++];//取小者复制 else b[k++]=slist[j++]; } while(i<=mid) b[k++]=slist[i++];//复制第一个文件的剩余元素 while(j<=high) b[k++]=slist[j++];//复制第二个文件的剩余元素 }

void main(){ const int h=5; int i; Orderedlist<int> ordlist; int a[h]={5,4,3,2,1}; Node<int> n[h]; for(i=0;i<h;i++) n[i].key=a[i]; for(i=0;i<h;i++) ordlist.Insert(n[i],i); //建立顺序表 cout<<"未排序表："<<endl; ordlist.print(); ordlist.Mergesort(); cout<<"已排序表："<<endl; ordlist.print(); }