【初阶算法4】——归并排序的详解，及其归并排序的扩展

目录

前言

学习目标：

学习内容：

一、介绍归并排序

1.1 归并排序的思路

1.2 归并排序的代码

1.2.1 mergesort函数部分 

1.2.2 process函数部分 

1.2.3 merge函数部分 

二、AC两道经典的OJ题目

题目一：逆序对问题

题目二：小和问题 

三、练习一道LeetCode的题目

四、总结在什么情况下使用归并排序的算法

学习产出：

---

前言

💓作者简介： 加油，旭杏，目前大二，正在学习C++，数据结构等👀
💓作者主页：加油，旭杏的主页👀

⏩本文收录在：再识C进阶的专栏👀

🚚代码仓库：旭日东升 1👀

🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦！💖💖

学习目标：

       在这一篇博客中，我们要学习排序算法中比较重要的三个排序中的其中一个，就是归并排序，并学会使用代码进行编写归并排序，之后能够AC两道经典的OJ题目，最后是刷几道LeetCode的题目，这就是本博客的学习目标！

---

学习内容：

通过上面的学习目标，我们可以列出要学习的内容：

1. 学习归并排序的思想
2. 使用代码进行编写归并排序
3. AC两道经典的OJ题目
4. 练习几道LeetCode的题目
5. 总结在什么情况下使用归并排序的算法

---

一、介绍归并排序

       在之前的学习中，我们可能或多或少的接触过排序算法，也知道一些排序算法：冒泡排序、选择排序、插入排序等。不过这些排序有共同点——时间复杂度为O(N * N)，时间上不是那么有效，我们需要进行进一步的优化，从而就有了我们这一篇博客讲述的归并排序，其时间复杂度为：O(N * logN)，空间复杂度为：O(N)。

1.1 归并排序的思路

       归并排序，顾名思义，“归并”的含义是将两个或两个以上的有序表合并为一个新的有序表。假设待排序数表有N个记录，则可将其视为N个有序的子表，每一个子表的长度是1，然后两两归并，得到[ N / 2 ]个长度为2或1的有序表；继续两两归并……如此重复，直到合并成一个长度为N有序表为止。下面小编将画图带大家理解：

       而这个排序刚开始有点像这个相反的做法，其思路是：先将这一大长串数组分割，因为其是一个递归的过程，就是将数组一直分割，直到每一个数组长度为1，此时每一个数组都是有序的；之后要开始合并数组，合并数组时将进行比较，看需要来判断是升序或降序，合并的时候就如同上方的合并一样，最后能够得出一个有序的数组。

1.2 归并排序的代码

这个算法有三个部分组成，请看下面我一一为大家进行讲解：

1.2.1 mergesort函数部分 

void mergesort(int arr[], int left, int right)
{
    int sz = right - left + 1; //计算数组的长度
    if(arr == NULL || sz < 2)  //如果数组的首元素不存在，则不用排序；
        return ;               //如果数组的长度只有一个，则也不用排序
    process(arr, left, right); //进入process函数部分
}

1.2.2 process函数部分 

void process(int arr[], int left, int right)
{
    int sz = right - left + 1;   //与mergesort函数的部分作用是一样的
    if(arr == NULL || sz < 2)
        return ;
//分割数组
    int mid = left + ((right - left) >> 1);  //计算出这段数组中正中心的位置坐标
    process(arr, left, mid);     //递归过程中，将数组分为左右部分，这是左部分
    process(arr, mid + 1, right);//这是右部分
    merge(arr, left, mid, right);
}

1.2.3 merge函数部分 

void merge(int arr[], int left, int mid, int right)
{
    int sz = right - left + 1;
    int* help = (int*)malloc(sizeof(int) * sz); //构造辅助数组
    int i = 0;
    int p1 = left;  //建立指针
    int p2 = mid + 1;
    while(p1 <= mid && p2 <= right) //如果左指针与右指针都不越界，则进入循环
    {
        help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++]; //进行比较，交换数据
    }
    while(p1 <= mid) //将左边剩余的数据拷贝到辅助数组中
    {
        help[i++] = arr[p1++];
    }
    while(p2 <= right) //将右边剩余的数据拷贝到辅助数组中
    {
        help[i++] = arr[p2++];
    }
    for(int i = 0; i < sz; i++) //最后将辅助数组中的数据转移到原数组中
    {
        arr[left + i] = help[i];
    }
}

二、AC两道经典的OJ题目

题目一：逆序对问题

题目：

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

思路：

       在这道题中，我们要注意题目中标红的描述，这个逆序对永远都是前一个数字的坐标位置永远小于后一个数字的坐标位置。这一点就和归并排序不谋而合，归并排序算法总是将左边的数字与右边的数字进行比较，然后进行排序。而这道题要求的是逆序对的个数，我们可以在进行比较的时候进行计数，这就是大致思路。

       将这个数组进行降序排序还是逆序排序呢？如果是降序排序时，我们将左边有右边进行比较，如果左边大于右边，则大于右边所有的数字，进行计数即可；如果是升序排序可能会出现漏项的情况，自然排除升序，采用降序。

代码：

