目录
算法思想
归并排序———分治（合二为一）
例
1.确定分界点（mid=(l+r)/2)
2.递归排序左边和右边
3.归并将左边和右边合二为一
例题
题目：acwing.787. 归并排序
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
原题链接 ：AcWing 787. 归并排序
#include<iostream> using namespace std; const int N = 1e6 + 10;//数据范围1≤n≤100000 int n; int q[N], tmp[N];//tmp临时数组 void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = l + r >> 1;//确定分界点（mid=(l+r)/2) merge_sort(q, l, mid);//递归排序左边 merge_sort(q, mid + 1, r);//递归排序右边 /*归并*/ int k = 0, i = l, j = mid + 1;//i指向左边的起点，j指向右边的起点 while (i <= mid && j <= r) if (q[i] <= q[j]) //左右比大小，小的存在临时数组中 tmp[k++] = q[i++]; else tmp[k++] = q[j++]; while(i<=mid) tmp[k++] = q[i++]; while(j<=r) tmp[k++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++)//将临时数组赋回有序数组 q[i] = tmp[j]; } int main() { scanf("%d", &n);//输入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; }
题目：acwing.787.逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量逆序对的定义如下: 对于数列的第i个和第 j个元素，如果满足i< i且a [i]>a[j]，则其为一个逆序对;否则不是。
输入格式
第一行包含整数n，表示数列的长度
第二行包含n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1 < n < 100000
数列中的元素的取值范围[1,10^9]
输入样例：
6 2 3 4 5 6 1
输出样例：
5
原题链接 ：AcWing 788. 逆序对的数量
#include <iostream> using namespace std; typedef long long LL; const int N = 1e6+10;//1 < n < 100000 int a[N], tmp[N]; LL merge_sort(int q[], int l, int r) { if (l >= r) return 0; int mid = (l + r) >> 1; // 确定分界点 LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); /*归并*/ int k = 0,i = l, j = mid + 1 ; while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else { res += mid - i + 1; tmp[k++] = q[j++]; } } 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; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); LL res = merge_sort(a, 0, n - 1); cout << res << endl; return 0; }
好了，本篇学习笔记就到此为止了，如有问题欢迎指正，感谢各位佬的支持!
