介绍二路归并排序的分治策略,分治思想的排序算法

//归并（非递归版)void _MergeSortNotR(int* a，int n){ int * tmp(int *)malloc(sizeof(int)* n)；if(tmp NULL){ perror(malloc fail)；退出(-1);} int gap 1；while(gap n){ for(int I 0；I n；i 2 * gap){int begin1 i，end 1i gap-1；int begin2 i gap，end 2 I 2 * gap-1；if (begin2 n)

{break;}if (end2 > n){end2 n - 1;}int index i;while (begin1 < end1 && begin2 < end2){if (a[begin1] < a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 < end1){tmp[index] a[begin1];}while (begin2 < end2){tmp[index] a[begin2];}memcpy(ai, tmpi, (end2-i1) * sizeof(int));}gap * 2;}free(tmp);} ⭐代码实现详解:

分配一个临时数组tmp用于存储归并结果。

设置一个变量gap为1表示归并的间隔大小。

接下来循环执行以下操作直到gap大于等于n

遍历整个数组每次取两个相邻的子序列进行归并。计算左右两个子序列的起始和结束位置。判断右子序列的结束位置是否超过了数组的长度如果超过则将结束位置设置为数组的最后一个元素的下标。使用两个指针begin1和begin2分别指向左右两个子序列的起始位置使用指针end1和end2分别指向左右两个子序列的结束位置。使用一个指针index指向当前归并结果的位置。使用一个循环比较左右两个子序列的元素大小并将较小的元素放入临时数组tmp中同时移动相应的指针。如果左子序列还有剩余元素则将剩余元素复制到tmp数组中。如果右子序列还有剩余元素则将剩余元素复制到tmp数组中。将tmp数组中的元素复制回原数组a中。将gap乘以2进行下一轮归并。

最后释放临时数组tmp的内存空间。

️归并排序特性总结 稳定性归并排序是一种稳定的排序算法即相等元素的相对顺序在排序后不会改变。时间复杂度归并排序的时间复杂度是O(nlogn)其中n是待排序序列的长度。这是由于归并排序的核心操作是将序列分成两个子序列然后分别进行排序再将排序好的子序列合并而分割和合并操作都需要O(logn)的时间所以总的时间复杂度是O(nlogn)。空间复杂度归并排序的空间复杂度是O(n)其中n是待排序序列的长度。这是由于归并排序需要一个与待排序序列相同大小的额外空间来存储临时的合并结果。非原地排序归并排序不是原地排序算法即它需要额外的空间来存储临时的合并结果。这是因为在合并操作中需要同时访问两个子序列的元素并将它们按照顺序合并到一个新的序列中。递归实现归并排序通常使用递归的方式来实现即将待排序序列不断分割成更小的子序列直到子序列的长度为1然后再将这些子序列按照顺序合并成一个有序的序列。递归实现的归并排序代码简洁易懂但是由于递归调用的开销比较大所以在实际应用中可能会使用迭代的方式来实现归并排序。适用性归并排序适用于各种数据规模的排序而且对于大规模数据的排序效果较好。它的时间复杂度稳定在O(nlogn)不会因为数据规模的增大而导致时间复杂度的增加。此外归并排序还适用于外部排序即对于无法一次性加载到内存的大规模数据进行排序。 ️全篇总结

​ 经过对归并排序的思想特性代码实现这些细致入微的讲解相信聪明的你肯定已经学会了叭

☁️ 好了由于篇幅有限,本章只是对归并进行了深度解刨后序会出更多的排序算法哦
看到这里了希望给博主留个
点赞收藏 ⭐️ 关注
❤️
拜托拜托这个真的很重要
你们的点赞就是博主更新最大的动力
有问题可以评论或者私信呢秒回哦。