复杂度为O(NlogN)的归并排序

---

---

前言

在前面的一章中，我们了解到了时间复杂度为n²的四种排序方法，但是当我们的数据量非常巨大的时候，这四种排序方法的效率就非常低了。那么为了解决这个问题，今天我所要讲解的就是时间复杂度为nlogn的排序，来帮助大家提高效率。

---

一、分而治之思想

分治算法简而言之，就是将一个大规模的问题不断划分为若干个规模较小、解决方式相同的问题。那么对于每一个子问题而言，由于规模的大幅度减小所以其解决起来就变得很简单，因此只要我们解决了每一个子问题之后，再将所有的子问题合并就可以解决原本的问题了。

二、归并排序

1、排序逻辑：

如果一个规模很大的乱序数组，我们对其进行排序，那么可想而知一般情况下，我们需要排序很多次。但是我们将其规模缩小，那么其排序的次数也会相对减少，那么我们将规模不断减小到1，此时一个数字组成的数组本身就是有序的。假设我们将其分成规模为2的数组，那么也只需要排序一次就可以将这个子序列变成有序的。

因此我们就可以将一个数列不断划分，直至规模为1。然后我们再将子序列不断地排序合并。最终使得整体有序。

2、代码实现（c++）：

//归并部分
void merge(int* arr, int low, int mid, int high)
{
	int* b = new int[high - low + 1];
	int i = low, j = mid + 1, k = 0;
	while (i <= mid && j <= high)
	{
		if (arr[i] <= arr[j])b[k++] = arr[i++];
		else b[k++] = arr[j++];
	}
	while (i <= mid)b[k++] = arr[i++];
	while (j <= high)b[k++] = arr[j++];
	for (i = low, k = 0; i <= high; i++)
		arr[i] = b[k++];
	delete[] b;
}
//分治部分
void mergesort(int* A, int low, int high)
{
	
	if (low < high)
	{
		int mid = (low + high) / 2;
		mergesort(A, low, mid);
		mergesort(A, mid + 1, high);
		merge(A, low, mid, high);
	}
}
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

3、代码分析

合并函数分析：

归并排序分成两部分，我们先来看归并部分，即将两个有序的数列，合并成一个有序的数列。
我们假设排序的规则是升序排序，那么两个有序数列的最左侧的数字都是每个数组中最小的数字，所以我们比较两个最左端的数字便能够找出两个数组中最小的数字，然后我们将这个数字放到临时数组的最左侧。
接着，我们将含有最小数字的子列中，指向最左端的指针向右偏移，那么再将这个数字和另一个子列中最左端的数字比较，接着我们就能找到第二小的数字，然后将第二小的数字放到临时数组中的左端的第二个位置，即两个子列中第二小的数字，后面重复上述操作。
直到某个子列中的数字全部放置到临时数组中，此时退出上述的操作，然后将另一个子列中的剩余数组按顺序放置到临时数组中即可。

分解函数分析：

这一部分先于合并函数，而这一部分也恰好是我们分治思想的体现。具体的实现逻辑如下：