书上习题2-1 在合并排序中对小数组采用插入排序。以下是我写的代码:
//合并排序+插入排序结合法 #include <iostream> #include <time.h> using namespace std; int* INSERTION_SORT(int A[],int B[],int p,int q,int r); void MERGE(int A[],int p,int q,int r); void MERGE_SORT(int A[],int p,int r,int k); void main() { clock_t start, finish; int duration; //测量一个事件持续的时间 start = clock(); const int n=10; int a[n],i; srand( (unsigned)time( NULL ) ); for( i=0;i<n;i++) { a[i]=rand()%101; } cout<<"排序前:"<<endl; for ( i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; MERGE_SORT(a,0,n,2);//K值应该最大为此数组元素个数的一半。 cout<<"排序后:"<<endl; for ( i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; finish = clock(); duration = (int)(finish - start) / CLOCKS_PER_SEC; printf( "%f seconds\n", duration ); } void MERGE(int A[],int p,int q,int r) { int n1=q-p+1,n2=r-q,i,j,flag=-1; int *L=new int[n1]; int *R=new int[n2]; L=INSERTION_SORT(A,L,p,q,n1); R=INSERTION_SORT(A,R,q+1,r,n2); i=0;j=0; L[n1]=flag; R[n2]=flag; for (int k=p;k<=r;k++) { if (L[i]==flag) { A[k]=R[j]; j++; } else if (R[j]==flag) { A[k]=L[i]; i++; } else if (L[i]>=R[j]) { A[k]=L[i]; i++; } else { A[k]=R[j]; j++; } } } int *INSERTION_SORT(int A[],int B[],int p,int q,int r) { int key; for (int i=p,j=0;i<=q,j<r;i++,j++) { B[j]=A[i]; } for (j=2;j<=r;j++) { key=B[j-1]; int i=j-1; while (i>0&&B[i-1]<key)//a[i-1]<key 变为降序排列 { B[i]=B[i-1]; i=i-1; } B[i]=key; } return B; } void MERGE_SORT(int A[],int p,int r,int k) { int q=(p+r)/k;//q=(p+r)/k if((q-p+1)<=k)//子数组长度≤k的时候就不再进行划分,而是对该子数组进行插入排序 { //当p=0时,有k<=r/k =>k<=√r kmax=√r kmin=2 return; } else { MERGE_SORT(A,p,q,k); MERGE_SORT(A,q+1,r,k); MERGE(A,p,q,r); } }
a)插入排序时间复杂度O(n^2)对于长度为k的子列表都有O(k^2),则n/k个为(k^2)*n/k=O(nk)
b)由于有n/k个子列表,那么共有log(n/k)+1层。每一层的代价是O(n),因此总共的时间复杂度为O(nlog(n/k));
c).标准的合并算法时间复杂度为O(nlog(n)),要使修改后的算法具有与标准合并排序算法一样的渐进运行时间,k的最大渐进值是logn,原来时间复杂度为O(nk + nlog(n/k)),现在变为了O(nlogn + nlog(n/logn)),忽略nlog(n/logn)的影响,这样即为O(nlogn);
d)在实践中,k的值应为:当p=0时,有k<=r/k k<=√r kmax=√r kmin=2