目錄

一，歸并排序（遞歸）

1，基本思想

?2，思路實現(xiàn)

二，歸并排序（非遞歸）

1，思路實現(xiàn)

2，歸并排序的特性總結：

一，歸并排序（遞歸）

1，基本思想

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用；

將已有序的子序列合并，得到完全有序的序列；

即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并；

歸并排序核心步驟：

?2，思路實現(xiàn)

這個歸并排序乍一看像一顆二叉樹，事實也是如此，如上圖所示我們需要不斷的拆分直至拆成一個元素此時就是有序的，然后再合并，合并的時候不要選擇原地合并（原地合并時間復雜度很高），需要開辟與數(shù)組同等大小的空間用來存放數(shù)據(jù)；

主函數(shù)整體框架：

//歸并排序
void MergerSort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//開辟同等大小數(shù)組
	int* tmp = (int*)malloc((end - begin + 1)*sizeof(int));
	//歸并
	Merger(arr, tmp, begin, end);
	free(tmp);
	tmp = NULL;
}

然后我們就要開始實現(xiàn) Merger 函數(shù)，是數(shù)據(jù)歸并了；

把數(shù)組拆分成一個數(shù)據(jù)后開始合并，剛開始一 一合并，然后二 二合并，然后四 四合并，直至全數(shù)組合并完；

//歸并
void Merger(int* arr, int* tmp,int begin,int end)
{
	int mid = (begin + end) / 2;
	if (begin == end)
	{
		return;
	}
	//排序【begin,mid】& 【mid+1,end】
	Merger(arr, tmp, begin,mid);
	Merger(arr, tmp, mid+1, end);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = 0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while(begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//進行拷貝
	memcpy(arr + begin, tmp, (end - begin+1)*sizeof(int));
}

然后我們運行測試一下：

可以看到是有序的，選擇排序就?OK?了；

其實跟二叉樹的前序遍歷有異曲同工之處，前后知識都是連貫起來的；

二，歸并排序（非遞歸）

1，思路實現(xiàn)

現(xiàn)在我們來拿捏一下非遞歸版的歸并排序，其實也還是換湯不換藥；

其實新思路是這個圖的下半部分，我們先讓數(shù)據(jù)一 一合并，然后再二 二合并，然后再四 四合并程倍數(shù)增長，有人問如果越界了怎么辦？沒關系我們后面會做越界處理的；

直接上代碼！

//歸并排序(非遞歸)
void MergerSortNon(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//開辟同等大小數(shù)組
	int* tmp = (int*)malloc((end - begin + 1) * sizeof(int));
	int gap = 1;
	int j = 0;
	while (gap < end)
	{
		for (j = 0; j < end; j += 2 * gap)
		{
			int begin1 = j, end1 = begin1+gap-1;
			int begin2 =end1+1, end2 = begin2+gap-1;
			int i = 0;
			//處理邊界問題
			if (end1 >= end)
			{
				break;
			}
			if (end2 >end)
			{
				end2 = end;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])
				{
					tmp[i++] = arr[begin1++];
				}
				else
				{
					tmp[i++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[i++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[i++] = arr[begin2++];
			}
			//進行拷貝
			memcpy(arr + j, tmp, (end2 - j+ 1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

我們來運行測試一下：

可以看到是有序的，選擇排序就?OK?了；

2，歸并排序的特性總結：

1，?歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題

2，?時間復雜度：O(N*logN)

3，?空間復雜度：O(N)

4，?穩(wěn)定性：穩(wěn)定

第四階段就到這里了，帶大家繼續(xù)吃肉！

后面博主會陸續(xù)更新；

如有不足之處歡迎來補充交流！

完結。。

文章來源地址http://www.zghlxwxcb.cn/news/detail-713636.html

到了這里，關于【數(shù)據(jù)結構】手撕歸并排序（含非遞歸）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！