C語言歸并排序如何應(yīng)用

這篇文章主要介紹“C語言歸并排序如何應(yīng)用”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“C語言歸并排序如何應(yīng)用”文章能幫助大家解決問題。

一.歸并排序

1.1歸并排序引入

對于堆排序來說，因?yàn)橛玫搅送耆鏄涞纳疃仁牵╨og2n+1）的特性，所以效率就比較高，但是堆結(jié)構(gòu)的設(shè)計(jì)比較復(fù)雜，現(xiàn)在我們想要可以直接利用完全二叉樹來排序的方法，這個(gè)方法就是歸并排序。

1.2歸并排序的概念

歸并排序是建立在歸并操作上的一種有效的排序算法，歸并排序?qū)π蛄械脑剡M(jìn)行逐層折半分組，然后從最小分組開始比較排序，合并成一個(gè)大的分組，逐層進(jìn)行，最終所有的元素都是有序的。

1.3歸并排序的原理

原理：假設(shè)初始序列含有n個(gè)記錄，則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長度為1，然后兩兩歸并，得到n/2個(gè)長度為2或1的有序子數(shù)列，再兩兩歸并，如此重復(fù)直到得到一個(gè)長度為n的有序序列為止。

1.4實(shí)例說明

(1).以4，5，8，1，7，2，6，3為例，排序過程：

(2).以84，9，18，19，48，12，90，84，8，12為例，排序過程：

這里的兩兩合并指的是兩個(gè)組合并；

每組的數(shù)據(jù)單獨(dú)看是有序的。

1.5具體步驟說明

以實(shí)例中的第一個(gè)為例：

序列逐層拆分如下：

然后從下往上逐層合并，首先對第一層序列1（只包含元素4）和序列2（只包含元素5）進(jìn)行合并

創(chuàng)建一個(gè)大序列，序列長度為兩個(gè)小序列長度之和，A、B指針分別指向兩個(gè)小序列的第一個(gè)元素，C指向大序列的第一個(gè)元素

比較A、B指向的元素，4小于5，將4填入C指向的元素，C、A往右移一位

此時(shí)，序列1已經(jīng)沒有元素，將序列2的元素依次填入大序列中

序列8和1，序列7和2，序列6和3，用同樣的方式填入新的序列

接著，以4、5為序列1，1、8為序列2，繼續(xù)進(jìn)行合并

創(chuàng)建一個(gè)序列長度為4的大序列，A指向序列1的第一個(gè)元素4，B指向序列2的第一個(gè)元素1，C指向大序列的第一個(gè)元素

4和1比較，4大于1，1填入C指向的元素，C、B往右移一位

4和8比較，4小于8，4填入C指向的元素，C、A往右移一位

5和8比較，5小于8，5填入C指向的元素，C、A往右移一位

自此，序列1已經(jīng)沒有元素，將序列2的元素依次填入大序列中

序列2、7和序列3、6以同樣的方式合并成新的序列

最后，將序列1、4、5、8和序列2、3、6、7以同樣的方式繼續(xù)合并成新的序列

所有元素均已排好。

1.6代碼實(shí)現(xiàn)

void MergeSort(int *arr, int len)
{
	for(int i=1; i<len; i*=2)// O（logn）
	{
		Merge(arr, len, i);
	}
}
//一次劃分函數(shù)  核心函數(shù)  //返回基準(zhǔn)值最終所在下標(biāo)
int Partition(int *arr, int left, int right)
{
	//先講arr數(shù)組里的[left， right]的第一個(gè)值 作為基準(zhǔn)值
	int tmp = arr[left];
	while(left < right)
	{
		while(left<right && arr[right] > tmp)//左右邊界沒有相遇且當(dāng)前右邊的值大于基準(zhǔn)值tmp
		right--;
		if(left < right)//如果此時(shí)，左右邊界沒有相遇，那就只能證明右邊right找到了一個(gè)小于等于基準(zhǔn)值tmp的值
		{
			arr[left] = arr[right];
		}
		else
		{
			break;
		}
		while(left<right && arr[left] <= tmp)//左右邊界沒有相遇且當(dāng)前左邊的值小于等于基準(zhǔn)值tmp
		left++;
		if(left < right)//如果此時(shí)，左右邊界沒有相遇，那就只能證明左邊left找到了一個(gè)大于基準(zhǔn)值tmp的值
		{
			arr[right] = arr[left];
		}
		else
		{
			break;
		}
	}
	arr[left] = tmp;//此時(shí) 因?yàn)?nbsp;left == right
	return left;//return right ok
}

1.7性能分析

• 時(shí)間復(fù)雜度：最好，最壞，平均的時(shí)間復(fù)雜度均為O(nlogn)。

• 空間復(fù)雜度：空間復(fù)雜度O（n）。

• 穩(wěn)定性：穩(wěn)定。

關(guān)于“C語言歸并排序如何應(yīng)用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識點(diǎn)。