排
排序

归并排序

排序算法

归并排序以O(NlogN)最坏情形运行时间运行，而所使用的比较次数几乎是最优的。它是递归算法一个很好的实例。这个算法中基本的操作是合并两个已排序的表。因为这两个表是已排序的，所以若将输出放到第三个表中时则该算法可以通过对输入数据一趟排序来完成。

归并排序代码

归并排序分为三个函数，分别是：mSort函数、merge函数、mergeSort函数。其中merge函数是将不断输入的数据排序并归并。mSort函数是利用递归的想法分而治之，分治是递归非常有力的用法。mergeSort函数是起到调用前面两个函数与分配临时空间的作用。

mSort函数

1
2
3
4
5
6
7
8
9
10
11
12
void mSort( int nums[], int tmpNums[], int left, int right )
{
	int center;
	if ( left < right )
	{
		center = (left + right) / 2;
		mSort(nums, tmpNums, left, center);
		mSort(nums, tmpNums, center + 1 , right);
		merge(nums, tmpNums, left, center + 1, right);
	}
}

merge函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void merge(int nums[], int tmpNums[], int lPos, int rPos, int rightEnd)
{
	int i, leftEnd, numsElement, tmpPos;
	leftEnd = rPos - 1;
	tmpPos = lPos;
	numsElement = rightEnd - lPos + 1;
	while (lPos <= leftEnd && rPos <= rightEnd)
	{
		if (nums[lPos] <= nums[rPos])
		{
			tmpNums[tmpPos++] = nums[lPos++];
		}
		else
		{
			tmpNums[tmpPos++] = nums[rPos++];
		}
	}
	while (lPos <= leftEnd)
	{
		tmpNums[tmpPos++] = nums[lPos++];
	}
	while (rPos <= rightEnd)
	{
		tmpNums[tmpPos++] = nums[rPos++];
	}
	for (i = 0; i < numsElement; i++, rightEnd--)
	{
		nums[rightEnd] = tmpNums[rightEnd];
	}
}

mergeSort函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void mergeSort(int nums[], int N)
{
	int *tmpNums;
	tmpNums = malloc(N * sizeof(int));
	if (tmpNums != NULL)
	{
		mSort(nums, tmpNums, 0, N - 1);
		free(tmpNums);
	}
	else
	{
		printf("No space for tmp array");
	}
}

main函数

1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
int main(int argc, char *argv[])
{
	int nums[10] = { 5, 3, 4, 1, 6, 10, 12, 2, 23, 9 };
	mergeSort(nums, 10);
	int i;
	for (i = 0; i<10; i++)
	{
		printf("%d\n", nums[i]);
	}
}

归并排序的分析

假设N是2的幂，从而我们总可以将它分裂成均为偶数的两部分。对于N-1，归并排序时间是常数，我们将记为1.否则，对N个数归并并排序的用时等于完成两个大小为N/2的递归排序所用的时间再加上合并的时间， 它是线性的。下面方程给出准确的表示：
$$ T(1) = 1 $$
$$ T(N) = 2T(\frac N2) + N $$
将上式两边同时除以N有：
$$ \frac{T(N)}{N} = {T(\frac N2)\over(\frac N2)} + 1 $$
该方程对2的幂的任意的N是成立的，我们还可以写成：
$$ {T(\frac N2)\over(\frac N2)} = {T(\frac N4)\over(\frac N4)} +1 $$
$$ .
.
.$$
$$ {T(2)\over2} = {T(1)\over1} + 1 $$
将上式相加，并约掉可以得到：
$$ {T(N)\over N} = {T(1)\over1} + logN $$
两边同时乘以N得到：
$$ T(N) = N + NlogN = O(NlogN) $$

分享到 评论