排序二（归并、快排）_归并排序的递归方程

一、归并排序

归并排序的核心思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起。

归并排序使用的是分治思想，即将一个大问题分解成小的子问题来解决。因此，这里我们用递归代码来实现归并排序。

归并排序递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解
1
2
3
4
5

merge_sort(p…r) 表示，给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。

归并代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 100  

void merge_sort(int a[], int n);
void merge_sort_c(int a[], int p, int r);
void merge(int a[], int p, int q, int r);
void print(int* a, int n);

int main()
{
	srand((unsigned)(time(NULL)));  // 添加随机种子
	int a[N];
	for (int i = 0; i < N; ++i)
	{
		a[i] = rand() % 100;
	}
	printf("数组a未进行归并排序前：");
	print(a, N);
	printf("\n数组a进行归并排序后：");
	merge_sort(a, N);
	print(a, N);
	return 0;
}

void merge_sort(int a[], int n)
{
	merge_sort_c(a, 0, n - 1);
}

// 递归排序
void merge_sort_c(int a[], int p, int r)
{
	// 递归终止条件
	if (p >= r) return ;
	// 取p到r之间的中间位置q
	int q = (p + r) / 2;
	// 分治递归
	merge_sort_c(a, p, q);  
	merge_sort_c(a, q + 1, r);
	// 将a[p...q]和a[q + 1...r]合并为a[p...r]
	merge(a, p, q, r);  // merge函数只负责将已经排好序的两个数组组合成一个新的数组
}

void merge(int a[], int p, int q, int r)
{
	int i = p, j = q + 1, k = 0;  // 初始化变量i，j，k
	// 申请一个跟a[p...r]一样大小的临时数组
	int* tmp = (int*)malloc(sizeof(a[0]) * N);
	while (i <= q && j <= r)
	{
		if (a[i] <= a[j])
		{
			// 这里体现了归并排序算法的稳定性
			// 即经过排序后，值相同元素，先后顺序不变
			tmp[k++] = a[i++];
		}
		else
		{
			tmp[k++] = a[j++];
		}
	}

	// 判断哪个子数组中有剩余的数据
	int start = i, end = q;
	if (j <= r)
	{
		start = j; 
		end = r;
	}

	// 将剩余的数组拷贝到临时数组tmp
	while (start <= end)
	{
		tmp[k++] = a[start++];
	}

	// 将tmp中的数组拷贝回a[p...r]
	for (i = 0; i <= r - p; i++)
	{
		a[p + i] = tmp[i];
	}
	free(tmp);
}

void print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

运行结果：

归并排序时间复杂度分析

根据递归求解问题的思想：一个问题a可以分解为多个问题 b 和 c，求解问题 a 就可以分解为求解问题 b 和 c，把 b，c 解决之后，我们再把 b、c 的结果合并成 a 的结果。

我们定义求解问题a的时间为T(a)，求解问题 b、c 的时间为T(b)和T©，于是可以得到如下的递推公式：

                                                T(a) = T(b) + T(c) + K
1

假设归并排序需要的时间为T(n)，分解成两个子数组排序的时间都是T(n/2)，又因为 merge() 函数合并两个有序数组的时间复杂度是 O(n)，所以套用上面的公式，归并排序的时间复杂度计算公式就是：

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1
1
2

进一步分析：

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......
1
2
3
4
5
6
7

通过这样一步一步分解推导，我们可以得到 T(n) = 2^k * T(n/2^k) + k * n。当T(n/2^k) = T(1)时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

T(n/2^k)中 n/2^k 表示分解后的数据规模，2^k 中k表示把数据规模分解到1时的分解次数，故当算法完成，数据规模分解到1，此时n/2^k=1

归并排序的空间复杂度分析

递归代码的空间复杂度并不能像时间复杂度那样增加，尽管每次的合并操作都需要申请额外的内存空间，但是这个临时内存空间最大不会超过n个数据规模的大小，所以空间复杂度是O(n)。

二、快速排序

快速排序的主要思想是：如果要排序数组中 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。根据分治、递归的处理思想，用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，当区间缩小为 1时即排序完成。

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r
1
2
3
4
5

快排代码：

#include<stdio.h>
#include<stdlib.h>

#define N 100

// 此处分区函数的实现使得快速排序占用更少的内存空间
int partition(int* a, int p, int r)
{
	int pivot = a[r];
	int i = p;
	for (int j = p; j < r; ++j)
	{
		if (a[j] < pivot)
		{
			int tmp1 = a[j];
			a[j] = a[i];
			a[i] = tmp1;
			i++;
		}
	}
	int tmp2 = a[r];
	a[r] = a[i];
	a[i] = tmp2;
	return i;
}

// 快速排序递归函数，p，r为下标
void quick_sort_c(int* a, int p, int r)
{
	if (p >= r) return;
	int q = partition(a, p, r);  // 获取分区点
	quick_sort_c(a, p, q - 1);
	quick_sort_c(a, q + 1, r);
}

void quick_sort(int* a, int n)
{
	quick_sort_c(a, 0, n - 1);
}

void print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	srand((unsigned)(time(NULL)));  // 添加随机种子
	int a[N];
	for (int i = 0; i < N; ++i)
	{
		a[i] = rand() % 100;
	}
	printf("数组a未进行快速排序前：");
	print(a, N);
	printf("\n数组a进行快速排序后：");
	quick_sort(a, N);
	print(a, N);
	return 0;
}
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
56
57
58
59
60
61
62
63

运行结果：

由于快速排序过程中有数据的交换，所以快速排序不是一个稳定的排序算法。

快速排序时间复杂度分析

快速排序在大部分情况下时间复杂度都能可以达到O(nlogn)，只有在极端情况下才会退化为O(n^2)

如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。

快速排序空间复杂度分析

由于partition()函数只涉及元素的交换，所以快排的空间复杂度为O(1)。

归并排序与快速排序的对比

• 归并排序和快速排序都用到了分治的思想，递归公式和递归代码也很相似；
• 归并排序的处理过程是由下到上的，先处理子问题，然后再合并，而快排的处理过程则是由上到下的，先分区再处理子问题；
• 归并排序不是原地排序算法，空间复杂度为O(n)，快排是原地排序算法，空间复杂度为O(1)，因此归并排序会比快速排序占用更多的内存。
• 归并排序是稳定的排序算法，可以保证相同值的元素排序过后，其原本的先后顺序不发生变化，但快排不是。