归并排序与其例题

一、归并排序的简述

归并排序（Merge Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略。它的基本思想是将一个大的问题分解成多个小问题，然后解决这些小问题，最后将结果合并起来得到最终的答案。具体来说，归并排序的算法思想可以分为以下几个步骤：

1. 分解（Divide）

将待排序的数组或列表分成两个大小相等或接近相等的子数组。这个过程会递归地进行，直到子数组的大小为1或0（即子数组已经排序好）。

2. 解决（Conquer）

当子数组的大小为1或0时，这些子数组自然是已排序的。接下来，逐步合并这些子数组，以形成较大的排序数组。

3. 合并（Merge）

将两个已排序的子数组合并成一个新的已排序的数组。这个合并操作是归并排序的关键部分，它可以通过比较两个子数组的元素并将较小的元素添加到结果数组中来完成。

详细的归并排序算法步骤：

分解：
- 如果数组的长度大于1，找到数组的中间位置，将数组分成两半。
递归排序：
- 对每个子数组递归地调用归并排序算法，直到子数组的长度为1。
合并：
- 将两个已排序的子数组合并成一个排序后的数组。可以使用两个指针分别指向两个子数组的当前元素，比较这两个元素，将较小的元素添加到结果数组中，并移动指针。

示例

假设我们要对数组 [38, 27, 43, 3, 9, 82, 10] 进行归并排序：

分解：
- [38, 27, 43, 3, 9, 82, 10] 被分成 [38, 27, 43] 和 [3, 9, 82, 10]。
- [38, 27, 43] 进一步分解为 [38] 和 [27, 43]。
- [27, 43] 进一步分解为 [27] 和 [43]。
- [3, 9, 82, 10] 被分解为 [3, 9] 和 [82, 10]。
- [3, 9] 进一步分解为 [3] 和 [9]。
- [82, 10] 进一步分解为 [82] 和 [10]。
递归排序：
- 单个元素 [38], [27], [43], [3], [9], [82], [10] 都是已排序的。
合并：
- 合并 [27] 和 [43] 变成 [27, 43]。
- 合并 [38] 和 [27, 43] 变成 [27, 38, 43]。
- 合并 [3] 和 [9] 变成 [3, 9]。
- 合并 [82] 和 [10] 变成 [10, 82]。
- 合并 [3, 9] 和 [10, 82] 变成 [3, 9, 10, 82]。
- 最后合并 [27, 38, 43] 和 [3, 9, 10, 82] 变成 [3, 9, 10, 27, 38, 43, 82]。

时间复杂度

归并排序的时间复杂度为 (O(n \log n))，其中 (n) 是待排序元素的数量。这个复杂度是因为分解和合并操作都在对数级别的层次上进行，每一层需要对整个数组进行操作。

空间复杂度

归并排序的空间复杂度为 (O(n))，因为需要额外的空间来存储合并后的数组。

归并排序是一种稳定的排序算法，不会改变相同元素的相对顺序。这使得它在某些需要稳定排序的场景中非常有用。

二、模板题

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼ $10^{9}$ 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

#include<iostream>using namespace std;const int N=1e5+10;
int q[N],tmp[N];void merge_sort(int q[],int l,int r){if(l>=r)  return; //当只有一个元素时，没必要递归，直接返回退出。int mid=l+r>>1,i=l,j=mid+1,k=0;//先找中点。merge_sort(q,l,mid); merge_sort(q,mid+1,r);/*找到中点后将整个要排序的序列分成了两半，然后左边右边归并排序使得左右两边的序列变成有序的，所以这里递归一下。*//*当分成的左右两个序列恰好是长度相等的时候，就执行下面while里面的操作。*/while(i<=mid&&j<=r){if(q[i]<=q[j])  tmp[k++]=q[i++];/*在左右两个序列中找更小的值，然后把这个更小的值放入已经准备好的临时数组tmp[N]。tmp[k++]=q[i++];   这句话其实等价于tmp[k]=q[i]; k++,i++;  这样只写一句话是为了代码更简洁。*/else tmp[k++]=q[j++];}/*当分成的左边的序列大于右边的序列时，直接将左边序列剩余的部分接在tmp数组后面就是。因为本来左右两边的序列就已经是有序的了，所以左边序列剩下来的数都是要大于整体的数，因为比他们小的数已经放进去tmp临时数组了，这一点要注意。*/while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(int i=l,j=0;i<=r;i++,j++)  q[i]=tmp[j];/*这是将tmp数组里面的值复制给原本的q[N]，因为tmp本就是设立的临时数组，最后输出的话还得是q[N]这个实体的。*/
}int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&q[i]); merge_sort(q,0,n-1);for(int i=0;i<n;i++) printf("%d ",q[i]);return 0;
}

