【数据结构初阶】一文带你学会归并排序(递归非递归)
创始人
2024-06-03 10:07:59
0

目录

前言

递归实现

代码实现

 非递归实现

代码实现

总结


 

前言

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

递归实现

在我们前边的学习过程中,例如合并两个有序数组等问题,我们就使用过归并的思想,本质上来说归并排序还是分治的思想,将大问题化为小问题,然后解决小问题,最终是实现大问题的解决。

 动图演示

 

归并排序的递归实现并不复杂,有以下几个步骤:

1.首先申请一段空间tmp,用来保存以及排好序的部分数据,当所有数据都排序完后,重新拷贝回原数组。

2.对数组数据进行分割,例如二叉树分为左右子树一样,也将数组分割为左右数组,知道左指针left大于等于右指针right时,返回。

3.对以及递归好的数据进行排序,两个区域内的数据进行比较,小的数据插入到tmp数组中,直至到数组的最后一个数据,如果当一个数组提前结束,直接将另外一个数组数据直接拷贝即可。

4.将排序好的tmp数组拷贝回原数组。

代码实现

由于原函数不适合递归,所以我们定义子函数,并且求出left和right进行递归,将数组分为[left,mid]和[mid+1,right]两个部分,切记free我们申请的空间,其余按照思路实现即可。

void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int mid = left + (right - left) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int i = left;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;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++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}
}
void MergeSort(int* a, int n)
{int left = 0;int right = n - 1;int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, left, right, tmp);free(tmp);tmp = NULL;
}

 非递归实现

归并的非递归实现起来比递归实现较难一点,但是还是分治的思想,只不过非递归有点类似于二叉树的后序遍历,我们使用gap来控制每次归并时数组内数据个数,例如第一次就是一个一个数据归并成两个数据的有序数组,第二次使用两个数据的有序数组归并成四个数据的有序数组,所以gap是由1开始,并且每次乘2。

非递归实现就是在gap等于1时,将整个数组元素排序成两个两个有序,这个递归实现是不同的。

但是当我们每次将gap乘2时,我们发现数组元素个数不一定是2的次方倍,所以不进行处理时,我们的数组一定会造成越界访问。

我们对每次要归并的数组,第一个数组起始为begin1,结束为end1,第二个数组起始为begin2,结束为end2,所以就会有以下三种情况越界:

1.end1越界,即end1>=n。

2.begin2越界,即begin2>n。

3.end2越界,即end2>=n。

所以我们要对边界进行修正,当边界>=n时,我们将其赋值为n-1,修正如下:

            if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}

我们注意到当begin1>=n时,我们将begin2 赋值为n,end2赋值为n-1,我们发现这样的话这段区间就不存在了,这是为什么呢,我们来探究一下。

 

 我们对程序进行以上的处理,发现程序崩溃了,通过调试发现是tmp数组越界了,那么tmp数组为什么会越界呢?

 通过测试发现,本来只有十个数据,所以下标最多到9,但是tmp数组的下标10的位置插入元素,导致越界,这是因为当[begin2,end2]原本不存在,但是我们修正让其存在[9,9],多插入一个数据,所以导致越界,所以我们做一下修改。

 处理过后就没有下标的越界了。

代码实现

当我们解决这个问题之后,其余代码按照思路实现就好了。

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("maolloc fail");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2*gap - 1;int InDex = i;if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}/*printf("[%d,%d] ", begin1, end1);printf("[%d,%d] ", begin2, end2);*/while (begin1 <= end1 && begin2 <= end2){//printf("%d ", InDex);if (a[begin1] < a[begin2]){tmp[InDex++] = a[begin1++];}else{tmp[InDex++] = a[begin2++];}}while (begin1 <= end1){//printf("%d ", InDex);tmp[InDex++] = a[begin1++];}while (begin2 <= end2){//printf("%d ", InDex);tmp[InDex++] = a[begin2++];}}for (int j = 0; j < n; j++){a[j] = tmp[j];}gap *= 2;}free(tmp);tmp = NULL;
}

总结

我们今天讲解了归并排序的递归和非递归的实现方法,码文不易,希望可以对大家有所帮助。

 

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...