[求助]:高手们,来帮我看看这个题啊,是内部排序问题,我急着用.谢谢了!
高手们,"内部排序算法比较"的思想和程序怎么写啊,帮帮我啊通过随机数据比较各算法的关键字比较次数和关键字移动次数,
要求:1,对6种常用的内部排序算法进行比较
2,待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生
#include <iostream.h> #include <malloc.h> #include <stdlib.h> #define LS(a,b) ((a)<(b)) #define LL(a,b) ((a)>(b)) #define MAXSIZE 100 typedef int KeyType; typedef struct { int key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; typedef SqList HeapType; int compare=0; int change=0; int Create_Sq(SqList &L){ int i,k; cout<<"How many elems the List have:"; cin>>k; L.length=k; for(i=1;i<=k;++i){ cout<<"Please enter the "<<i<<" elem:"; cin>>L.r[i].key; } return 1; } void Bubble_sort(SqList &L){//冒泡排序 int i,j,l,k=L.length,m=0,n=0; for(i=1;i<=L.length-1;++i){ for(j=1;j<=k-1;++j){ ++m; if(LL(L.r[j].key,L.r[j+1].key)){ l=L.r[j].key; L.r[j].key=L.r[j+1].key; L.r[j+1].key=l; ++n; } } --k; } cout<<endl<<"-----冒泡排序后的序列-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; cout<<endl; cout<<"冒泡排序的比较次数:"; cout<<m<<endl; cout<<"冒泡排序的交换次数:"; cout<<n<<endl; } void InsertSort(SqList &L){//冒泡排序 int i,j,m=0,n=0; cout<<endl; for(i=2;i<=L.length;++i) if(LS(L.r[i].key,L.r[i-1].key)){ ++m; ++n; L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;LS(L.r[0].key,L.r[j].key);--j){ ++m; L.r[j+1]=L.r[j]; } L.r[j+1]=L.r[0]; } cout<<"-----直接插入排序后的序列-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; cout<<endl; cout<<"直接插入排序的比较次数:"; cout<<m<<endl; cout<<"直接插入排序的交换次数:"; cout<<n<<endl; } void SelectSort(SqList &L){//简单选择排序 int l,i,j,m=0,n=0; cout<<endl; for(i=1;i<L.length;++i){ L.r[0]=L.r[i]; j=i+1; l=i; for(j;j<=L.length;++j){ ++m; if(LL(L.r[0].key,L.r[j].key)){ l=j; L.r[0]=L.r[j]; } } if(l!=i){ ++n; L.r[l]=L.r[i]; L.r[i]=L.r[0]; } } cout<<"-----简单选择排序后的序列-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; cout<<endl; cout<<"简单选择排序的比较次数:"; cout<<m<<endl; cout<<"简单选择排序的交换次数:"; cout<<n<<endl; } int Partition(SqList &L,int low,int high){ int pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low<high){ while(low<high&&L.r[high].key>=pivotkey){ ++compare; --high; } ++change; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey){ ++compare; ++low; } ++change; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } void QSort(SqList &L,int low,int high){//递归形式的快速排序算法 int pivotloc; if(low<high){ pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); } } void QuickSort(SqList &L){ int i; QSort(L,1,L.length); cout<<"-----快速排序后的序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; cout<<endl; cout<<"快速排序的比较次数:"; cout<<compare<<endl; cout<<"快速排序的交换次数:"; cout<<change<<endl; compare=0; change=0; } void ShellInsert(SqList &L,int dk){//希尔排序 int i; int j; for(i=dk+1;i<=L.length;++i) if(LS(L.r[i].key,L.r[i-dk].key)){ ++compare; L.r[0]=L.r[i]; for(j=i-dk;j>0&&LS(L.r[0].key,L.r[j].key);j-=dk){ ++compare; ++change; L.r[j+dk]=L.r[j]; } L.r[j+dk]=L.r[0]; } } void ShellSort(SqList &L,int dlta[]){//希尔排序 int k,j=L.length/2,t=0; while(j>=0){ ++t; j-=2; } j=L.length/2; for(k=0;k<t;++k){//计算每次的增量值 if(j==0) j=1;//定义最后一趟排序的增量 dlta[k]=j; j-=2;
} for(k=0;k<t;++k) ShellInsert(L,dlta[k]); cout<<"-----希尔排序后的序列为-----"<<endl; for(k=1;k<=L.length;k++) cout<<" "<<L.r[k].key; cout<<endl; cout<<"希尔排序的比较次数:"; cout<<compare<<endl; cout<<"希尔排序的交换次数:"; cout<<change<<endl; compare=0; change=0; } void HeapAdjust(HeapType &H,int s,int m){//堆排序
int j; RedType rc; rc=H.r[s]; for(j=2*s;j<=m;j*=2){ if(j<m&&LS(H.r[j].key,H.r[j+1].key)){ ++compare; ++j; } if(!LS(rc.key,H.r[j].key)){ ++compare; break; } H.r[s]=H.r[j]; s=j; } H.r[s]=rc; } void HeapSort(HeapType &H){ int i; for(i=H.length/2;i>0;--i) HeapAdjust(H,i,H.length); for(i=H.length;i>1;--i){ ++change; H.r[0]=H.r[1]; H.r[1]=H.r[i]; H.r[i]=H.r[0]; HeapAdjust(H,1,i-1); } cout<<"-----堆排序后的序列为-----"<<endl; for(i=1;i<=H.length;i++) cout<<" "<<H.r[i].key; cout<<endl; cout<<"堆排序的比较次数:"; cout<<compare<<endl; cout<<"堆排序的交换次数:"; cout<<change<<endl; } void main(){ int i; int dlta[MAXSIZE]; SqList L; HeapType H; cout<<"-----冒泡排序-----"<<endl; Create_Sq(L); cout<<"-----冒泡排序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; Bubble_sort(L); cout<<"-----直接插入排序-----"<<endl; Create_Sq(L); cout<<"-----直接插入排序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; InsertSort(L); cout<<"-----简单选择排序-----"<<endl; Create_Sq(L); cout<<"-----简单选择排序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; SelectSort(L); cout<<"-----快速排序-----"<<endl; Create_Sq(L); cout<<"-----快速排序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; QuickSort(L); cout<<"-----希尔排序-----"<<endl; Create_Sq(L); cout<<"-----希尔排序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; ShellSort(L,dlta); cout<<"-----堆排序-----"<<endl; Create_Sq(L); cout<<"-----堆排序列为-----"<<endl; for(i=1;i<=L.length;i++) cout<<" "<<L.r[i].key; HeapSort(H);
}
