目录
1.知识回顾
归并排序的递归解法:125.【C语言】数据结构之归并排序递归解法
2.非递归解法
一般有两种改非递归的写法:1.用栈 2.用循环
对于归并排序而言,用栈来存储左右区间是不可以的,因为栈模拟的是前序遍历,而归并排序类似后序遍历
可以使用循环:两个两个归并→四个四个归并→……
如果数组元素个数为2的次方倍
以int arr[] = {10,6,7,1,3,9,4,2}为例,从小到大排序
两个两个归并:{10,6,7,1,3,9,4,2}→{6,10,1,7,3,9,2,4}
四个四个归并:{6,10,1,7,3,9,2,4}→{1,6,7,10,2,3,4,9}
八个八个归并:{1,6,7,10,2,3,4,9}→{1,2,3,4,6,7,9,10}
可以设一个变量gap来控制每次归并的个数(gap n.间隙)
稍微改改125.【C语言】数据结构之归并排序递归解法文章的代码即可写成一个框架
一个一个归并→两个两个归并→四个四个归并→八个八个归并→...... 发现归并的个数是有规律的,遵循个规律
| gap==1 | 2^1==2 |
| gap==2 | 2^2==4 |
| gap==4 | 2^4==16 |
例如gap==2时,每组数据个数为2(即==gap),两个一组归并,
gap初始值设为1,每次大循环结束后都自乘2,这样i+=2*gap就能实现gap个一组归并了
单次归并的框架代码(针对于2的次方倍个元素)
void non_recursive_mergesort(int* arr,int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
int gap = 1;
for (int i = 0; i < ; i += 2 * gap)
{
int begin1=, end1 = ;
int begin2=, end2 = ;
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[j++] = arr[begin1++];
while (begin2 <= end2)
tmp[j++] = arr[begin2++];
gap *= 2;
}
} 重点是填写begin1、end1、begin2、end2的值,依照每组数据个数为gap个的规则,画图分析:
(自右向左,gap个归并)
则有:
int begin1= i, end1 = i+gap-1;
int begin2= i + gap, end2 =i+2*gap-1 ;完整代码
gap为1,归并一次;gap位2,归并一次......
显然要有一个外循环来控制gap
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void non_recursive_mergesort(int* arr, int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
printf("debug info:\narr\'s size=%d\n",size);
while (gap < size)
{
printf("gap-%d\n", gap);
for (int i = 0; i < size; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
printf("[begin1, end1]=[%d,%d],[begin2,end2]=[%d,%d]\n", begin1, end1, begin2, end2);
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1)
{
printf("[begin1, end1]=[%d,%d]\n", begin1, end1);
tmp[j++] = arr[begin1++];
}
while (begin2 <= end2)
{
printf("[begin2,end2]=[%d,%d]\n", begin2, end2);
tmp[j++] = arr[begin2++];
}
}
memmove(arr, tmp, sizeof(int)*size);
gap *= 2;
}
free(tmp);
}
int main()
{
int arr[] = { 10,6,7,1,3,9,4,2 };
non_recursive_mergesort(arr, sizeof(arr)/sizeof(int));
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
printf("%d ", arr[i]);
return 0;
}运行结果:
如果数组的元素个数不是2的次方倍
例如,上述数组改成:int arr[] = { 10,6,7,1,3,9,4,2,99 };运行时会出问题
发现:begin1没有越界(因为begin=i,i没有越界),但end1、begin2、end2均出现越界情况,因此需要分类讨论不同的越界情况
一共有两种写法,不同写法对不同的越界情况的处理不一样
1.归并完了后再拷贝到原数组中(麻烦,不建议写)
则memove应该写在while (gap < size)循环的外面:
处理end1越界
那begin2和end2肯定越界
如果越界了,不用归并,但必须先拷贝到tmp,因为归并完了后tmp要拷贝到原数组中,如果不先拷贝到tmp,那tmp的数据拷贝到原数组会让原数组丢失数据!
继续归并,更正end1为size-1;修改begin2和end2为不存在的区间就不能归并了(让begin2>end2即可,注意不能begin2==end2,因为是[begin2,end2]闭区间,begin2==end2时区间内仍然有一个元素)
if (end1 >= size)
{
end1 = size - 1;
begin2 = size;
end2 = size - 1;
}处理begin2越界
那end2肯定越界
修改begin2和end2为不存在的区间
if (begin2 >= size)
{
begin2 = size;
end2 = size - 1;
}处理end2越界
继续归并,更正end2为size-1
if (end2 >= size)
{
end2 = size - 1;
}修正后的完整代码
void non_recursive_mergesort(int* arr, int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
printf("debug info:\narr\'s size=%d\n",size);
while (gap < size)
{
printf("gap-%d\n", gap);
for (int i = 0; i < size; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
if (end1 >= size)
{
end1 = size - 1;
begin2 = size;
end2 = size - 1;
}
if (begin2 >= size)
{
begin2 = size;
end2 = size - 1;
}
if (end2 >= size)
{
end2 = size - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
printf("[begin1, end1]=[%d,%d],[begin2,end2]=[%d,%d]\n", begin1, end1, begin2, end2);
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1)
{
printf("[begin1, end1]=[%d,%d]\n", begin1, end1);
tmp[j++] = arr[begin1++];
}
while (begin2 <= end2)
{
printf("[begin2,end2]=[%d,%d]\n", begin2, end2);
tmp[j++] = arr[begin2++];
}
}
memmove(arr, tmp, sizeof(int)*size);
gap *= 2;
}
free(tmp);
}再次测试数组int arr[] = { 10,6,7,1,3,9,4,2,99 };运行结果:
提交到LeetCode的912. 排序数组题上测试:
2.一边归并一边拷贝到原数组中(推荐,处理方法简单)
则memove应该写在while (gap < size)循环的里面:
每次只memmove从begin1到end2之间的元素
处理end1越界和begin2越界
让[begin1,end1]和[begin2,end2]归并,但第一个区间有越界的部分,不需要归并(归并一定是两个区间归并),因此都停止归并(注意:不用拷贝到tmp中,因为没有必要)
if (end1 >= size || begin2 >= size)
{
break;
}其实可以简写成: if (begin2 >= size),end1如果越界,那么begin2一定越界
处理end2越界
继续归并,更正end2为size-1
if (end2 >= size)
{
end2 = size - 1;
}修正后的完整代码
void non_recursive_mergesort(int* arr, int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
printf("debug info:\narr\'s size=%d\n",size);
while (gap < size)
{
printf("gap-%d\n", gap);
for (int i = 0; i < size; i += 2 * gap)//{ -2,3,-5 }
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
if (end1 >= size || begin2 >= size)
{
break;
}
if (end2 >= size)
{
end2 = size - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
printf("[begin1, end1]=[%d,%d],[begin2,end2]=[%d,%d]\n", begin1, end1, begin2, end2);
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1)
{
printf("[begin1, end1]=[%d,%d]\n", begin1, end1);
tmp[j++] = arr[begin1++];
}
while (begin2 <= end2)
{
printf("[begin2,end2]=[%d,%d]\n", begin2, end2);
tmp[j++] = arr[begin2++];
}
memmove(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}再次测试数组int arr[] = { 10,6,7,1,3,9,4,2,99 };运行结果:
提交到LeetCode的912. 排序数组题上测试:
