[C++知识库]多路归并结合败者树排序（C语言）

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
void merge(int arr[],int l,int r,int mid){
	int ar[r-l+1];
	int t,k;
	for(t=0;t<r-l+1;t++){
		ar[t]=arr[t+l];
	}
	int i=l,j=mid+1;
	for(k=l;k<r+1;k++){
		if(i>mid){
			arr[k]=ar[j-l];
			j++;
		}else if(j>r){
			arr[k]=ar[i-l];
			i++;
		}else if(ar[i-l]<=ar[j-l]){
			arr[k]=ar[i-l];
			i++;
		}else{
			arr[k]=ar[j-l];
			j++;
		}
	}
}
void mergeSort(int arr[],int l,int r){
	if(l>=r){
		return;
	}
	int mid=(l+r)/2;
	mergeSort(arr,l,mid);
	mergeSort(arr,mid+1,r);
	merge(arr,l,r,mid);
}
int Max(int a[],int index[],int i,int j,int *win){
	if(a[index[i]]>a[index[j]]){
		*win=j;
		return i;
	}
	*win=i;
	return j;
}
void loserSort(int a[],int b[],int l,int r,int n,int m){
	int index[n];
	for(int i=0;i<n;i++){
		index[i]=i*m;
	}
	int heap[2*n];
	int winner[2*n];
	int win;
	for(int i=n;i<2*n;i++){
		heap[i]=i-n;
		winner[i]=i-n;
	}
	for(int i=(2*n-1)/2;i>=1;i--){
		heap[i]=Max(a,index,winner[2*i],winner[2*i+1],&win);
		winner[i]=win;
	}
	heap[0]=winner[1];
	int count[n];
	for(int i=0;i<n;i++){
		count[i]=0;
	}
	for(int i=0;i<n*m;i++){
		b[i]=a[index[heap[0]]];
		count[heap[0]]++;
		if(count[heap[0]]>=m){
			index[heap[0]]=n*m;
		}else{
			index[heap[0]]++;
		}
		int j=(heap[0]+n)/2;
		while(j!=0){
			heap[j]=Max(a,index,winner[2*j],winner[2*j+1],&win);
			winner[j]=win;
			j/=2;
		}
		heap[0]=winner[1];
	}
}
int main(){
	int n=6;
	int m=100;
	int a[n*m+1];
	int b[n*m];
	srand(time(NULL));
	int i;
	for(i=0;i<n*m;i++){
		a[i]=rand()%10000;
	}
	a[i]=pow(2,30)-1;
	printf("原数组:\n");
	for(int i=0;i<n*m;i++){
		printf("  %d",a[i]);
	}
	printf("\n\n\n");
	for(int i=0;i<n;i++){
		mergeSort(a,i*m,(i+1)*m-1);
	}
	loserSort(a,b,0,n*m,n,m);
	printf("六路败者树排序后:\n");
	for(int i=0;i<n*m;i++){
		printf("  %d",b[i]);
	}
	return 0;
}

?