蓝桥杯|蓝桥杯AcWing学习笔记 4-3排序的学习（附相关蓝桥真题（小朋友排队）(Java)） java|算法|排序算法|职场和发展

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

蓝桥杯我的AcWing
题目及图片来自蓝桥杯C++ AB组辅导课
归并排序

蓝桥杯|蓝桥杯AcWing学习笔记 4-3排序的学习（附相关蓝桥真题（小朋友排队）(Java)）

文章图片

归并排序——分治
① 确定分界点：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; } } }