1

我想建立一种排序方法将数组“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; 
    }
}

怎么了

4

3 回答 3

1

我看到的第一件事是，当您调用递归方法时，您使用fst++的是++fst.

于 2010-10-25T02:03:07.467 回答
1

如果这不是家庭作业，那么您应该使用 Arrays.sort(int[]) 在 Java 中对整数进行排序。

于 2010-10-25T02:15:53.820 回答
0

您可以使用预先存在的排序方法，并依赖Integer（或任何其他类型）的自然排序。您需要做的就是编写一个转发compareTo方法（实现Comparable）来Node检查泛型参数是否实现'Comparable'，然后将方法调用转发到compareTo存储的对象。

您将值存储为一个字段，然后只需使用正常的“instanceof”检查来检查是否Comparable已实现、转换为Comparable然后调用该方法。简单的。现在，您可以使用Arrays.sort(nodearray)wherenodearray是一个Node<?>. 那是你所追求的吗？:)

排序算法是经过调整的快速排序。

正如另一张海报提到的，如果你有一个intor数组Integer，你可以直接使用一个Arrays.sort(..)方法，但是由于类中的封装，我们需要转发调用Node。

从 Arrays.java 实现快速排序（你可以修改它）：

    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       }
于 2010-10-25T02:18:14.140 回答