归并排序的原理及其多种方法的实现
✨✨✨学习的道路很枯燥，希望我们能并肩走下来!
目录
前言
一、归并排序的基本思想
二、代码实现
1.递归实现
2.非递归实现
三、 归并排序的特性总结
总
前言
本篇详细介绍了归并排序，让使用者对归并排序有进一步认识，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！。
一、归并排序的基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：
动图分析：
二、代码实现
1.递归实现
MergeSort_A(int* a, int* temp, int begin, int end)
{if (begin == end)return;int mid = (begin + end) / 2; //取中MergeSort_A(a, temp, begin, mid); //递归MergeSort_A(a, temp, mid+1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2) //结束条件为其中一方停止{if (a[begin1] <= a[begin2]) //依次比较，取小的尾插到temp数组中{temp[i++] = a[begin1++];}else{temp[i++] = a[begin2++];}}while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1)); //覆盖到原数组
}void MergeSort(int* a, int n)
{int temp = (int*)malloc(sizeof(int) * n); //创建存放数组temp，用于交换排序if (temp == NULL){perror("malloc fail");return;}MergeSort_A(a,temp, 0, n - 1);free(temp);temp = NULL;
}2.非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1; //begin（包括1，2，后end同）与end之间的元素个数while (gap < n){for (int j = 0; j < n; j += 2*gap){int begin1 = j, end1 = begin1 + gap - 1;int begin2 = begin1 + gap, end2 = begin2 + gap - 1;int i = j;if (end1 >= n || begin2 >= n) //越界问题处理break;if (end2 >= n)end2 = n - 1;while(begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));}gap *= 2;}free(tmp);tmp = NULL;
}越界问题处理：
三、 归并排序的特性总结
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
总结
✨✨✨各位读友，本篇分享到内容是否更好的让你理解了数据在内存中的存储，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！！。