前面我写的归并排序实现,虽然原理上没什么问题,但算法实现不是很理想,今天没什么事情,重新优化了一下,这里比较一下:
1) 第1种方式,我采用了辅助存储来进行归并,代码如下:
private void MergeSort1(int[] A, int iS, int iE)
{
if (iS == iE)
{
count++;
return;
}
int iE1 = (iS + iE) / 2;
int iS2 = iE1 + 1;
MergeSort1(A, iS, iE1);
MergeSort1(A, iS2, iE);
//针对两个排好序的段(iS-iE1,iS2-iE)进行整理
int i1 = iS, j1 = iS2;
//这里的归并采用辅助存储空间的方式.
int[] Result = new int[iE - iS + 1];
int b = 0;
while(true)
{
count++;
if (j1 <= iE && i1 <= iE1)
{
if (A[i1] <= A[j1])
{
Result[b] = A[i1];
i1++;
}
else
{
Result[b] = A[j1];
j1++;
}
}
else if (j1 <= iE & i1 > iE1)
{
Result[b] = A[j1];
j1++;
}
else if (j1 > iE & i1 <= iE1)
{
Result[b] = A[i1];
i1++;
}
else
{
break;
}
b++;
}
//将结果回写到原数组,这是必须的,否则结果不对.
for (int j = iS; j <= iE; j++)
{
A[j] = Result[j - iS];
count++;
}
}
2)第2种方式,归并时没有采取辅助存储,代码如下:
private void MergeSort2(int[] A, int iS, int iE)
{
if (iS == iE)
{
count++;
return;
}
int iE1 = (iS + iE) / 2;
int iS2 = iE1 + 1;
MergeSort2(A, iS, iE1);
MergeSort2(A, iS2, iE);
//针对两个排好序的段(iS-iE1,iS2-iE)进行整理归并
int i1 = iS, j1 = iS2;
//因为都存放在数组的iS->iE段中,而且从小到大,从左到右存放。
//最大整理次数为iE-iS,但一般只要整理完其中一段后即可.
while (true)
{
//左边段当前值小于等于右边段最小值,则不需要移动,左边段指针i1右移一位即可。
if (A[i1] <= A[j1])
{
count++;
i1++;//右移
//因为两个段都是排序的,左边段如果整理完毕,则左边段不再需要整理
if (i1 >= j1)
{
break;
}
}
else
{
//如果左边段大于右边段,则需要移位处理.
//将j1移到i1处,原来的i1到j1-1整体右移一位.
int tmp = A[i1];
A[i1] = A[j1];
for (int b2 = j1; b2 > i1 + 1; b2--)
{
A[b2] = A[b2 - 1];
count++;
}
A[i1 + 1] = tmp;
i1++; j1++;
}
//因为两个段都是排序的,右边段如果整理完毕,则左边段不再需要整理
if (j1 > iE)
{
break;
}
}
}
两种方式,在速度上相差非常大,我测试后发现,Count计数的差距可达10倍,说明归并时采用上述的插入排序,虽然节省了空间,但时间上损失非常大(因为归并插入排序是的时间复杂度是的2次方级)。第1中方式采用了辅助存储,T(n)=2n,时间复杂度是线性的。实际上,如果归并算法的归并排序如果不借助辅助存储空间,而是移位的话,性能不比纯粹的插入排序好多少。归并排序在时间上和空间上比起快速排序来说,还是差很多。因此归并排序的实现还是要借助辅助存储空间,才会真正发挥其优势。
分享到:
相关推荐
归并排序 归并排序 归并排序 归并排序 归并排序
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
实现归并排序的c++代码,根据算法导论书籍内伪代码改写
代码是归并排序的c语言实现,归并算法MergeSortList.cpp
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
用C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
排序算法-归并排序详细讲解(MergeSort)
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
//输入整数1-7,选择排序方式 switch (i){ case 1: InsertSort(R); break; //值为1,直接插入排序 case 2: BubbleSort(R); break; //值为2,冒泡法排序 case 3: QuickSort(R,1,n); break; //值为3,快速排序 ...
mergeSort 方法实现了归并排序算法。它使用递归的方式将数组不断划分为更小的子数组,直到每个子数组只有一个元素,然后再依次将这些子数组进行合并,从而实现排序。 merge 方法用于合并两个有序子数组。它借助两个...
%mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用
归并排序 归并排序算法的实现。
本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下 一、思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n); (2)归并:将两个子序列从小到大...
使用C++书写的归并排序算法,希望对各位有用。也请大牛指教代码中有何不足的地方!
排序算法 排序算法_基于C语言实现的排序算法之MergeSort实现
//归并排序 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); ...
归并排序并行和顺序归并排序算法
归并排序执行三路归并排序