有参加蓝桥杯的同学可以给博主点个关注，博主也在准备蓝桥杯，可以跟着博主的博客一起刷题。

蓝桥杯

我的AcWing

题目及图片来自蓝桥杯C++ AB组辅导课

归并排序

归并排序——分治

① 确定分界点：mid = (l + r) / 2

② 递归排序 left，right

③ 归并——合二为一

归并中最麻烦的就是最后一步：合二为一，我们可以利用双指针，假设我们有两个有序的序列，然后用res[]数组记录答案，两个指针分别指向序列的头部，也就是两个序列分别的最小值min，此时比较这两个指针指向值的大小，此时这两个指针较小值就是两个序列中的最小值，假设第一个序列的是两个序列的最小值，我们将这个值存入res[]中，第一个序列指针往后挪一位。

挪完之后我们发现，第一个指针还是第一个序列中最小的值，那么我们再跟第二个序列的指针比较，再把较小值存入数组中。

以此类推，两个指针依次往后走进行比较，直到其中有一个指针走到终点，循环此时可以退出，假设第二个指针走了一半，把第二个序列后半段的值直接补到数组即可。

归并排序算法是稳定的，当两个指针指向的值相同时，我们优先将第一个序列的值存入数组中。

例题

AcWing 787. 归并排序

模板题

import java.util.Scanner;public class Main { static final int N = 100010;    static int[] q = new int[N];    static int[] tmp = new int[N]; // 辅助存值的数组 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) q[i] = sc.nextInt();  merge_sort(q, 0, n - 1);  for (int i = 0; i < n; i++) System.out.print(q[i] + " ");    } private static void merge_sort(int q[], int l, int r) { if (l >= r) return;  int mid = (l + r) / 2; // 确定分界点  merge_sort(q, l, mid); // 递归对左区间和右区间排序 merge_sort(q, mid + 1, r);  int k = 0; // k表示当前已经合并了几个数 int i = l, j = mid + 1;  // 初始化两个序列的指针 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++]; // 如果i还没走完 将左区间剩余的直接存入数组 while (j <= r) tmp[k++] = q[j++]; // 如果j还没走完 将右区间剩余的直接存入数组  for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];    }}

AcWing 788. 逆序对的数量

序列中任意两个数，前面的数比后面的数大，那么这两个数就是逆序对。

基于分治的思想，将所有的逆序对分成三大类：

① 两个数同时出现在左半边

② 两个数同时出现在右半边

③ 一个数在左半边 一个数在右半边

假定我们归并排序的函数可以将整个区间排好序的同时，求出来整个区间内部所有逆序对的个数

我们发现再求黄色逆序对数量时，我们可以利用归并排序来求，还是双指针，当第二个序列指针比第一个序列小时，q[i] > q[j]，我们可以发现从i开始这个区间的所有数都比q[j]大，此时s[j] = mid - i + 1

因此求我们黄色逆序对的数量，每一次当我们要把q[j]输出来的时候，就在答案里加上mid - i + 1就可以了。

import java.util.Scanner;public class Main {    static final int N = 100010;    static int[] q = new int[N];    static int[] tmp = new int[N];    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) q[i] = sc.nextInt(); System.out.println(merge_sort(0, n - 1));    }    private static long merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; long res = merge_sort(l, mid) + merge_sort(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 {  tmp[k++] = q[j++];  res += mid - i + 1;     } // 扫尾 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];  return res;    }}

第五届2014年蓝桥杯真题

AcWing 1215. 小朋友排队

C++B组第10题

归并排序+贪心

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main {    static Child[] children;    static Child[] temp;    public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); children = new Child[n]; temp = new Child[n]; String[] num = in.readLine().split(" "); for (int i = 0; i < n; i++) {     children[i] = new Child(Integer.parseInt(num[i])); } mergeSort(0, n - 1); long res = 0; for (int i = 0; i < n; i++) res += cal(children[i].k); System.out.println(res);    }    private static long cal(int k) { return ((long) k * (k + 1)) / 2;    }    private static void mergeSort(int l, int r) { if (l == r) return; int mid = l + r >> 1; mergeSort(l, mid); mergeSort(mid + 1, r); merge(l, mid, r);    }    private static void merge(int l, int mid, int r) { int i = l; int j = mid + 1; int k = l; while (i <= mid && j <= r) {     if (children[i].h <= children[j].h){  children[i].k += (j - mid - 1);  temp[k++] = children[i++];     } else {  children[j].k += mid - i + 1;  temp[k++] = children[j++];     } } while (i <= mid){     // 此时右边区间的所有的都是小于i所在位置的小朋友的     children[i].k += r - mid;     temp[k++] = children[i++]; } while (j <= r) temp[k++] = children[j++]; for (int m = l; m <= r ; m++) {     children[m] = temp[m]; }    }    static class Child { int h; // 小朋友的高度 int k; // 该小朋友所涉及的逆序对的个数 即该小朋友需要交换的次数 public Child(int h) {     this.h = h; }    }}

有对代码不理解的地方可以在下方评论