典型的汉诺塔圆盘移动方法:
/**
* 每次只能移动一个圆盘,将原本放在初始位置的圆盘借助中间位置按原来的顺序移动到目标位置
*
* @param topN 开始时在初始位置共有多少圆盘
* @param from 初始位置
* @param inter 中间位置
* @param to 目标位置
*/
public static void doTowers(int topN, char from, char inter, char to)
{
if(topN == 1)//将最后一个圆盘放到最终位置
System.out.println(" DISK 1 FROM " + from + " TO " + to);
else
{
doTowers(topN - 1, from, to, inter);//借助于目标位置先将除最后一个圆盘的所有圆盘放在中间位置
System.out.println(" DISK " + topN + " FROM " + from + " TO " + to);
doTowers(topN - 1, inter, from, to);//借助于初始位置将已经处于中间位置的除最后一个圆盘的所有圆盘放在目标位置
}
}
归并排序类:
/**
* @param args 归并排序,递归方法
* @author xujp1
*/
class Darray
{
private final long[] theArray;
private int eItem;
public Darray(int max)
{
theArray = new long[max];
eItem = 0;
}
public void insert(long value)
{
theArray[eItem++] = value;
}
public void display()
{
for(int i = 0; i < eItem; i++)
System.out.print(theArray[i] + " ");
System.out.println();
}
public void mergeSort()
{
long[] workspace = new long[eItem];
recMergeSort(workspace, 0, eItem - 1);
}
public void recMergeSort(long[] workspace, int lowerBound, int upperBound)
{
if(lowerBound == upperBound)
return;
else
{
int mid = (lowerBound + upperBound) / 2;
recMergeSort(workspace, lowerBound, mid); // 归并前半部分
recMergeSort(workspace, mid + 1, upperBound); // 归并后半部分
merge(workspace, lowerBound, mid + 1, upperBound);
}
}
/**
* 类似于两个数组从小到大合并到第三个数组
*
* @param workspace 中间变量(类似于第三个数组,即合并的结果)
* @param lowerPtr 数组下标最左边(类似于第一个数组的index1)
* @param highPtr 数组下标中间位置(类似于第二个数组的index1)
* @param upperBound 数组下标最右边,比较结束后可用此参数。
*/
public void merge(long[] workspace, int lowerPtr, int highPtr, int upperBound)
{
int j = 0;
int lowerBound = lowerPtr; // lowerBound后续用到
int mid = highPtr - 1; // 作为跟lowerPtr比较的参数
int n = upperBound - lowerPtr + 1; // 本次归并后的数组大小
/**
* 最左边的值和中间的值进行比较,哪个数比较小则赋值给workspace,同时下标加1。
*/
while (lowerPtr <= mid && highPtr <= upperBound)
if(theArray[lowerPtr] > theArray[highPtr])
workspace[j++] = theArray[highPtr++];
else
workspace[j++] = theArray[lowerPtr++];
while (lowerPtr <= mid)
workspace[j++] = theArray[lowerPtr++];
while (highPtr <= upperBound)
workspace[j++] = theArray[highPtr++];
for(int i = 0; i < n; i++)
theArray[lowerBound + i] = workspace[i];
}
}
注:以上代码均出自JAVA数据结构和算法第二版
分享到:
相关推荐
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
用C++实现的非递归的归并排序,此为实验小程序,仅供参考。
c++实现的合并排序算法 用递归和非递归两种方式实现的
合并排序,使用非递归的方式,使输入的数组按升序排列
归并排序,消除递归归并排序,快排,Java实现
源程序给出了插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序等多种排序算法,其中有17处需要填空。
非递归归并排序.cpp
递归调用归并排序.cpp
非递归归并排序详细分析,Java实现. 非常详细,基本上可以看明白
归并排序的非递归排序的代码解析
自然合并排序是对合并排序的非递归形式的一种改进,很好很有用
归并排序的非递归实现详细介绍了归并排序的非递归实现
合并排序递归和非递归算法的实现可以让人理解到递归算法的实现有时候比非递归算法效率高很多,人只需要给出一个递归公式和一个递归出口,所有的事都可以交给计算机来完成了
一个Java小程序,利用递归思想实现的归并排序算法。其中有两个类,排序数据是写死在main方法中的。
递归实现的二路归并排序算法,其中对结构体按其内部一个关键字(本例是对一个任务结构体,按其收益排序)进行排序
8645 归并排序 (非递归算法).txt
分治法排序算法
合并排序非递归算法是学习计算机算法与实现的一种应用,可以巩固c语言所学的知识
用java写的一些常用算法 如快速排序、归并排序、非递归的归并排序、堆排序等 后续还会加上其他常用算法 用java写的一些常用算法 如快速排序、归并排序、非递归的归并排序、堆排序等 后续还会加上其他常用算法 用java...
用C语言写的归并排序的递归写法.这是本人按照书本上的定义揣摩出来的写法。仅供大家参考。另外我的资源中还有非递归和自然归并。敬请下载。