1.归并排序介绍如果说快排是“先分后排”根据基准元素把数组分三块把左边区间排一排再把右边区间排一排数组就有序了那归并排序就是“先分到底再一层一层和并”。归并排序核心思想分解把整个数组从中间切成两半然后每半再切成两半……直到每一份只剩一个元素一个元素天然有序。合并把相邻的两份按顺序合并成一份有序的小数组。重复合并不断把有序的小数组合并成更大的有序数组直到全部合并成完整的一个有序数组。举个例子排序[6, 2, 8, 1, 9, 3]第一步不断切分[6, 2, 8, 1, 9, 3]左半[6, 2, 8]右半[1, 9, 3]左左[6, 2]左右[8]右左[1, 9]右右[3]再切[6] [2][1] [9]都只剩一个元素第二步两两合并重点合并[6]和[2]→ 谁小谁在前 →[2, 6][8]单独和[2,6]还不是同一层先放着[2,6]与[8]合并 → 比较 2,6 与 8 →[2,6,8]右边合并[1]和[9]→[1,9][1,9]与[3]合并 → 比较 1,9 与 3 →[1,3,9]第三步最终合并合并[2,6,8]和[1,3,9]像两副已经排好的牌每次取两堆顶部最小的那个比较 2 和 1 → 取 1 →[1]比较 2 和 3 → 取 2 →[1,2]比较 6 和 3 → 取 3 →[1,2,3]比较 6 和 9 → 取 6 →[1,2,3,6]比较 8 和 9 → 取 8 →[1,2,3,6,8]剩下 9 →[1,2,3,6,8,9]完成2.归并排序具体过程由上面例子可以看出来归并排序的第一步就是把区间划分成两部分。1均分区间求区间的中点midleftright1划分出来的两个区间为【leftmid】【mid1right】。2对左右区间进行排序也就是递归调用mergeSort传入要排序区间的左右端点mergeSortarrleftmidmergeSortarrmid1right递归的结束条件是leftrightleftright此时区间内只有一个元素已经有序直接回到上一层进行合并leftright说明区间不合法直接返回。3合并已经排好序的左右区间用排升序来说明借用辅助数组来合并区间辅助数组的大小和原数组大小一致定义为全局的。开始合并cur1left指向左区间的第一个元素cur2mid1指向右区间的第一个元素ileft表示将要放在辅助数组的哪个下标处。当arr【cur1】小于arr【cur2】要先放arr【cur1】cur1。否则就放arr【cur2】cur2。直到左右区间其中有一个元素先排完了while循环条件的由来while(cur1midcur2right)此时左右区间必定有一个区间中还有元素没有排完把没排完的区间排完。接下来就是从辅助数组中恢复到原数组恢复到原数组的下标left-right。3.归并排序完整代码//辅助数组 vectorint v; void mergeSort(int* arr, int left, int right) { //递归出口 区间内只有一个元素了说明这个区间已经有序了 if (left right) return; //均分数组 int mid (left right) 1; //[left,mid] [mid1,right] //对两个区间进行排序 mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); //合并两个有序数组 int cur1 left, cur2 mid 1, i left; while (cur1 mid cur2 right) { if (arr[cur1] arr[cur2]) v[i] arr[cur1]; else v[i] arr[cur2]; } //处理没排完的区间 while (cur1 mid) v[i] arr[cur1]; while (cur2 right) v[i] arr[cur2]; //恢复到原数组 for (int j left; j right; j) { arr[j] v[j]; } } int main() { int arr[] {5, 2, 8, 5, 1, 5, 3}; int n sizeof(arr) / arr[0]; v.resize(n); mergeSort(arr,0,n-1); return 0; }4.归并排序时间复杂度和稳定性时间复杂度O(n*logn) 稳定性稳定的