int merge(int arr[], int left, int mid, int right)
{
    int sz = right - left + 1;
    int* help = (int*)malloc(sizeof(int) * sz);
    int p1 = left;
    int p2 = mid + 1;
    int i = 0;
    int ret = 0;
    while(p1 <= mid && p2 <= right)
    {
        ret += arr[p1]>arr[p2]?(right - p2 + 1):0; //如果左边的数字大于右边的数字，则计算右边
//一共有多少数字
        help[i++] = arr[p1] > arr[p2]?arr[p1++]:arr[p2++];
    }
    while(p1 <= mid)
    {
        help[i++] = arr[p1++];
    }
    while(p2 <= right)
    {
        help[i++] = arr[p2++];
    }
    for(int i = 0; i < sz; i++)
    {
        arr[left + i] = help[i];
    }
    return ret;
}
 
int process(int arr[], int left, int right)
{
    int sz = right - left + 1;
    if(arr == NULL || sz < 2)
        return 0;
    int mid = left + ((right - left) >> 1);
    return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
}
 
int revOrder(int arr[], int left, int right)
{
    int sz = right - left + 1;
    if(arr == NULL || sz < 2)
        return 0;
    return process(arr, left, right);
}
 
int reversePairs(int* nums, int numsSize){
    int left = 0;
    int right = numsSize - 1;
    int ans = revOrder(nums, left, right);
    return ans;
}

题目二：小和问题 

题目：

       在一个数组中，每一个数左边比当前的数小进行累加起来，叫做这个数组的小和，求一个数组的小和。

思路：

       同理，看题目中被标红的描述，进行降序排序，如果左边的数字小于右边的数字，则将左边的数字乘右边有多少个大于他的个数，进行累加即可。

代码：

int merge(int arr[], int left, int mid, int right)
{
	int sz = right - left + 1;
	int* help = (int*)malloc(sizeof(int) * sz);
	int i = 0;
	int p1 = left;
	int p2 = mid + 1;
	int count = 0;
	while (p1 <= mid && p2 <= right)
	{
		count += arr[p1] < arr[p2] ? (right - p2 + 1)*arr[p1] : 0;
		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= mid)
	{
		help[i++] = arr[p1++];
	}
	while (p2 <= right)
	{
		help[i++] = arr[p2++];
	}
	for (int i = 0; i < sz; i++)
	{
		arr[left + i] = help[i];
	}
	return count;
}
 
int process(int arr[], int left, int right)
{
	int sz = right - left + 1;
	if (arr == NULL || sz < 2)
		return 0;
	int mid = left + ((right - left) >> 1);
	return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
}
int reverseOrder(int arr[], int left, int right)
{
	int sz = right - left + 1;
	if (arr == NULL || sz < 2)
		return 0;
	return process(arr, left, right);
}
 
int main()
{
	int arr[] = { 1,3,4,2,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;
	int ans = reverseOrder(arr, left, right);
	printf("%d\n", ans);
	return 0;
}

三、练习一道LeetCode的题目

题目：

       给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。

思路：

       前面的操作基本一样，只需将merge函数部分进行修改即可，将左边的指针不动，一一右边的数字进行比较，如果条件成立，就将指针向右移动一位，如果不成立跳出，结果加上右指针减去初始位置的个数。

代码：

int process(int arr[], int left, int right)
{
    int sz = right - left + 1;
    if(arr == NULL || sz < 2)
        return 0;
    int mid = left + ((right - left) >> 1);
    int n1 = process(arr, left, mid);
    int n2 = process(arr, mid + 1, right);
    int ret = n1 + n2;
    int p1 = left;
    int p2 = mid + 1;
    int i = 0;
    while(p1 <= mid)
    {
        while(p2 <= right && (long long)arr[p1]>2*(long long)arr[p2])
        p2++;
        ret += (p2 - mid - 1);
        p1++;
    }
    p1 = left;
    p2 = mid + 1;
    int* help = (int*)malloc(sizeof(int) * sz);
    while(p1 <= mid && p2 <= right)
    {
        help[i++] = arr[p1]
    }
    while(p1 <= mid)
    {
        help[i++] = arr[p1++];
    }
    while(p2 <= right)
    {
        help[i++] = arr[p2++];
    }
    for(int i = 0; i < sz; ++i)
    {
        arr[left + i] = help[i];
    }
    return ret;
}
 
int mergeSort(int arr[], int left, int right)
{
    int sz = right - left + 1;
    if(arr == NULL || sz < 2)
        return 0;
    return process(arr, left, right);
}
 
int reversePairs(int* nums, int numsSize){
    int left = 0;
    int right = numsSize - 1;
    return mergeSort(nums, left, right);
}

四、总结在什么情况下使用归并排序的算法

       小编觉得在数组对问题可能使用归并排序，尤其是一个数组对中满足一定条件，左边的左边小于右边的坐标时，可以考虑考虑归并排序算法的思想。

---

学习产出：

1. 学习归并排序的思想
2. 使用代码进行编写归并排序
3. AC两道经典的OJ题目
4. 练习几道LeetCode的题目
5. 总结在什么情况下使用归并排序的算法