排序算法数据结构 Compositor.h

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

///////////////////////////

// //

// 排序算法数据结构 Compositor.h //

// //

//////////////////////////

#include<iostream.h>

template<class Type>

class Compositor

{

public:

Compositor():sort(NULL){}

void Creat(); //创建排序数组

void Bubble(); //冒泡排序

void Insert(); //插入排序

//快速排序

void Quick();

void QSort(int,int);

int Partition(int low,int high);

//归并排序

void Merge(Type SR[],Type TR[],int i,int m,int n);

void Msort(Type SR[],Type TR1[],int s,int t);

void MergeSort();

//选择排序

void Select();

void Print(); //打印排序后的结果

protected:

Type *sort;

int leng;

};

template<class Type>

void Compositor<Type>::Creat()

{

cout<<"输入你需要排序的数据个数: ";

cin>>leng;

while(leng<=0)

{

cout<<"输入数据有误";

cin>>leng;

}

sort=new Type[leng];

cout<<"请输入各数据项:";

for(int i=0;i<leng;i++)

cin>>sort;

}

template<class Type>

void Compositor<Type>::Insert()

{

Creat();

Type temp;

for(int i=1;i<leng;i++)

{

if(sort<sort[i-1])

{

temp=sort;

for(int j=i-1;temp<sort[j]&&j>=0;j--)

{

sort[j+1]=sort[j];

}

sort[j+1]=temp;

}

}

Print();

}

template<class Type>

void Compositor<Type>::Bubble()

{

Creat();

Type temp;

for(int i=leng-1;i>=0;i--)

{

for(int j=0;j<leng-1;j++)

{

if(sort[j]>sort[j+1])

{

temp=sort[j];

sort[j]=sort[j+1];

sort[j+1]=temp;

}

}

}

Print();

}

template<class Type>

void Compositor<Type>::Quick()

{

Creat();

QSort(0,leng-1);

Print();

}

template<class Type>

void Compositor<Type>::QSort(int s,int t)

{

if(s<t-1)

{

int pivotloc=Partition(s,t);

QSort(s,pivotloc-1);

QSort(pivotloc+1,t);

}

}

template<class Type>

int Compositor<Type>::Partition(int low,int high)

{

Type pivotkey=sort[low];

while(low < high)

{

while(low<high&&sort[high]>=pivotkey)

--high;

sort[low++]=sort[high];

while(low<high&&sort[low]<=pivotkey)

++low;

sort[high--]=sort[low];

}

sort[low]=pivotkey;

return low;

}

template<class Type>

void Compositor<Type>::MergeSort()

{

Creat();

Msort(sort,sort,0,leng-1);

Print();

}

template<class Type>

void Compositor<Type>::Msort(Type SR[],Type TR1[],int s,int t)

{

int m;

Type *TR2=new Type[t-s];

if(s==t) TR1[s]=SR[s];

else

{

m=(t+s)/2;

Msort(SR,TR2,s,m);

Msort(SR,TR2,m+1,t);

Merge(TR2,TR1,s,m,t);

}

}

template<class Type>

void Compositor<Type>::Merge(Type SR[],Type TR[],int i,int m,int n)

{

for(int j=m+1,k=i;i<=m&&j<=n;k++)

{

if(SR<=SR[j])

TR[k]=SR[i++];

else

TR[k]=SR[j++];

}

while(i<=m)

TR[k++]=SR[i++];

while(j<=n)

TR[k++]=SR[j++];

}

template<class Type>

void Compositor<Type>::Select()

{

Creat();

Type temp;

int t;

for(int i=0;i<leng;i++)

{

t=i;

for(int j=i+1;j<leng;j++)

{

if(sort[t]>sort[j])

t=j;

}

if(t!=i)

{

temp=sort[t];

sort[t]=sort;

sort=temp;

}

}

Print();

}

template<class Type>

void Compositor<Type>::Print()

{

cout<<"排序结果为: ";

for(int i=0;i<leng;i++)

cout<<sort<<" ";

cout<<endl;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航