归并排序#include iostream using namespace std; const int N 1e6 10; int q[N], v[N], n; // 写法一、m进行下取整进行归并 void merge_sort(int q[], int l, int r) { if(l r) return; int m l r 1; merge_sort(q, l, m); merge_sort(q, m 1, r); int i l, j m 1, idx l; while(i m j r) { if(q[i] q[j]) v[idx ] q[i ]; else v[idx ] q[j ]; } while(i m) v[idx ] q[i ]; while(j r) v[idx ] q[j ]; for(int i l, k l; i r; i) q[i] v[k ]; } // 写法二、以m 进行上取整进行归并 void function(int l, int r){ if(l r) return; int m l r 1 1; function(l, m - 1); function(m, r); int i l, j m, idx l; while(i m j r) { if(q[i] q[j]) v[idx ] q[i ]; else v[idx ] q[j ]; } while(i m) v[idx ] q[i ]; while(j r) v[idx ] q[j ]; for(int k l, i l; i r; i, k) q[i] v[k]; } int main(){ 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]); }这个算法的本质是使得q[l, m]q[m 1, r]区间中的所有数有序然后开用一个额外的空间v去处理递归中的一个(可以看作是用m为划分点的两个)数组中的数字。待证问题v数组中保存的是q[l...m]、q[m 1...r]中从小到大所有的有序数。(m 1其实就是j)证明第一个while循环v[0...idx - 1]中保存的是上述两个数组中所有数组从小到大的有序数。1.初始idx l 0v数组为空结论显然成立。2.保持假设某一轮循环开始之前循环不变式成立若q[i] q[j]则v[idx ] q[i]其中q[i] q[i 1...mid]q[i] q[j] q[j 1... r]∴q[i]是剩下所有数字中最小的一个当q[i] q[j]时同理可以得到v[idx] q[j]是剩下数中最小的一个∴v[idx]是剩下数中最小的一个∴idx自增之后下轮循环开始之前v[0..idx-1]保存从小到大排序的最小k个数3.终止i mid或j r则q[l..mid]和q[mid1..r]其中一个数组的数都已遍历。v[0..idx-1]保存从小到大排序的最小idx个数边界分析为什么不用mid - 1作为分隔线呢即merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)因为mid l r 1是向下取整mid有可能取到0(数组只有两个数时即使是N多的数最后也会被递归到2个)造成无限划分。解决办法:mid向上取整就可以了, 即mid l r 1 1。补充写法二需要将i m修改成为i m因为上面已经将区间划分成q[l, m - 1]与q[m, r]此时左半段的最大取值是m - 1。所以需要写成开区间形式。while循环的i, m, j, r可以视作将一个区间分成两个有序区间的四个划分点。