else first--;

if(0==j)j=n;

cache[j-1]=nu[i].key;

s++; } } }

for(i=first,j=0;j

nu[j].key=cache[i];

i++;

if(i==n)i=0; }

cout<<\移动次数=\比较次数=\ }

//二路归并

void Merge(sqlist a, sqlist b, int low, int mid, int high) { int i= low, j = mid + 1,k = low; while ((i <= mid) && (j <= high)) { if(a[i].key <= a[j].key) { h++; b[k++] = a[i++]; g++;

++i; } else { h++; b[k++] = a[j++]; g++; ++j; } ++k; }

// if(i <= mid) while(i <= mid) { b[k++] = a[i++]; g++; } //else while(j <= high) { b[k++]=a[j++]; g++; } }

//进行一趟归并

void MergePass(sqlist a, sqlist b, int n, int lenth) { int i = 0, k=0; while(i <= n - 2*lenth) { Merge(a, b, i, i + lenth -1, i + 2*lenth -1); i += 2*lenth; } if(i < n - lenth )

{ Merge(a, b, i, i + lenth -1, n-1); } else for(k = i; k <= n-1; k++) {b[k] = a[k]; g++; } }

//进行二路归并

void MergeSort(sqlist a, int n) {sqlist b;

//int* b=(int*)malloc(n*sizeof(int)); int lenth = 1; while(lenth < n/2+1) {

MergePass(a, b,n, lenth); lenth = 2*lenth; MergePass(b, a, n, lenth); lenth = 2*lenth; }

cout<<\移动次数=\比较次数=\ }

//堆排序

void sift(sqlist r,int s,int m) { int j; rec x; x=r[s];

for(j=2*s;j<=m;j*=2) {q++;

if(j

q++;

if(!(x.key

void heapsort(sqlist &r,int m) {

int i;rec w;

for(i=m/2;i>0;--i) sift(r,i,m); for(i=m;i>1;--i) {

w=r[i];r[i]=r[1]; r[1]=w; p+=3;

sift(r,1,i-1); } }

void sorting(sqlist &r,int t) {

BeforeSort(); heapsort(r,t); display(p,q); }

void init(int a[])//随机生成N个整数并 { int i;

//#define N 100;

srand ( ( unsigned int ) time ( NULL ) ); for(i=0;i

void main() { int g=0; int h=0;