目錄

1、歸并的思想

2、歸并排序的思想

2.1 基本思想

2.2 圖解分析

3、歸并排序遞歸版本代碼實(shí)現(xiàn)

3.1 代碼解析

3.2 注意事項(xiàng)

3.2.1錯(cuò)誤劃分：[begin, mid-1]，[mid, end]

3.2.2 正確劃分：[begin, mid], [mid+1, end]

4、歸并排序的測(cè)試

5、時(shí)間復(fù)雜度、空間復(fù)雜度分析

5.1 時(shí)間復(fù)雜度

5.2 空間復(fù)雜度

1、歸并的思想

這是我們第二次了解歸并的思想了，第一次在我們之前的鏈表oj題里面，合并兩個(gè)有序鏈表，我們當(dāng)時(shí)解題的思想就是歸并的思想。

我們這次來(lái)系統(tǒng)的學(xué)習(xí)一下歸并的思想（本篇以升序?yàn)槔归_(kāi)）：

歸并兩個(gè)數(shù)組（鏈表）時(shí)，我們使用兩個(gè)指針指向不同的數(shù)組首元素，控制并遍歷兩個(gè)數(shù)組，比較兩個(gè)指針指向的值，小的我們放入開(kāi)辟的臨時(shí)數(shù)組里面，然后讓指向小值的指針往后走一步，繼續(xù)比較。不斷去比，總有一個(gè)數(shù)組先被遍歷完，由于是有序數(shù)組，另外那個(gè)沒(méi)有被遍歷完的數(shù)組直接連接到臨時(shí)數(shù)組的后面就完成了排序。

我們畫圖來(lái)理解這個(gè)思想：

2、歸并排序的思想

2.1 基本思想

歸并排序是建立在歸并操作上的一種有效的排序算法。

1.歸并排序的思想是，將一個(gè)數(shù)組二分為左右兩個(gè)數(shù)組，然后對(duì)左右兩個(gè)數(shù)組繼續(xù)進(jìn)行二分，直到分為的子區(qū)間為一個(gè)數(shù)據(jù)的時(shí)候，這一個(gè)數(shù)據(jù)一定是有序的，便不再二分。

2.接下來(lái)就對(duì)左右兩個(gè)子區(qū)間進(jìn)行排序合并，不斷排序合并，最終就實(shí)現(xiàn)了整個(gè)數(shù)組的排序。

2.2 圖解分析

我們歸并的時(shí)候不是直接在原數(shù)組上就交換的，直接在原數(shù)組上操作會(huì)產(chǎn)生覆蓋，導(dǎo)致錯(cuò)誤。因此我們是malloc一個(gè)與原數(shù)組大小相同的空間tmp，將每次合并后的值拷貝到tmp中，合并一次拷貝一次，最中tmp數(shù)組為有序，再將tmp使用memcpy拷貝回原數(shù)組，再free(tmp) （防止內(nèi)存泄漏），整個(gè)排序就完成了。

3、歸并排序遞歸版本代碼實(shí)現(xiàn)

// 歸并排序遞歸實(shí)現(xiàn)
// 時(shí)間復(fù)雜度：O(N*logN)
// 空間復(fù)雜度：O(N + logN)
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	//[begin, mid] [mid+1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (NULL == tmp)
	{
		perror("malloc fail:");
		return;
	}
	_MergeSort(a, 0, n-1, tmp);
	free(tmp);
}

3.1 代碼解析

我們?cè)谶@一段使用了遞歸，遞歸的思想就是二分，將數(shù)組分為左右兩個(gè)區(qū)間，然后再對(duì)左右兩個(gè)區(qū)間繼續(xù)進(jìn)行二分，當(dāng) begin >= end 時(shí)，就是最小的區(qū)間，然后我們就進(jìn)行排序+合并。

這一段就是排序+合并，我們對(duì)兩個(gè)子區(qū)間進(jìn)行排序+合并，思路就是我們歸并的思想。這里要注意，我們tmp的下標(biāo)是begin，因?yàn)槲覀冃枰獙⒚恳粚雍喜⒌闹迪确胚M(jìn)tmp中，然后再拷貝到原數(shù)組里，如果是0，拷貝回去的時(shí)候就會(huì)出現(xiàn)錯(cuò)誤。

3.2 注意事項(xiàng)

在劃分左右區(qū)間的時(shí)候一定是 [begin, mid]，[mid+1, end]，

不能是 [begin, mid-1]，[mid, end]?。?！

這里很容易出錯(cuò)，看著邏輯上沒(méi)問(wèn)題，但是在排序的時(shí)候就會(huì)出問(wèn)題。

3.2.1錯(cuò)誤劃分：[begin, mid-1]，[mid, end]

3.2.2 正確劃分：[begin, mid], [mid+1, end]

總結(jié)：造成第一種劃分死循環(huán)的原因是，當(dāng)我們 mid = begin+end/2 時(shí)，計(jì)算器是向下取整的，所以一旦向下取整的時(shí)候，我們的區(qū)間就要包含mid這個(gè)值，這樣就會(huì)補(bǔ)上向下取整造成的舍去。

4、歸并排序的測(cè)試

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid] [mid+1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (NULL == tmp)
	{
		perror("malloc fail:");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}
void test()
{
	int a[] = { 6,3,2,1,5,7,9 };
	Print(&a, sizeof(a) / sizeof(int));
	MergeSort(&a, sizeof(a) / sizeof(int) - 1);
	Print(&a, sizeof(a) / sizeof(int));
}
int main()
{
	test();

	return 0;
}

測(cè)試結(jié)果：

5、時(shí)間復(fù)雜度、空間復(fù)雜度分析

5.1 時(shí)間復(fù)雜度

歸并排序區(qū)間不斷二分，時(shí)間復(fù)雜度為O(logN)；然后再合并，時(shí)間復(fù)雜度為O(N)。

整體的時(shí)間復(fù)雜度為o(N*logN)。

5.2 空間復(fù)雜度

因?yàn)槲覀冮_(kāi)辟了一個(gè)臨時(shí)空間用于排序，因此空間復(fù)雜度O(N)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-573259.html

到了這里，關(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)！