mergesort.h

来自「快速排序、合并排序、插入排序、堆排序、计数排序等算法的C语言实现」· C头文件 代码 · 共 57 行

#include<stdio.h>
#include<limits.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0

#define MaxValue UINT_MAX//UINT_MAX为最大无符号整数

typedef int ElemType;

//合并排序头文件
void Merge(ElemType A[],long p,long q,long r)
//数组A[p--q]和数组A[q+1--r]经合并后存放于数组A中
{
	long n1 = q - p + 1;
	long n2 = r - q;
	LinkList temp1,temp2,p1,p2;
	long i,j,k;
	temp1=InitList_L();
	temp2=InitList_L();
	for(i = 0;i < n1;i++)
		ListInsert_L(temp1,i+1,A[p+i]);
	for(j = 0;j < n2;j++)
		ListInsert_L(temp2,j+1,A[q+1+j]);
	ListInsert_L(temp1,n1+1,MaxValue);
	ListInsert_L(temp2,n2+1,MaxValue);
	p1=temp1->next;
	p2=temp2->next;
	for(k = p;k <= r;k++)
	{
		if(p1->data <= p2->data)
		{
			A[k] = p1->data;
			p1=p1->next;
		}
		else
		{
			A[k] = p2->data;
			p2=p2->next;
		}
	}
	DestroyList_L(temp1);
	DestroyList_L(temp2);
	free(p1);
	free(p2);
}
void MergeSort(ElemType A[],long p,long r)
{//合并排序算法，时间复杂度为O(n*lgn)
	long q;
	if(p < r)
	{
		q = (p + r)/2;
		MergeSort(A,p,q);
		MergeSort(A,q+1,r);
		Merge(A,p,q,r);
	}
}