算法学习与实践之归并排序

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

int n;
int *a;

int src(void)
{
	printf("src:\n");
	srand((unsigned int)time(NULL));
	for(int i = 0; i < n; i++) {
		a[i] = rand() % 1000000;
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

int dst(void)
{
	printf("dst:\n");
	for(int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

void Merge(int A[], int p, int q, int r)
{
	int *L,*R;
	int i,j,k;

	//printf("Merge: %d %d %d\n\r", p, q, r);

	L = (int *)malloc((q - p + 1) * sizeof(int));
	R = (int *)malloc((r - q) * sizeof(int));

	//printf("L: ");
	for(i = 0; i <= (q - p); i++) {
		L[i] = A[i + p];
		//printf("%d ", L[i]);
	}
	//printf("\n\r");
	//printf("R: ");
	for(j = 0; j <= (r - q - 1); j++) {
		R[j] = A[j + q + 1];
		//printf("%d ", R[j]);
	}
	//printf("\n\r");
	//printf("\n\r");

	i = 0; 
	j = 0;
	//printf("A: ");
	for(k = p; k <= r; k++) {
		if(i > (q - p)) {
			A[k] = R[j];
			j++;
			//printf("%d ", A[k]);
			continue;
		}

		if(j > (r - q - 1)) {
			A[k] = L[i];
			i++;
			//printf("%d ", A[k]);
			continue;
		}

		if((i <= (q - p)) && (j <= (r - q - 1))) {
			if(L[i] > R[j]) {
				A[k] = R[j];
				j++;
				//printf("%d ", A[k]);
			} else {
				A[k] = L[i];
				i++;
				//printf("%d ", A[k]);
			}
		}
		//printf("%d ", A[k]);
	}
	//printf("\n\r");
	//printf("\n\r");
	
	free(L);
	free(R);
}

void MergeSort(int A[], int p, int r)
{
	int q;

	if(r > p) {
		q = p + (r - p) / 2;
		MergeSort(A, p, q);
		MergeSort(A, q + 1, r);
		Merge(A, p, q, r);
	}
}

void sort(int A[], int N)
{
	MergeSort(A, 0, N-1);
}

int main(void)
{
	n = 10000;
	a = (int *)malloc(n * sizeof(int));
	src();
	sort(a, n);
	dst();
	free(a);
	return 0;
}