下面直接上代码:
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> void merge(int *a, int *c, int L, int R) { int mid = (L + R) >> 1; int i = L, j = mid + 1, k = L; while (i <= mid&&j <= R) //将 a 数组分成左右两边,归并到 c 数组 { if (a[i] <= a[j]) c[k++] = a[i++]; else c[k++] = a[j++]; } while (i <= mid) // 前半数组还有剩余的情况 c[k++] = a[i++]; while (j <= R) // 后半数组还有剩余的情况 c[k++] = a[j++]; for (i = L; i <= R; i++) // 放回去 a[i] = c[i]; } void mergeSort(int *a, int *c, int L, int R) { if (L == R) return; int mid = (L + R) >> 1; mergeSort(a, c, L, mid); mergeSort(a, c, mid + 1, R); merge(a, c, L, R); } int main(void) { const int N = 404; int n, a[N], c[N]; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); mergeSort(a, c, 1, n); for (int i = 1; i <= n; i++) { printf("%d ", a[i]); }puts(""); system("pause"); return 0; }
一,与 快排 的比较
这是一种和 快排 有点类似的算法,其总体流程基本相同,当具体思想却不相同,
① 总体上都是用分治的思想,不过 快排是 由大到小去做 partition
归并是 由小到大去做 merge
② 具体实现 partition 是 把数组以大小 分为左右两边
merge 是 把左右两边已经排好序的数组,归并到第二个数组,再放回去
二,merge 函数
把左右两边已经排好序的数组,归并到第二个数组,再放回去
① 注意 L,M,R 的位置
② 数组分别比较,哪个小那个插入数组中,直到哪个数组登顶了,即使另外一个一个也没插,也退出循环。
③ 剩下的数组直接放进出就可以了。
④ 再将整个数组放回去就可以了。
三,mergeSort 函数
merge 要处理的是排序好了的数组,所以怎么实现排好序呢
自然是 递归调用 merge,让它在 数组 长度为 1 时返回 ——> 所以,merge 函数是 从数组 长度 为 2 的 位置开始真正作用
——> 那你说 长度为 2 的数组,左右两边各一个,那左右数组不就是排好序了吗(此处应画重点 ( ̄▽ ̄)~■干杯□~( ̄▽  ̄) ——> 而且 merge 之后,数组又被排好序
——> 所以一直返回到 长度为 n 的时候,左右两边的数组是 已经排好序了的!!!
四,逆序对
此处 应该 提一下 逆序对,在merge 函数中,
① 首先 考虑一下 R 数组 把其中的元素放进 c 数组里面是什么情况就知道怎么做了
没错就是 L 数组里面的元素 比 R 数组里大的时候,
② 所以只要每次 R 数组要放的时候,算一下 L 数组还剩多少个, 这些都是比 R 数组 大的数,即逆序对
③ 然后累加就可以了
========== ========= ======== ======== ====== ====== ==== === == =
昔有盖世之德,今见罕见之才。——灵谷寺灵谷老人 给 汪精卫 的 贺联