思想:
因为递归法的
归并排序实际上是将待排序的无序序列一分为二,直至分解到只剩下一个元素为止,然后不断合并二个排好序的子序列,按此思想可以写出消除递归的合并排序。这里使用的是分治策略。
/**
* EliminateRecursionMergeSort.java
*
* 非递归法实现合并排序.
*
* @author Administrator
*
*/
public class EliminateRecursionMergeSort {
public static void eliminateRecursionMergeSort(int[] a) {
int[] b = new int[a.length];
int s = 1; //有序序列的初始长度.
while( s < a.length ) {
Util.mergePass(a, b, s); //合并数组a中大小为s的相邻元素到数组b.
s*=2;
Util.mergePass(b, a, s); //合并数组b中大小为s的相邻元素到数组a.
s*=2;
}
}
/**
* @param args
*/
public static void main(String[] args) {
if (args.length == 0) {
System.out.println("请输入数字以空格隔开");
System.exit(-1);
}
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
eliminateRecursionMergeSort(a);
// 输出排序后的数组元素。
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
}
分享到:
相关推荐
归并排序,消除递归归并排序,快排,Java实现
c++实现的合并排序算法 用递归和非递归两种方式实现的
合并排序,使用非递归的方式,使输入的数组按升序排列
自然合并排序是对合并排序的非递归形式的一种改进,很好很有用
合并排序非递归算法是学习计算机算法与实现的一种应用,可以巩固c语言所学的知识
合并排序递归和非递归算法的实现可以让人理解到递归算法的实现有时候比非递归算法效率高很多,人只需要给出一个递归公式和一个递归出口,所有的事都可以交给计算机来完成了
合并排序的递归调用和合并排序的非递归调用的对比,可以让人感受到选择递归调用可以提高工作作业效率,只要得到递归公式和递归出口就可以了,问题解决起来会很省力
利用栈来消除递归 模拟快速排序的过程 实现非递归的快速排序
非递归归并排序详细分析,Java实现. 非常详细,基本上可以看明白
非递归归并排序.cpp
采用递归分治方法进行合并排序的算法下载 这是为上机做准备时写的
消除左递归消除左递归消除左递归消除左递归消除左递归
合并排序算法非递归形式源码 http://edsionte.com/techblog/archives/2898
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
分治法排序算法
朴素的动态规划,使用一维数组改进消除递归重复计算,消除递归这三种方法解决01背包问题,通过数据比较和运行的结果上来看,消除递归重复计算的递归算法效率相当高,在6组数据的时候,将效率提高了几乎一倍,我使用的...
采用冒泡、递归分治及非递归分治三种排序方式,测试过100、1000、10000、100000四个数据规模
java 快速排序 折半查找的界面实现 (递归与分治法)
实现并验证合并排序算法; Ex2:实现并验证快速排序算法 Ex3:用递归与分治的方法设计并实现寻找第k小元素算法
一个简单的合并排序的算法的演示过程。还不错。。