排序篇：歸并排序的遞歸，非遞歸以及計數(shù)排序的實現(xiàn)(C語言)

這篇具有很好參考價值的文章主要介紹了排序篇：歸并排序的遞歸，非遞歸以及計數(shù)排序的實現(xiàn)(C語言)。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

一：歸并排序

(1)歸并排序的基本思想

(2)遞歸版本

①實現(xiàn)思路

②合并

③遞歸實現(xiàn)有序

④最終代碼

(3)非遞歸版本

①實現(xiàn)思路

②控制分組

③最終代碼

(4)時間，空間復雜度分析

(5)小結(jié)

二：計數(shù)排序

(1)計數(shù)排序的基本思想

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

(3)圖解加最終代碼

(4)時間，空間復雜度分析

(5)小結(jié)

一：歸并排序

(1)歸并排序的基本思想

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。
將已有序的子序列合并，得到完全有序的序列；
即先使每個子序列有序，再使子序列段間有序。若將兩個有序數(shù)組合并成一個有序數(shù)組，稱為二路歸并。

圖解：

(2)遞歸版本

①實現(xiàn)思路

【1】把待排序數(shù)組從中間分成兩個子數(shù)組，直到無法分割（即每個子數(shù)組只有一個元素)。

【2】對每個子數(shù)組進行歸并排序，即遞歸調(diào)用歸并排序函數(shù)。

【3】合并兩個有序子數(shù)組，得到一個有序的數(shù)組(這里需要輔助數(shù)組來實現(xiàn))，然后把這個有序數(shù)組拷貝到原數(shù)組中。

【4】重復步驟3，直到所有的子數(shù)組合并成一個有序的數(shù)組，排序完成。

②合并

合并兩個有序數(shù)組需要輔助數(shù)組tmp，大致思路就是遍歷兩個區(qū)間，拿出兩個數(shù)組中較小值放在tmp中，合并成有序后再拷貝回原數(shù)組。

圖解：

這里循環(huán)已經(jīng)結(jié)束但我們需要把沒結(jié)束的一方拷貝到tmp中
    //把沒結(jié)束的一方拷貝到tmp中
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
合并的代碼：
//這個時候左右已經(jīng)有序，合并
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = left;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin2] < a[begin1])
		{
			tmp[i++] = a[begin2++];
		}
		else
		{
			tmp[i++] = a[begin1++];
		}
	}

	//把沒結(jié)束的一方拷貝到tmp中
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	//拷貝回去
	//注意這里合并了的有序區(qū)間為[left,right]
	//別的區(qū)間不一定有序，拷貝時要注意
	for (int j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}

③遞歸實現(xiàn)有序

圖解(以左區(qū)間為例)：

④最終代碼

void _MergeSort(int* a, int left,int right,int* tmp)
{
	//只有一個元素(可看成有序)或者區(qū)域不存在，返回
	if (left >= right)
	{
		return;
	}
	int mid = left + (right - left) / 2;
	//先遞歸排序左區(qū)間，后遞歸排序右區(qū)間
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//這個時候左右已經(jīng)有序，合并
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = left;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin2] < a[begin1])
		{
			tmp[i++] = a[begin2++];
		}
		else
		{
			tmp[i++] = a[begin1++];
		}
	}

	//把沒結(jié)束的一方拷貝到tmp中
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	//拷貝回去
	//注意這里合并了的有序區(qū)間為[left,right]
	//別的區(qū)間不一定有序，拷貝時要注意
	for (int j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
}
//歸并排序
void MergeSort(int* a, int n)
{
	//臨時數(shù)組
	int* tmp = (int*)malloc(sizeof(int) * n);
	
	//調(diào)用子函數(shù)進行排序
	_MergeSort(a, 0,n-1,tmp);

	//銷毀
	free(tmp);
	//這里置不置空沒影響
	tmp = NULL;
}

(3)非遞歸版本

①實現(xiàn)思路

【1】首先將待排序數(shù)組中的每一個元素看成是一個大小為1的有序區(qū)間。

【2】然后將相鄰的兩個區(qū)間(保證每次合成的都是相鄰區(qū)間，依靠間距gap來控制)合并成一個更大的有序區(qū)間，這可以通過歸并排序中的合并操作來實現(xiàn)。

【3】重復步驟2，每次將相鄰的兩個有序子數(shù)組合并成更大的有序子數(shù)組，直到得到一個完整的有序數(shù)組。

【4】最終得到的有序數(shù)組就是排序結(jié)果。

②控制分組

關(guān)于間距gap對循環(huán)的控制：

gap=1，范圍為1(gap)的區(qū)間是有序的，合并相鄰兩個區(qū)間，拷貝。

gap=gap*2=2，范圍為2(gap)的區(qū)間是有序的，合并相鄰兩個區(qū)間，拷貝。

gap=gap*2=4，范圍為4(gap)的區(qū)間是有序的，合并相鄰兩個區(qū)間，拷貝。

………………

一直到gap>=n(這個時候數(shù)組前n個數(shù)一定有序，n是數(shù)組元素個數(shù)，結(jié)束循環(huán))

