归并排序是一种高级的排序算法，该算法采用经典的分治法的思想，"分"就是先将原序列拆分为一些小的有序序列，而"治"的结点就是将这些小的序列合并得到新的有序序列。

下面以一个例子为例讲解归并排序的过程。

假设现在有一个序列是:

该序列归并排序的过程如下:

上面归并排序的过程很简单，最关键的部分是合并的过程。

合并两个有序序列要借助一个辅助数组，假设现在有两个有序的序列A = [4, 5, 7, 8]和B = [1, 2, 3, 6]，要将其合并为一个有序的序列，合并过程如下:

合并时需创建3个临时变量i、j、k:

i指向A中待合并的元素j指向B中待合并的元素k指向temp数组中用来存放合并元素的位置

合并过程如下图所示:

上面就是整个归并排序的过程了。下面要说一下时间复杂度和空间复杂度了:

时间复杂度: O(nlogn)空间复杂度: O(n)

完整的代码如下:

#include <iostream>#include <vector>using namespace std;void merge(vector<int>& nums, int left, int mid, int right, vector<int>& temp){	int i = left, j = mid + 1, k = left;	while (i <= mid && j <= right)	{		temp[k++] = (nums[i] <= nums[j] ? nums[i++] : nums[j++]);	}	while (i <= mid)		temp[k++] = nums[i++];	while (j <= right)		temp[k++] = nums[j++];	// 将temp拷贝到原数组中	for (i = left; i <= right; i++)		nums[i] = temp[i];}void mergeSort(vector<int>& nums, int left, int right, vector<int>& temp){	if (left < right)	{		int mid = (left + right) / 2;		// 对左半序列进行归并排序		mergeSort(nums, left, mid, temp);		// 对右半序列进行归并排序		mergeSort(nums, mid + 1, right, temp);		// 将左半序列和右半序列合并为一个完整的有序序列		merge(nums, left, mid, right, temp);	}}void printVector(vector<int>& arr){	for (int i = 0; i < arr.size(); i++)		cout << arr[i] << "\t";	cout << endl;}int main(){	vector<int> nums = { 1, 10, 9, 4, 3, 7, 6, 8 };	vector<int> temp(nums.begin(), nums.end());	cout << "排序前: " << endl;	printVector(nums);	mergeSort(nums, 0, nums.size() - 1, temp);	cout << "排序后: " << endl;	printVector(nums);	return 0;}

运行结果:

---------------------------------------------------------------------------------------------------------------------------------------

下面有一道以归并排序为背景的算法题，使用暴力解法也是可以解的，但是时间会超时的哦。有兴趣的可以做一下，下一篇文章中给出完整的解答。

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

测试用例: [7, 5, 6, 4]

输出结果: 5

今天的内容就到这儿了。如果对我的推、文有兴趣，欢迎转、载分、享。也可以推荐给朋友关、注哦。只推干货，宁缺毋滥。