归并排序是一种经典的排序算法，其基本思想是分治法。它的主要步骤是将一个大问题分解成若干个小问题，对每个小问题进行解决，然后将结果合并成一个整体。下面是代码的逐行详细解释：

#include<iostream> using namespace std; const int N=1e5+10; int q[N],tmp[N];

#include<iostream>: 包含输入输出流库，用于输入和输出操作。
using namespace std;: 使用 std 命名空间中的所有符号，避免写 std:: 前缀。
const int N=1e5+10;: 定义常量 N，表示数组 q 和 tmp 的最大大小。1e5+10 即 100010。
int q[N], tmp[N];: 声明两个整型数组 q 和 tmp，分别用于存储待排序的数组和临时数组。

void merge_sort(int q[], int l, int r){ if(l >= r) return; //当只有一个元素时，没必要递归，直接返回退出。

void merge_sort(int q[], int l, int r): 定义一个名为 merge_sort 的函数，接收待排序数组 q、左边界 l 和右边界 r 作为参数。
if(l >= r) return;: 当子数组的左边界 l 不小于右边界 r 时，说明子数组只有一个或零个元素，此时已经不需要进一步分割，直接返回。

int mid = l + r >> 1, i = l, j = mid + 1, k = 0; // 先找中点。 merge_sort(q, l, mid); merge_sort(q, mid + 1, r);

int mid = l + r >> 1;: 计算中点，l + r >> 1 是 (l + r) / 2 的位运算实现。
int i = l, j = mid + 1, k = 0;: 初始化指针 i、j 和 k。i 指向左子数组的起始位置，j 指向右子数组的起始位置，k 用于标记临时数组 tmp 的位置。
merge_sort(q, l, mid); merge_sort(q, mid + 1, r);: 对左半部分 [l, mid] 和右半部分 [mid + 1, r] 递归调用 merge_sort 函数，分别排序这两部分。

while(i <= mid && j <= r){ if(q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; }

while(i <= mid && j <= r): 当左子数组和右子数组都有剩余元素时，比较两者的当前元素。
if(q[i] <= q[j]) tmp[k++] = q[i++];: 如果左子数组的当前元素 q[i] 小于或等于右子数组的当前元素 q[j]，将 q[i] 复制到 tmp[k]，然后移动指针 i 和 k。
else tmp[k++] = q[j++];: 如果右子数组的当前元素 q[j] 小于左子数组的当前元素 q[i]，将 q[j] 复制到 tmp[k]，然后移动指针 j 和 k。

while(i <= mid) tmp[k++] = q[i++]; while(j <= r) tmp[k++] = q[j++];

while(i <= mid) tmp[k++] = q[i++];: 当左子数组有剩余元素时，将这些元素复制到 tmp 中。
while(j <= r) tmp[k++] = q[j++];: 当右子数组有剩余元素时，将这些元素复制到 tmp 中。

for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];

for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];: 将临时数组 tmp 中的排序结果复制回原数组 q。i 遍历原数组的范围 [l, r]，j 遍历临时数组 tmp 的范围。

int main(){ int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); merge_sort(q, 0, n - 1); for(int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }

int main(): 主函数的开始。
int n;: 定义整型变量 n，用于存储数组的大小。
scanf("%d", &n);: 从标准输入读取数组的大小 n。
for(int i = 0; i < n; i++) scanf("%d", &q[i]);: 从标准输入读取 n 个整数并存入数组 q。
merge_sort(q, 0, n - 1);: 调用 merge_sort 函数对数组 q 进行排序。
for(int i = 0; i < n; i++) printf("%d ", q[i]);: 打印排序后的数组。
return 0;: 主函数返回 0，表示程序正常结束。

总结

归并排序的基本流程是递归地将数组分成两半，分别对这两半进行排序，然后将它们合并成一个有序数组。该代码实现了归并排序的这一过程，通过分割、排序和合并三个主要步骤来完成数组的排序。

那上面的代码就是归并排序的模板，和快速排序一样要理解与记忆，当涉及到归并排序时，就可以用这个模板。

