dmedian.c

四个小算法。红黑树

#include "stdio.h"
#include "stdlib.h"
#define MAXNUM 10
#define leftChild(i)        2*(i)+1
void GenerateRand(int A[MAXNUM],int B[MAXNUM]);
void  sift(int vector[MAXNUM], int i, int n)

{
	int child; 
	int temp =vector[i];
	child=leftChild(i);                       /* Rchild是R0的左子女 */
	while(child<n)
	{
		if((child<n-1)&&(vector[child]<vector[child+1]))
			child++;           /* child 指向Ri的左、右子女中排序码较大的结点 */
		if(temp<vector[child])
		{ 
			vector[i]=vector[child]; 
			/* 将Rchild换到父结点位置，进入下一层继续调整*/
			i=child;  
			child=leftChild(i);
		}
		else
			break;                                    /* 调整结束 */
	}
	vector[i]=temp;                            /* 将记录Ri放入正确位置 */
}

void  heapSort(int vector[MAXNUM])                 /* 对记录R0到Rn-1进行堆排序 */

{
	int i, n;
	int temp; 
	n=MAXNUM;
	for(i=n/2-1; i>=0; i--)
		sift(vector,i,n);                                    /* 建立初始堆 */
	for(i=n-1; i>0; i--)                                       /* 进行n-1趟堆排序 */
	{
		temp=vector[0];                         /* 当前堆顶记录和最后一个记录互换 */
		vector[0]=vector[i];
		vector[i]=temp;
		sift(vector,0,i);                                    /* 从R0到Ri-1重建堆 */
	}
}

void GenerateRand(int A[MAXNUM],int B[MAXNUM])
{
	int i,j,tmp;
    for(i=0;i<MAXNUM;++i)
	{   
		
		A[i]=i;
		B[i]=i+4;
	}
	srand(time(0));
	for(i=0;i<MAXNUM;++i)
	{   
		int chpos=rand()%MAXNUM;
		tmp=A[i];
		A[i]=A[chpos];
        A[chpos]=tmp;
		
	}
	srand(time(0)+100);
	for(i=0;i<MAXNUM;++i)
	{   
		int chpos=rand()%MAXNUM;
		tmp=B[i];
		B[i]=B[chpos];
        B[chpos]=tmp;
		
	}
}

int HalfFind(int A[MAXNUM],int num,int p,int r)
{
	int m;
	while(p<r)
	{
		if(A[(p+r)/2]<num)
			p=(p+r)/2+1;
		else if(A[(p+r)/2]>num)
			r=(p+r)/2-1;
		else
			return (p+r)/2;
	}
	return r;

}
int Dmedian(int A[MAXNUM],int B[MAXNUM])
{
	int Ap,Ar,Bp,Br,n,routine;
	Ap=0;Ar=MAXNUM-1;
	Bp=0;Br=MAXNUM-1;
	n=0;
	while(n<MAXNUM)
	{
		if(A[Ap]>B[Bp])
		{
			routine=0;
			Bp=HalfFind(B,A[Ap],Bp,Br);
		}
		else if(A[Ap]<B[Bp])
		{
			routine=1;
			Ap=HalfFind(A,B[Bp],Ap,Ar);
		}
		else
		{
			routine=2;
			Ap++;
			Bp++;
		}
		n=Ap+Bp;
	}
	if(routine==0)
	{
		return B[MAXNUM-Ap];
	}
	else if(routine==1)
	{
		return A[MAXNUM-Bp];
	}
	else if(routine==2)
	{
		return B[MAXNUM-Ap];
	}

}
int main()
{
	int A[MAXNUM],B[MAXNUM];
	int median,i;
	GenerateRand(A,B);
	for(i=0;i<MAXNUM;++i)
		printf("%d ",A[i]);
	printf("\n");
	for(i=0;i<MAXNUM;++i)
		printf("%d ",B[i]);
	printf("\n");
	heapSort(A);
	heapSort(B);
	median=Dmedian(A,B);
	printf("%d\n",median);
	return 1;
}