/*
* mergesort_unrecursive.cpp
*
* Created on: Dec 14, 2011
* Author: junfeng
*
//从分治策略的机制入手,容易消除归并排序算法中的递归,事实上,
//算法Mergesort的递归过程只是将待排序列 集合一分为二,直到待排序列集合
//只剩下一个元素为止,然后不断合并两个排好序的数组段。按此机制,可以首先
//将数组a中相邻元素两两配对。用合并算法将它们排序,构成n/2组长度为2的排好
//序的子数组段,然后再将它们 排序成长度为4的排好序的子数组段,如此继续下去,
//直至整个数组排好序。这就是自然合并排序的思想。对于n元数组已排好序情况
//自然排序算法不执行合并,而算法mergesort需执行[logn]次合并。
*
*
*/
#ifndef MERGESORT_UNRECURSIVE_
#define MERGESORT_UNRECURSIVE_
#include<stdio.h>
void mergesort_unrecursive(int* a, const int n);
void print(int const * a, const int n);
int main()
{
int a[] = { 1, 3, 2, 4, 5, -1, 0, -2, -3, -4, -5 };
int len = sizeof(a) / sizeof(*a);
print(a, len);
mergesort_unrecursive(a, len);
print(a, len);
return 0;
}
void mergesort_unrecursive(int* a, const int n)
{
int* b = new int[n];
int len = 1;
while (len < n)
{
/*
* 初始len==1
*/
int start = 0;
int end = start + len;
int k, start_max, end_max;
while (start < n)
{
start_max = start + len;
end_max = end + len;
/*
* 处理一个小于len片断的情况
*/
if (start_max > n)
break;//结束当前len的一次merge
/*
* 处理最后一个长度len和小于len的两个片断
*/
if (end_max > n)
end_max = n;//
// printf("start=%d\n", start);
// printf("start_max=%d\n", start_max);
// printf("end=%d\n", end);
// printf("end_max=%d\n", end_max);
//复制merge的部分
for (int i = start; i < end_max; i++)
b[i] = a[i];
/*
* end==start+len;
* merge [start,end]
* [end,end+len]
*/
k = start;
while (start < start_max && end < end_max)
{
if (b[start] < b[end])
a[k++] = b[start++];
else
a[k++] = b[end++];
}
while (start < start_max)
a[k++] = b[start++];
while (end < end_max)
a[k++] = b[end++];
/*
* 下2个len的片断
*/
start = end_max;//这个开始错写尾s=end+len;
end = start + len;
// printf("len=%d\n", len);
// printf("a=");
// print(a, n + 1);
}
len = len * 2;//开始错误:没有这句
}
delete[] b;
}
void print(int const * a, int const n)
{
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
#endif //MERGESORT_UNRECURSIVE_
分享到:
相关推荐
归并排序 归并排序算法的实现。
用非递归算法实现合并排序,具有高效的特征,从底向上
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
归并排序并行和顺序归并排序算法
归并排序 归并排序 归并排序 归并排序 归并排序
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
用C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
MergeSort合并排序
归并排序 (相当)无痛依赖类型编程的案例:Agda 中完全认证的归并排序 Agda 中的合并排序正确性证明 我们在 Agda 中展示了一个经过完全认证的合并排序版本。 它的特点是:终止的句法保证(即不需要明确的终止证明)...
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
非递归快速排序归并排序堆排序基数排序的实现 //快速排序 function quickSort ( arr ) { var parts = [ [ 0 , arr . length - 1 ] ] ; while ( parts . length ) { var part = parts . shift ( ) ; var l = part...
代码是归并排序的c语言实现,归并算法MergeSortList.cpp
%mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用
排序算法-归并排序详细讲解(MergeSort)
mergeSort 方法实现了归并排序算法。它使用递归的方式将数组不断划分为更小的子数组,直到每个子数组只有一个元素,然后再依次将这些子数组进行合并,从而实现排序。 merge 方法用于合并两个有序子数组。它借助两个...
mergesort.h为归并排序的资源文件,main.c为merge sort的用法。
归并排序执行三路归并排序
//归并排序 public void MergeSort(int low, int high, int[] a) { int mid, i, j, k; int[] b = new int[high+1]; if (low >= high) { return; } mid = (low + high) / 2; MergeSort(low,mid,a); ...
归并排序的C++代码,是TXT文档形式,希望有用