归并排序（非递归）（C语言）_c归并排序非递归csdn

判题网站：PTA

得分：25/25

#include "stdio.h"
#include "stdlib.h"
#pragma warning(disable:4996)
 
void Swap(long A[], long i, long j);
void Merge(long A[], long temp[], int L, int R, int RightEnd);
void MSort(long A[], long temp[], int L, int R);
void MergeSort(long A[], int N);
void MSort2(long A[], int L, int R);
 
int main()
{
	int N;
	scanf("%d", &N);
	long number[N];
	for (int i = 0; i < N; i++)
	{
		scanf("%ld", &number[i]);
	}
	MergeSort(number, N);
	for (int i = 0; i < N - 1; i++)
	{
		printf("%ld ", number[i]);
	}
	printf("%ld", number[N - 1]);
	return 0;
}
 
void Swap(long A[], long i, long j)
{
	long temp;
	temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}
 
void Merge(long A[], long temp[], int L, int R, int RightEnd)
{
	int LeftEnd;
	LeftEnd = R - 1;
	int j = L;
	int i = 0;
	int NumElement = RightEnd - L + 1;
	while (L <= LeftEnd && R <= RightEnd)
	{
		if (A[L] > A[R])
		{
			temp[j] = A[R];
			j++;
			R++;
		}
		else
		{
			temp[j] = A[L];
			j++;
			L++;
		}
	}
	while (L <= LeftEnd)
	{
		temp[j] = A[L];
		j++;
		L++;
	}
	while (R <= RightEnd)
	{
		temp[j] = A[R];
		j++;
		R++;
	}
	for (i = 0; i < NumElement; i++, RightEnd--)
	{
		A[RightEnd] = temp[RightEnd];
	}
}
 
void MSort(long A[], long temp[], int L, int R)
{
	int center;
	center = (L + R) / 2;
	if (L < R)
	{
		MSort(A, temp, L, center);
		MSort(A, temp, center + 1, R);
		Merge(A, temp, L, center + 1, R);
	}
}
 
void MergeSort(long A[], int N)
{
	MSort2(A, 0, N);
 
}
void MSort2(long A[], int L, int R)
{
	long temp[R];
	int length = 1;
	int i = 0;
	if (R == 1)
	{
		return;
	}
	for (length;length<R; length *= 2)
	{
		for (i = 0; i <= R - 2 * length; i += length * 2)
			Merge(A, temp, i, length + i, i + length*2-1);
		if (i + length < R)
		{
			Merge(A, temp, i, i + length, R - 1);
		}
	}
}