高手们,"内部排序算法比较"的思想和程序怎么写啊,帮帮我啊
通过随机数据比较各算法的关键字比较次数和关键字移动次数,
要求: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);

}