一文详解归并排序

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

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

假设现在有一个序列是:

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

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

合并两个有序序列要借助一个辅助数组，假设现在有两个有序的序列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 
#include 
using namespace std;

void merge(vector& nums, int left, int mid, int right, vector& 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& nums, int left, int right, vector& 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& arr)
{
	for (int i = 0; i < arr.size(); i++)
		cout << arr[i] << "\t";
	cout << endl;
}

int main()
{
	vector nums = { 1, 10, 9, 4, 3, 7, 6, 8 };
	vector 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

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