今天我来讲一下归并排序以及归并排序的非递归实现形式首先提交以下代码普通归并void _MergeSort(int* arr, int* tmp, int left, int right) { if (left right) return; //归 int begin left; int end right; int mid begin (end - begin) / 2; //[begin,mid][mid1,right] _MergeSort(arr, tmp, begin, mid); _MergeSort(arr, tmp, mid 1, right); //并 int begin1 begin; int end1 mid; int begin2 mid 1; int end2 end; int i begin; while (begin1 end1 begin2 end2) { while (begin2 end2 arr[begin1] arr[begin2]) { tmp[i] arr[begin2]; begin2; i; } while (begin1 end1 arr[begin2] arr[begin1]) { tmp[i] arr[begin1]; begin1; i; } } while (begin1 end1) { tmp[i] arr[begin1]; } while (begin2 end2) { tmp[i] arr[begin2]; } memcpy(arr begin, tmp begin, sizeof(int) * (end - begin 1)); } void MergeSort(int* arr, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc); return; } _MergeSort(arr, tmp, 0, n - 1); free(tmp); tmp NULL; }非递归void MergeSortNon(int* arr, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc); return; } int begin 0; int end n - 1; int mid begin (end - begin) / 2; //[begin1,end1][begin2,end2] //end1越界 //begin2越界 //end2越界 for (int gap 1; gap n; gap * 2) { for (int j 0; j n; j 2 * gap) { int begin1 j; int end1 begin1 gap - 1; int begin2 end1 1; int end2 begin2 gap - 1; int i j; if (end1 n|| begin2 n) { break; } else if (end2 n) { end2 n - 1; } while (begin1 end1 begin2 end2) { while (begin2 end2 arr[begin1] arr[begin2]) { tmp[i] arr[begin2]; begin2; i; } while (begin1 end1 arr[begin2] arr[begin1]) { tmp[i] arr[begin1]; begin1; i; } } while (begin1 end1) { tmp[i] arr[begin1]; } while (begin2 end2) { tmp[i] arr[begin2]; } memcpy(arr j, tmp j, sizeof(int) * (2 * gap)); } /*memcpy(arr, tmp, sizeof(int) * n);*/ } free(tmp); tmp NULL; }所谓归并排序自然是分为归和并我简单演示一下过程如此图从中间拆分然后得到的每组数据再从中间拆分直到只剩一个数据这其实就已经有序了因为一个数据本身就是有序然后是并每次选一个最小值插入新数组这样可以保证局部有序直至完成归并。显然这是一个分而治之的思想要用递归实现递归实现的主要逻辑是区间的拆分后续有序数组的合并过程和我们之前讲的有序链表合并相似但略有不同不同点在于归并排序需要新建一个新数组。然后来讲一下非递归与上一讲快速排序不同的是归并的非递归并没有用到栈这一数据结构其实想想也容易明白虽然我们这里的黑核心仍然是拆分区间但拆分后我们还需要合并你拿栈去搞那拆分一次出栈回来合并的时候你也找不到之前区间了对吧所以我们这里直接给他改成循环。当然你说非要用栈行不行呢其实是可以的只不过你得用两个栈拿来存储区间这里就不多介绍了。那么非递归的核心又是什么呢看一下这张图我们直接前后取相同数进行归并不从中间拆开那这样就需要定义一个变量gap拿来指明每一组的数据个数比如90 23合并那90自己就是一组gap就等于1同理往下就不过多赘述了。其实和递归代码区别不大但细节方面还是需要处理首先gap取值一定不能n吧你比原数组都长哪来这么多元素呢那你能等于n吗等于1的时候是11合并合并成两个元素的有序数组那你等于n呢合并成2n个元素的有序数组哪来这么多元素给你合并其次怎样算是一次gap合并完成呢就是从前往后都归并一次对吧那你是不是要在写一层循环用于标注这次合并是否整体结束再往这个循环里走你怎么确定合并各个小组之间的起始和终止要利用gap的关系进行标注。到这里看似没啥问题了但其实还是不行gap我们设置的是倍乘增加这种只适用于有2的次方个元素个数的数组否则会越界这个越界还要处理三种情况第一是end1越界第二是begin2第三是end2前两种是一种情况后者则自己一组为什么呢当你end1越界的时候begin2和end2肯定越界了end1越界了意味着什么呢小组成员不够呗我拿10个元素的数组举例你最后一步肯定begin10end110此时这个数组已经有序了通过上一组82合并已经合并好了然后再往下才会出现这情况同理begin2越界也是如此所以直接break就好。那第三种情况咋办呢这就是上边说的82合并第一组没问题第二组元素不够那你第二组有多少就给多少呗直接把end2置为n-1即可