遞歸是可以向非遞歸進(jìn)行變化的：
比如很經(jīng)典的斐波那契數(shù)列可以用遞歸實(shí)現(xiàn)也可以用循環(huán)實(shí)現(xiàn)

但是有些復(fù)雜的遞歸僅僅依靠循環(huán)是很難控制的，
所以我們需要借助數(shù)據(jù)結(jié)構(gòu)中的棧與隊(duì)列幫助我們用非遞歸模擬遞歸，
故有的時(shí)候我們說(shuō)非遞歸不是遞歸卻勝似遞歸

通過(guò)本文可以更好的對(duì)比來(lái)理解兩者不同之處

快速排序的非遞歸：

先說(shuō)結(jié)論，我們會(huì)使用棧來(lái)模擬快速排序的遞歸----棧所在的文章。

注意：下圖所使用的單趟排序?yàn)?code>前后指針?lè)?/code>----前后指針?lè)ㄋ谖恼隆?br>
注意：

1. 我們選擇先壓右邊，這樣StackTop得到的就是左邊，因?yàn)闂?code>先進(jìn)后出的原理
2. 雖然我們自己造的棧push一次只能存儲(chǔ)一個(gè)數(shù)據(jù)，但是我們push兩次就可以解決這個(gè)問(wèn)題

圖示就很好的展示了如何用棧來(lái)模擬遞歸的過(guò)程。
可以與代碼相互進(jìn)行加強(qiáng)理解：

代碼：

//前后指針
int PartSort(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int key = a[left];

	while (cur <= right)
	{
		if (a[cur] < key)
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[left]);
	return prev;
}

void QuickSortNonR(int* a, int begin, int end)
{
	Stack s;
	StackInit(&s);
	StackPush(&s, end);
	StackPush(&s, begin);

	while (!StackEmpty(&s))
	{
		int left = StackTop(&s);
		StackPop(&s);
		int right = StackTop(&s);
 		StackPop(&s);
		int keyi = PartSort(a, left, right);

		//[begin keyi-1] [keyi+1 right]
		if (keyi + 1 < right)
		{
			StackPush(&s, right);
			StackPush(&s, keyi + 1);
		}
		if (left < keyi - 1)
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, left);
		}
	}

	StackDestroy(&s);
}

歸并排序的非遞歸：

那么歸并是否也是使用棧來(lái)模擬呢？
答案是否定的，同時(shí)隊(duì)列也是錯(cuò)誤的

因?yàn)槲覀儼l(fā)現(xiàn)：

快排的模擬遞歸是前序，即遞下來(lái)的過(guò)程就完成了排序，不需要歸回去。

而歸并排序的思想呢？

在遞的時(shí)候只是完成了分組，每一組是返回條件的最小單元，還沒(méi)有進(jìn)行歸并，
歸并的過(guò)程是在分組之后完成的，是一種后序的思想

故我們當(dāng)然不能用棧來(lái)模擬歸并，即使可以達(dá)到分組的效果，那之后呢？

這里我們選擇使用數(shù)組，需要一個(gè)額外的數(shù)組，空間復(fù)雜度仍然是O(N)

那我們是如何進(jìn)行模擬的呢？

這張圖就比較好的體現(xiàn)了非遞歸的思想，直接進(jìn)行歸并，這就要求我們要對(duì)數(shù)組的下標(biāo)使用的比較靈活。

我們使用gap作為每一組（有序的組）的元素個(gè)數(shù)
先來(lái)看一次歸并的代碼，雖然長(zhǎng)，但是分開來(lái)看就比較一目了然

這一部分是對(duì)下標(biāo)的控制，
我們完成這一部分再嵌套一個(gè)控制gap的循環(huán)就得到完整的代碼
int gap = 1;
int j = 0;
for (int i = 0; i < n; i += (2 * gap))
{
	int begin1 = i, end1 = i + gap - 1;
	int begin2 = end1 + 1, end2 = begin2 + gap - 1;
	
	這一部分是防止數(shù)組越界的操作，
	當(dāng)end1與begin2越界我們break即可
	因?yàn)楫?dāng)上兩者越界時(shí)，我們所在的區(qū)間已經(jīng)有序，不需要排序
	if (end1 >= n || begin2 >= n)
	{
		break;
	}
	if (end2 >= n)
	{
		end2 = n - 1;
	}
	... 接下來(lái)是進(jìn)行兩者合并的邏輯
}

這是兩個(gè)”數(shù)組”進(jìn)行合并的邏輯文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-813140.html

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[j++] = a[begin1++];
		}
		else
		{
			tmp[j++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[j++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[j++] = a[begin2++];
	}
	memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));

代碼：

void MergerSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		int j = 0;
		for (int i = 0; i < n; i += (2 * gap))
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = end1 + 1, end2 = begin2 + gap - 1;

			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】非遞歸實(shí)現(xiàn)快速排序與歸并排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！