先赞后看,养成习惯!!!^ _ ^<3 ❤️ ❤️ ❤️
码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦!
所属专栏:排序算法
一、非递归思路
步骤如下:
1.先两两归并,两个为一组
2.然后根据每组的距离gap,分配组数进行排序
3.gap每次扩大2的倍数
4.注意一些细节:首先注意可能会出现最后一组归并会发生数组的越界,因此我们所使用的方法是排完一组拷贝一组,出现越界的情况还要分情况讨论进行判断如果begin2越界了,那这两组就不需要进行归并了
如果end2越界了,begin2没有越界,那么我们可以把end2修正成n-1,这样就可以两两归并了
细节图解:
文章来源:https://www.toymoban.com/news/detail-843008.html
二、代码演示
void _MergeSort(int* a, int n,int* tmp)
{
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;
//大于的部分就直接跳出不拷贝了
if (begin2 >= n)
{
break;
}
// 如果第二组的右边界越界,修正一下
if (end2 >= n)
{
end2 = n - 1;
}
int dex = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])
tmp[dex++] = a[begin2++];
else
tmp[dex++] = a[begin1++];
}
while (begin1 <= end1)
{
tmp[dex++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[dex++] = a[begin2++];
}
//排完一组拷贝一组
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
}
void MergeTest(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//MergeSort(a, 0,n-1,tmp);
_MergeSort(a,n,tmp);
}
int main()
{
int a[11] = {3,5,2,1,6,7,9,8,10,11,4};
MergeTest(a,sizeof(a)/sizeof(int));
for (int i = 0; i < 11; i++)
printf("%d ", a[i]);
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-843008.html
到了这里,关于排序算法:归并排序(非递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!