归并排序

归并排序 2013年10月31日 22:49:05

#include <stdio.h>
#include <stdlib.h>


void merge(int a[],int left,int middle, int right)
{
	int i = left;
	int j = middle + 1;
	int k = 0;
	int *b = (int*)malloc(sizeof(int)*(right - left + 1));
	while(i <= middle && j <= right)
	{
		if(a[i] > a[j])
		{
			b[k++] = a[j++];
		}else{
			b[k++] = a[i++];
		}
	}

	while (i <= middle)
	{
		b[k++] = a[i++];
	}

	while (j <= right)
	{
		b[k++] = a[j++];
	}

	for(i= left,k = 0; i <= right;i++,k++)
	{
		a[i] = b[k];
	}

	free(b);
}

void mergeSort(int a[],int left,int right)
{
	if(left==right)
	{
		return;
	}

	int middle = (left + right)/2;
	mergeSort(a,left,middle);
	mergeSort(a,middle+1,right);

	merge(a,left,middle,right);
}

int main()
{
	int x[]={4,-5,0,3,-1,12,9,-7,8,-4,11};
	mergeSort(x,0,10);
	for (int i = 0; i < sizeof(x)/sizeof(int); i++)
	{
		printf("%d ",x[i]);
	}
	return 0;
}