代碼：
    int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + gap * 2 - 1;
			int index = i;

			while (begin1 <= end1 && begin2 <= end2)
			{
				//begin1小，放a[begin1]
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			//排序一組拷貝一組
			for (int j = i; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
圖解：

我們可以看到像前面那樣進行分組是有很大可能越界的，那我們應該怎么做呢？

?

在合并拷貝前加上區(qū)間判斷和修正后，排序不會越界了

③最終代碼

//歸并非遞歸
void MergeSortNonR(int* a, int n)
{
	//臨時數(shù)組
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + gap * 2 - 1;
			int index = i;

			//end1,begin2,end2都有可能越界
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				//begin1小，放a[begin1]
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			//排序一組拷貝一組
			for (int j = i; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}

	//釋放
	free(tmp);
	tmp = NULL;
}

(4)時間，空間復雜度分析

空間復雜度：

開辟了空間大小和原數(shù)組相同的輔助數(shù)組，故空間復雜度為O(N)

時間復雜度：

【1】在歸并排序的每一次合并操作中，需要將兩個有序數(shù)組合并成一個有序數(shù)組，這個過程需要比較兩個有序數(shù)組中所有元素，因此時間復雜度為O(N)。

【2】在歸并排序中，每次將數(shù)組劃分成兩個長度大致相等的子數(shù)組，因此可以得到一個完全二叉樹，其深度大約為logN。每層的合并操作的時間復雜度為O(N)，因此整個算法的時間復雜度為O(N*logN)。

(5)小結(jié)

歸并排序的效率還不錯，但是有O(N)的空間復雜度，更多是應用在解決磁盤中的外排序問題。

另外控制邊界的方法并不止上面一種

除了右區(qū)間不在數(shù)組中(左右都越界)直接跳出(這個時候沒有對tmp進行操作，對應位置為隨機值)

我們也可以把右區(qū)間人為修改為不存在(begin>end)，這種情況下即使不需要合并也會拷貝到tmp中，我們就可以一次大循環(huán)結(jié)束再進行拷貝(拷貝一層)，但是這樣不是很好理解

代碼：
//歸并非遞歸
void MergeSortNonR1(int* a, int n)
{
	//臨時數(shù)組
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2*gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + gap * 2 - 1;
			int index = i;

			//修正，讓左區(qū)間不越界
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			//修正，讓右區(qū)間不存在
			if (begin2 >= n)
			{
				//begin2 > end2，區(qū)間不存在
				begin2 = n ;
				end2 = n - 1;
			}
			//修正，讓右區(qū)間不越界
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				//begin1小，放a[begin1]
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

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

		}
		//一層按組排序完，拷貝
		for (int j = 0; j < n; j++)
		{
			a[j] = tmp[j];
		}
		gap *= 2;
	}
	
	//釋放
	free(tmp);
	tmp = NULL;
}

二：計數(shù)排序

(1)計數(shù)排序的基本思想

對于給定的輸入序列中的每一個元素x，確定出小于x的元素個數(shù)

這樣就可以直接把x放到以小于x的元素個數(shù)為下標的輸出序列的對應位置上。

(這里其實是相對位置的概念，比如數(shù)組中最小值為0，它對應下標0位置，最小值為1000，也是對應下標0位置)

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

【1】遍歷一遍，找出最大值和最小值

【2】依據(jù)最大值和最小值的差值來開辟輔助數(shù)組tmp

【3】計數(shù)，記錄數(shù)組元素出現(xiàn)次數(shù)

【4】遍歷tmp數(shù)組，進行拷貝

(3)圖解加最終代碼

圖解：

排序篇：歸并排序的遞歸，非遞歸以及計數(shù)排序的實現(xiàn)(C語言)

最終代碼：

//計數(shù)排序
void CountSort(int* a, int n)
{
	//找出最大和最小
	int max = a[0];
	int min = a[0];
	int i = 0;
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}

	//開空間加初始化
	int* tmp = (int*)malloc(sizeof(int) * (max - min + 1));
	if (tmp == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}
	//必須初始化為0
	memset(tmp, 0, sizeof(int) * (max - min + 1));

	//計數(shù)
	for (i = 0; i < n; i++)
	{
		tmp[a[i]-min]++;
	}

	//拷貝
	int j = 0;
	for (i = 0; i < max - min + 1; i++)
	{
		while (tmp[i]--)
		{
			a[j++] = i + min;
		}
	}
}

(4)時間，空間復雜度分析

空間復雜度：

開辟了空間大小為range(max-min+1)的輔助數(shù)組，故空間復雜度為O(range)

空間復雜度：

遍歷a找最大和最小為O(N)

遍歷a計數(shù)為O(N)

遍歷range為O(range)

故時間復雜度為O(max(N,range))

(5)小結(jié)

計數(shù)排序是一種非比較的排序，它不需要進行數(shù)據(jù)間的比較。

算法設計上非常巧妙，時間復雜度最快可以達到O(N)，但是有一定的局限性

比如正負數(shù)同時存在或者數(shù)據(jù)大小浮動很大(1,2,3,1000000)的情況，可能導致空間的大量浪費，效率也會有所下降。文章來源地址http://www.zghlxwxcb.cn/news/detail-439704.html

到了這里，關(guān)于排序篇：歸并排序的遞歸，非遞歸以及計數(shù)排序的實現(xiàn)(C語言)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！