? ? ? ?1、介紹

? ? ? ? 歸并排序既可以是內(nèi)排序（在內(nèi)存上的數(shù)據(jù)排序），也可以是外排序（磁盤(pán)上）（硬盤(pán)）（在文件中的數(shù)據(jù)排序）。

? ? ? ? 其他排序一般都是內(nèi)排序。

????????區(qū)別于快速排序的非遞歸，歸并排序非遞歸不適合使用棧。

? ? ? ? 因?yàn)榭焖倥判虻谋举|(zhì)是一種前序遞歸，而歸并排序的本質(zhì)是一種后序遞歸，并沒(méi)有“根”來(lái)區(qū)分左右。

? ? ? ? 那么歸并排序的非遞歸應(yīng)該怎么樣實(shí)現(xiàn)呢？

? ? ? ? 2、思想

? ? ? ? 我們先想想歸并的思想和目的：遞歸的分治是將數(shù)組分割成兩邊有序的子序列，然后再合并這兩個(gè)。那么我們是否可以直接將數(shù)組中兩兩元素歸并呢？答案是：對(duì)的！因?yàn)槲覀儗?shù)組中所有元素看作兩兩一組（每組數(shù)據(jù)中都各有一個(gè)元素），那么這一組中的兩個(gè)元素單個(gè)來(lái)看就是有序的子序列，然后合并這兩個(gè)元素。再往上就是四四一組（每組數(shù)據(jù)中都各有兩個(gè)有序的元素），八八一組........

? ? ? ? 聽(tīng)起來(lái)好像很簡(jiǎn)單，其實(shí)坑很多，下面慢慢實(shí)現(xiàn)。

? ? ? ? 3、代碼

void MergeSortNonR_incline(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}

	int gap = 1;//1-1歸
	//gap代表歸并每組數(shù)組個(gè)數(shù)，即gap個(gè)和gap個(gè)歸并
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)//[0,n)
		{
			int begin1 = i, end1 = i + gap - 1;//第一組
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二組
			//[begin1,end1],[begin2,end2] 歸并
			//[0,0]-[1,1]歸，[2,2]-[3,3],[4,4]-[5,5]....
			//[0,1]-[2,3]歸, [4,5]-[6,7]....
			//[0,3]-[4,7]歸, [8,11]-[11,15]......
			// ......
			//注意：begin1不會(huì)越界，end1，begin2，end2都可能越界，所以要修正
			if (end1 >= n || begin2>=n)
				break;
			if (end2 >= n)
				end2 = n - 1;

			//合并，將arr中對(duì)應(yīng)位置，放入tmp的對(duì)應(yīng)位置
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{

				if (arr[begin1] < arr[begin2])
					tmp[j++] = arr[begin1++];
				else
					tmp[j++] = arr[begin2++];
			}


			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}

			//[begin1,end1],[begin2,end2]
			memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));//每次歸并完拷貝回去
		}
		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

? ? ? ? 4、實(shí)現(xiàn)效果

	int arr[] = { 1,6,41,32,5,12,7,11 };
	int size = sizeof(arr) / sizeof(int);
	printf("原數(shù)組\n");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	printf("排序后\n");
	MergeSortNonR_incline(arr, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

原數(shù)組：1 6 41 32 5 12 7 11

排序后：1 5 6 7 11 12 32 41文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-801445.html

到了這里，關(guān)于排序算法8----歸并排序（非遞歸）（C）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！