1、介绍
归并排序既可以是内排序(在内存上的数据排序),也可以是外排序(磁盘上)(硬盘)(在文件中的数据排序)。
其他排序一般都是内排序。
区别于快速排序的非递归,归并排序非递归不适合使用栈。
因为快速排序的本质是一种前序递归,而归并排序的本质是一种后序递归,并没有“根”来区分左右。
那么归并排序的非递归应该怎么样实现呢?
2、思想
我们先想想归并的思想和目的:递归的分治是将数组分割成两边有序的子序列,然后再合并这两个。那么我们是否可以直接将数组中两两元素归并呢?答案是:对的!因为我们将数组中所有元素看作两两一组(每组数据中都各有一个元素),那么这一组中的两个元素单个来看就是有序的子序列,然后合并这两个元素。再往上就是四四一组(每组数据中都各有两个有序的元素),八八一组........
听起来好像很简单,其实坑很多,下面慢慢实现。
3、代码
void MergeSortNonR_incline(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail\n");
exit(-1);
}
int gap = 1;//1-1归
//gap代表归并每组数组个数,即gap个和gap个归并
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)//[0,n)
{
int begin1 = i, end1 = i + gap - 1;//第一组
int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二组
//[begin1,end1],[begin2,end2] 归并
//[0,0]-[1,1]归,[2,2]-[3,3],[4,4]-[5,5]....
//[0,1]-[2,3]归, [4,5]-[6,7]....
//[0,3]-[4,7]归, [8,11]-[11,15]......
// ......
//注意:begin1不会越界,end1,begin2,end2都可能越界,所以要修正
if (end1 >= n || begin2>=n)
break;
if (end2 >= n)
end2 = n - 1;
//合并,将arr中对应位置,放入tmp的对应位置
int j = begin1;
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++];
}
//[begin1,end1],[begin2,end2]
memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));//每次归并完拷贝回去
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
4、实现效果
int arr[] = { 1,6,41,32,5,12,7,11 };
int size = sizeof(arr) / sizeof(int);
printf("原数组\n");
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
printf("排序后\n");
MergeSortNonR_incline(arr, size);
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
原数组:1 6 41 32 5 12 7 11文章来源:https://www.toymoban.com/news/detail-801445.html
排序后:1 5 6 7 11 12 32 41文章来源地址https://www.toymoban.com/news/detail-801445.html
到了这里,关于排序算法8----归并排序(非递归)(C)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!