三、实战例题

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000，
数列中的元素的取值范围 [1, $10^{9}$ ]。

输入样例：

6
2 3 4 5 6 1

输出样例：

#include<iostream>using namespace std;
typedef long long LL;//这里是将long long类型定义为其他名字，其实质还是一样的，就相当于自己取了一个别名。
const int N=1e5+10;
int q[N],tmp[N];/*如果只用int的话是装不下的，因为int的取值范围最大是2的31次方，这个题超过了这个范围，所以用long long类型定义为其他名字*/
LL merge_sort(int q[],int l,int r){if(l>=r) return 0;/*这里不仅仅是简单的退出，因为要统计逆序对的数量，所以当只有一个元素的时候直接返回0就行了，表示没有逆序对。*/int mid=l+r>>1,i=l,j=mid+1,k=0;LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);/*这个res表示两种情况的逆序对数量，都在左边的和都在右边的。为什么归并排序的结果会是逆序对的数量呢，这是因为在归并排序中虽然是比较谁更小，然后放入结果数组，但是你比较得出谁更小的同时也得到了这两个数谁更大，所以相当于一石二鸟，既能找到小的那个放入结果数组，也知道了谁更大，从而逆序对的数量也就知道了。*/while(i<=mid&&j<=r){if(q[i]<=q[j]) tmp[k++]=q[i++];else{tmp[k++]=q[j++];res+=mid-i+1;/*这是逆序对数量存在的第三种情况就是上面图里面黄色部分的地方。当已经确定i<r且q[i]>q[j]的时候，i指针后面的值是一定会比j指针所指的值大的，因为左右子数组都是已经有序了的，相当于说i指向的后面的值只会比i更大，本身i现在所指的值就已经大于j所指的值，那i后面的肯定也是大于的，也就是说i指针后面所有的值都可以与j所指的值形成逆序对，所以算出i指针及其后面值的个数就是逆序对的数量，也就是直到左子数组的边界。最后才得到这个mid-i+1。*/}}while(i<=mid) tmp[k++]=q[i++];while(j<=r)  tmp[k++]=q[j++];//这些都是归并排序的正常模板，直接写就行。for(int i=l,j=0;i<=r;i++,j++)  q[i]=tmp[j];return res;//注意返回结果res，因为最后要的是逆序对的数量而不是输出一个序列，所以要返回一下。
}int main(){int n;cin>>n;for(int i=0;i<n;i++)  scanf("%d",&q[i]);cout<<merge_sort(q,0,n-1)<<endl;return 0;
}

补充说明：

1. 逆序对的定义

在一个数组中，逆序对是指数组中前面的元素大于后面的元素。给定数组 arr，逆序对的定义是 (i, j)，其中 i < j 且 arr[i] > arr[j]。

2. 归并排序简介

归并排序是一种分治算法，步骤如下：

分解：将数组分成两个子数组。
解决：递归地对这两个子数组进行归并排序。
合并：将两个已排序的子数组合并成一个有序数组。

3. 计算逆序对的思路

在归并排序的“合并”步骤中，我们可以同时统计逆序对的数量。具体步骤如下：

分解：递归地对数组进行分解，直到每个子数组只有一个元素（自然是已排序的）。
合并：在合并过程中统计逆序对。假设我们有两个已排序的子数组 left 和 right，我们可以用两个指针分别遍历这两个子数组：
- 如果 left[i] <= right[j]，则 left[i] 和 right[j] 不形成逆序对，移动 left 的指针。
- 如果 left[i] > right[j]，则 left[i] 与 right 子数组中的所有元素都形成逆序对。这个原因是 right 子数组中的元素已经排序，并且比 left[i] 小，所以 right 中的所有元素都和 left[i] 形成逆序对。然后移动 right 的指针。
统计逆序对：在合并的过程中，累加每次发现的逆序对的数量，最终得到整个数组的逆序对数量。

4. 合并过程中逆序对的统计示例

假设我们有两个已排序的子数组 left = [1, 3, 5] 和 right = [2, 4, 6]，我们在合并时可以这样统计逆序对：

left[0] 和 right[0] 比较：1 <= 2，不形成逆序对。
left[1] 和 right[0] 比较：3 > 2，形成逆序对。此时 right 中的所有元素都比 left[1] 小，所以 left[1] 与 right 中的所有元素形成逆序对。
类似地，继续比较，统计所有可能的逆序对。