歸并排序概念

1945年，約翰·馮·諾依曼（John von Neumann）發(fā)明了歸并排序，這是典型的分治算法的應(yīng)用。

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

歸并排序算法思路

歸并排序算法有兩個基本的操作，一個是分，也就是把原數(shù)組劃分成兩個子數(shù)組的過程。另一個是治，它將兩個有序數(shù)組合并成一個更大的有序數(shù)組。

1> 將待排序的線性表不斷地切分成若干個子表，直到每個子表只包含一個元素，這時，可以認為只包含一個元素的子表是有序表。
2> 將子表兩兩合并，每合并一次，就會產(chǎn)生一個新的且更長的有序表，重復(fù)這一步驟，直到最后只剩下一個子表，這個子表就是排好序的線性表。

相信大家都知道如何將兩個有序序列合為一個有序序列吧：

那么如何得到有序的子序列呢？當(dāng)序列分解到只有一個元素或是沒有元素時，就可以認為是有序了，這時分解就結(jié)束了，開始合并：

歸并排序遞歸實現(xiàn)

歸并排序，從其思想上看就很適合使用遞歸來實現(xiàn)，并且用遞歸實現(xiàn)也比較簡單。其間我們需要申請一個與待排序列大小相同的數(shù)組用于合并過程兩個有序的子序列，合并完畢后再將數(shù)據(jù)拷貝回原數(shù)組。

代碼示例：

//歸并排序（子函數(shù)）
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)//歸并結(jié)束條件：當(dāng)只有一個數(shù)據(jù)或是序列不存在時，不需要再分解
	{
		return;
	}
	int mid = left + (right - left) / 2;//中間下標
	_MergeSort(a, left, mid, tmp);//對左序列進行歸并
	_MergeSort(a, mid + 1, right, tmp);//對右序列進行歸并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	//將兩段子區(qū)間進行歸并，歸并結(jié)果放在tmp中
	int i = left;
	while (begin1 <= end1&&begin2 <= end2)
	{
		//將較小的數(shù)據(jù)優(yōu)先放入tmp
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//當(dāng)遍歷完其中一個區(qū)間，將另一個區(qū)間剩余的數(shù)據(jù)直接放到tmp的后面
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//歸并完后，拷貝回原數(shù)組
	int j = 0;
	for (j = left; j <= right; j++)
		a[j] = tmp[j];
}
//歸并排序（主體函數(shù)）
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//申請一個與原數(shù)組大小相同的空間
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);//歸并排序
	free(tmp);//釋放空間
}

時間復(fù)雜度：O(N*logN)??空間復(fù)雜度：O(N)

歸并排序非遞歸實現(xiàn)

歸并排序的非遞歸算法并不需要借助棧來完成，我們只需要控制每次參與合并的元素個數(shù)即可，最終便能使序列變?yōu)橛行颍?br>
當(dāng)然，以上例子是一個待排序列長度比較特殊的例子，我們?nèi)羰窍雽懗鲆粋€廣泛適用的程序，必定需要考慮到某些極端情況：

情況一：
?當(dāng)最后一個小組進行合并時，第二個小區(qū)間存在，但是該區(qū)間元素個數(shù)不夠gap個，這時我們需要在合并序列時，對第二個小區(qū)間的邊界進行控制。

情況二：
?當(dāng)最后一個小組進行合并時，第二個小區(qū)間不存在，此時便不需要對該小組進行合并。
?

情況三：
?當(dāng)最后一個小組進行合并時，第二個小區(qū)間不存在，并且第一個小區(qū)間的元素個數(shù)不夠gap個，此時也不需要對該小組進行合并。（可與情況二歸為一類）
?

只要把控好這三種特殊情況，寫出歸并排序的非遞歸算法便輕而易舉了。

代碼示例：

//歸并排序（子函數(shù)）
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
	int j = begin1;
	//將兩段子區(qū)間進行歸并，歸并結(jié)果放在tmp中
	int i = begin1;
	while (begin1 <= end1&&begin2 <= end2)
	{
		//將較小的數(shù)據(jù)優(yōu)先放入tmp
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//當(dāng)遍歷完其中一個區(qū)間，將另一個區(qū)間剩余的數(shù)據(jù)直接放到tmp的后面
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//歸并完后，拷貝回原數(shù)組
	for (; j <= end2; j++)
		a[j] = tmp[j];
}
//歸并排序（主體函數(shù)）
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//申請一個與待排序列大小相同的空間，用于輔助合并序列
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	int gap = 1;//需合并的子序列中元素的個數(shù)
	while (gap < n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (begin2 >= n)//最后一組的第二個小區(qū)間不存在或是第一個小區(qū)間不夠gap個，此時不需要對該小組進行合并
				break;
			if (end2 >= n)//最后一組的第二個小區(qū)間不夠gap個，則第二個小區(qū)間的后界變?yōu)閿?shù)組的后界
				end2 = n - 1;
			_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并兩個有序序列
		}
		gap = 2 * gap;//下一趟需合并的子序列中元素的個數(shù)翻倍
	}
	free(tmp);//釋放空間
}

時間復(fù)雜度：O(N*logN)??空間復(fù)雜度：O ( N )文章來源地址http://www.zghlxwxcb.cn/news/detail-454043.html

到了這里，關(guān)于這個 歸并排序詳解過程 我能吹一輩子?。?！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！