归并排序

发表于

思路

我们这里介绍的是二路归并算法，它的核心是将一维数组中前后的两个有序的序列合并成一个有序序列的过程。归并排序只需要做两将事情：

  1. “分解”——将序列每次折半划分
  2. “合并”——将划分后的序列段两两合并成有序序列。

图示（参考链接）

image

代码实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>

void Merge(int * a, int temp[], int low, int mid, int high)
{
	int low_s = low;
	int low_e = mid;
	int high_s = mid + 1;
	int high_e = high;
	int k = 0;
	while (low_s <= low_e && high_s <= high_e)    //通过归并进行排序，这个思路很重要
	{
		if (a[low_s] < a[high_s])
		{
			temp[k++] = a[low_s++];
		}
		else
		{
			temp[k++] = a[high_s++];
		}
	}

	while (low_s <= low_e)   temp[k++] = a[low_s++];
	while (high_s <= high_e) temp[k++] = a[high_s++];

	for (int i = 0; i < k; i++)
	{
		a[low + i] = temp[i];
	}
}

void Msort(int * a, int temp[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;      //中间下标
		Msort(a, temp, low, mid);        //对左边进行递归分割
		Msort(a, temp, mid + 1, high);   //对右边进行递归分割
		Merge(a, temp, low, mid, high);  //合并前面两个有序的序列
	}
}

int main()
{
	int temp[6];
	int a[] = { 14, 12, 15, 13, 11, 16 };
	Msort(a, temp, 0, 5);
	for (int i = 0; i < 6; i++)
	{
		printf("%d,", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

算法分析

设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，堆排序）也是效率比较高的。但是平均来说还是快速排序比较好。