Java回溯问题
我想建立一个排序方法将数组“4,2,7,5,1”排序为“1,2,4,5,7”我当前的代码是
public static Node<Integer> sort_it(int[] arr, int fst, int last, Node<Integer> part_soln)
{
if (fst>last)
return part_soln; // return a sorted list
else {
for (int row=0; row<=last; row++)
{
if (!exists(arr[row],part_soln) && ((arr[row]<=part_soln.getItem())||part_soln==null))
{
Node<Integer> new_soln = new Node<Integer>(row,part_soln);
Node<Integer> ret=sort_it(arr,fst++,last,new_soln);
if(ret!=null)
return ret;
}
}
return null;
}
}
错误的
i want to build a sorting method to sort array "4,2,7,5,1" into "1,2,4,5,7" my current code is
public static Node<Integer> sort_it(int[] arr, int fst, int last, Node<Integer> part_soln)
{
if (fst>last)
return part_soln; // return a sorted list
else {
for (int row=0; row<=last; row++)
{
if (!exists(arr[row],part_soln) && ((arr[row]<=part_soln.getItem())||part_soln==null))
{
Node<Integer> new_soln = new Node<Integer>(row,part_soln);
Node<Integer> ret=sort_it(arr,fst++,last,new_soln);
if(ret!=null)
return ret;
}
}
return null;
}
}
what is wrong
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我首先看到的是，当您调用递归方法时，您使用了
fst++而不是++fst。First thing I see is that when you called the recursive method, you used
fst++instead of++fst.如果这不是家庭作业，那么您应该使用 Arrays.sort(int[]) 对 Java 中的整数进行排序。
If this isn't homework, then you should be using Arrays.sort(int[]) to sort ints in Java.
您可以使用预先存在的排序方法，并依赖于
Integer（或任何其他类型）的自然排序。您需要做的就是为Node编写一个转发compareTo方法（实现Comparable），检查泛型参数是否实现'Comparable '，然后将方法调用转发给存储对象的compareTo。您将值存储为字段，然后只需使用正常的“instanceof”检查来检查
Comparable是否已实现，转换为Comparable，然后调用该方法。简单的。现在，您可以使用Arrays.sort(nodearray)，其中nodearray是Node的数组。这就是你所追求的吗？ :)排序算法是一种调整的快速排序。
正如另一位发帖者提到的，如果您有一个
int或Integer数组，则可以直接使用Arrays.sort(..)方法，但由于封装在Node类中，我们需要转发调用。Arrays.java 中快速排序的实现（您可以修改它）：
You can use the pre-existing sorting methods, and rely on the natural ordering of
Integer(or any other type). All you need to do is write a forwardingcompareTomethod (implementingComparable) forNodethat checks if the generic argument implements'Comparable'and then forwards the method call tocompareToof the stored object.You store the value as a field, and then just use the normal 'instanceof' check to check that
Comparableis implemented, cast toComparableand then just call that method. Easy. Now, you can useArrays.sort(nodearray)wherenodearrayis an array ofNode<?>. Is that what you were after? :)The sort algorithm is a tuned quicksort.
As another poster mentioned, if you have an array of
intorInteger, you can use anArrays.sort(..)method directly, but we need to forward the call due to the encapsulation in theNodeclass.Implementation of quicksort from Arrays.java (you can modify this):