Java backtracking problem
i want to 开发者_JAVA技巧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
First thing I see is that when you called the recursive method, you used fst++
instead of ++fst
.
If this isn't homework, then you should be using Arrays.sort(int[]) to sort ints in 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 forwarding compareTo
method (implementing Comparable
) for Node
that checks if the generic argument implements 'Comparable'
and then forwards the method call to compareTo
of the stored object.
You store the value as a field, and then just use the normal 'instanceof' check to check that Comparable
is implemented, cast to Comparable
and then just call that method. Easy. Now, you can use Arrays.sort(nodearray)
where nodearray
is an array of Node<?>
. Is that what you were after? :)
The sort algorithm is a tuned quicksort.
As another poster mentioned, if you have an array of int
or Integer
, you can use an Arrays.sort(..)
method directly, but we need to forward the call due to the encapsulation in the Node
class.
Implementation of quicksort from Arrays.java (you can modify this):
1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
2390 private static void sort(int start, int end, int[] array) {
2391 int temp;
2392 int length = end - start;
2393 if (length < 7) {
2394 for (int i = start + 1; i < end; i++) {
2395 for (int j = i; j > start && array[j - 1] > array[j]; j--) {
2396 temp = array[j];
2397 array[j] = array[j - 1];
2398 array[j - 1] = temp;
2399 }
2400 }
2401 return;
2402 }
2403 int middle = (start + end) / 2;
2404 if (length > 7) {
2405 int bottom = start;
2406 int top = end - 1;
2407 if (length > 40) {
2408 length /= 8;
2409 bottom = med3(array, bottom, bottom + length, bottom
2410 + (2 * length));
2411 middle = med3(array, middle - length, middle, middle + length);
2412 top = med3(array, top - (2 * length), top - length, top);
2413 }
2414 middle = med3(array, bottom, middle, top);
2415 }
2416 int partionValue = array[middle];
2417 int a, b, c, d;
2418 a = b = start;
2419 c = d = end - 1;
2420 while (true) {
2421 while (b <= c && array[b] <= partionValue) {
2422 if (array[b] == partionValue) {
2423 temp = array[a];
2424 array[a++] = array[b];
2425 array[b] = temp;
2426 }
2427 b++;
2428 }
2429 while (c >= b && array[c] >= partionValue) {
2430 if (array[c] == partionValue) {
2431 temp = array[c];
2432 array[c] = array[d];
2433 array[d--] = temp;
2434 }
2435 c--;
2436 }
2437 if (b > c) {
2438 break;
2439 }
2440 temp = array[b];
2441 array[b++] = array[c];
2442 array[c--] = temp;
2443 }
2444 length = a - start < b - a ? a - start : b - a;
2445 int l = start;
2446 int h = b - length;
2447 while (length-- > 0) {
2448 temp = array[l];
2449 array[l++] = array[h];
2450 array[h++] = temp;
2451 }
2452 length = d - c < end - 1 - d ? d - c : end - 1 - d;
2453 l = b;
2454 h = end - length;
2455 while (length-- > 0) {
2456 temp = array[l];
2457 array[l++] = array[h];
2458 array[h++] = temp;
2459 }
2460 if ((length = b - a) > 0) {
2461 sort(start, start + length, array);
2462 }
2463 if ((length = d - c) > 0) {
2464 sort(end - length, end, array);
2465 }
2466 }
精彩评论