网站和浏览器不兼容,住建局主要负责什么,网站建设方案概述,软件工程专业就业方向及前景分析大家好#xff0c;我是苏貝#xff0c;本篇博客带大家了解归并排序#xff0c;如果你觉得我写的还不错的话#xff0c;可以给我一个赞#x1f44d;吗#xff0c;感谢❤️ 目录 归并排序#xff08;用递归#xff09; 之前我们写了一篇博客来介绍如何用递归实现归并排序… 大家好我是苏貝本篇博客带大家了解归并排序如果你觉得我写的还不错的话可以给我一个赞吗感谢❤️ 目录 归并排序用递归 之前我们写了一篇博客来介绍如何用递归实现归并排序那么不用递归也可以实现归并排序吗是的
初步非递归归并排序: 注意上面的图只是为了方便看才感觉是在原数组上修改的实际上是先比较2个数组之后将这2个数组合成的数组存入额外的数组tmp中之后再拷贝回原数组。
2个要合并成一个有序数组的下标怎么表示呢我们来以gap2举例 begin1i end1igap-1 begin2igap end2i2*gap-1
代码如下 但是这段代码有些问题你能看出来吗
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[j] a[begin1];elsetmp[j] a[begin2];}while (begin1 end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
}问题当原数组的数组元素不为2^n时2个数组可能会越界如下图1还要与不是数组元素的值相比 所以我们要处理2个数组下标越界的可能
1. begin1越界 因为begin1被置为iin所以begin1不会越界 2. end1越界 就是上图的情况此时第一个数组肯定有序第二个数组肯定不存在所以直接退出循环 3. begin2越界 begin2越界时第二个数组肯定不存在所以也不需要操作直接退出循环 4. end2越界 当begin2没越界而end2越界时只需将end2置为最后一个元素的下标n-1即可
代码
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (end1 n || begin2 n)break;if (end2 n)end2 n - 1;int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[j] a[begin1];elsetmp[j] a[begin2];}while (begin1 end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
}好了那么本篇博客就到此结束了如果你觉得本篇博客对你有些帮助可以给个大大的赞吗感谢看到这里我们下篇博客见❤️
