当前位置：首页 > news >正文

归并排序（非递归）

news 来源：原创 2024/5/3 13:47:31

前面说完了递归，虽然递归容易理解，思路清晰，但是造成了时间和空间上的浪费。那为了追求效率，就可以将递归改为迭代，进一步提高代码性能。直接上代码：

#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 10000
#define N 9
typedef struct {
	int r[MAXSIZE + 1];
	int length;
}SqList;

/*将SR[i..m]和SR[m+1..n]归并排序为TR[i..n]*/ 
void Merge(int SR[], int TR[], int i, int m, int n) {
	int j;
	int k;
	int l;
	
	for(j = m+1, k = i; i <= m && j <= n; k++) {	//将SR中的数据有小到大写入TR 
		if(SR[i] < SR[j]) {
			TR[k] = SR[i++];
		} else {
			TR[k] = SR[j++];
		}
	}
	
	if(i <= m) {	//将剩余的SR[i..m]复制到TR 
		for(l = 0; l <= m-i; l++) {
			TR[k+l] = SR[i+l];
		}
	}
	
	if(j <= n) {	//将剩余的SR[j..n]复制到TR 
		for(l = 0; l <= n-j; l++) {
			TR[k+l] = SR[j+l];
		}
	}
}

void MergePass(int SR[], int TR[], int s, int n) {
	int i = 1;
	int j;
	while(i <= n-2*s+1) {
		Merge(SR, TR, i, i+s-1, i+2*s-1);	//两两归并
		i = i+2*s; 
	}
	if(i < n-s+1) {		//归并最后的两个序列 
		Merge(SR, TR, i, i+s-1, n);
	} else {		//若最后只剩下单个子序列 
		for(j = i; j <= n; j++) {
			TR[j] = SR[j];
		}
	}
} 

void MergeSort(SqList *L) {
	int* TR = (int*)malloc(L->length * sizeof(int));
	
	int k = 1;
	while(k < L->length) {
		MergePass(L->r, TR, k, L->length);
		k = 2*k;						//子序列长度加倍 
		MergePass(TR, L->r, k, L->length);
		k = 2*k;						//子序列长度加倍
	}
} 

/*打印顺序表*/
void print(SqList L) {
	int i;
	for(i = 1; i < L.length; i++) {
		printf("%d,", L.r[i]);
	}
	printf("%d\n", L.r[i]);
}

int main() {
	int i;
	int d[N]={50,10,90,30,70,40,80,60,20};
	
	SqList L;
	for(i = 0; i < N; i++) {
		L.r[i+1] = d[i];
	}
	L.length = N;
	
	printf("排序前:\n");
    print(L);
    printf("归并排序(非递归):\n");
	MergeSort(&L);
	print(L);
	
	return 0;
}

MergeSort()：

MergeSort()函数中while循环的目的是不断地归并有序序列，k值是由1->2->4->8->16变化的。k=1时，MergePass()函数是将原来无序的数组两两归并入TR。k=2时，MergePass()函数将TR中已经两两归并的有序序列再次归并回数组L.r中，k=4至k=16重复此过程。

由这段代码可以看出，非递归的方法更加清楚直接，从最小的直至归并完成。不像递归算法，需要先拆分递归，再归并退出递归。

MergePass()函数：

此函数中while循环就是为了两两归并。s=1，n-2*s+1=8,此时我们会想到，明明有9个元素呀，为什么是1-8？因为我们的目的是两两归并，最终9条数据肯定会剩下来，无法归并。一直循环，直至第七个和第八个数据完成归并。下来，就需要处理剩下的元素了，直接加入到TR数组末尾。当MergeSort()函数再次调用MergePass()函数时，s=2，此时i就是以4为增量进行循环了，就是将两个有两个数据的有序序列合并成四个数据的有序序列，最终再将剩下的第九个数据插入到TR数组末尾。

复杂度分析：

非递归的方法避免了递归时深度为log₂n的栈空间，空间只是用到申请归并临时用的TR数组上，因此空间复杂度为O(n)。时间复杂度也有所提升，因此，应尽量考虑非递归算法