4

我知道有内置的例程，但作为一个学习者，我想使用自己的设备进行排序，而且由于排序是老帽子，我决定尝试制作自己的通用排序例程，我可以将其用于数字或字符串，甚至可能日期，如果我弄清楚它们在 Java 中是如何工作的。

所以这就是我所拥有的，将一个错误换成另一个错误，直到现在我只有两个地方有错误（包含在“**”标记内），需要弄清楚如何进行比较。

package sort;
import java.util.ArrayList;

public  abstract class Sort<E> implements Comparable<E> {

   public void swap(ArrayList<E> a, int i, int j) {
    E c = a.get(i);
    a.set(i,a.get(j));// = a[j];
    a.set(j, c);
  }

  public void bubbleSort(ArrayList<E> a) {
    boolean inOrder = false;
    while (!inOrder) {
      inOrder = true;
      for (int i = 1; i < a.size(); i++) {
        **if( a.get(i - 1).compareTo(a.get(i)) > 0 )** {
//cannot find symbol: method compareTo(E); location: class Object
//where E is a type-variable: E extends Object declared in class Sort                 
      inOrder = false;
          swap(a, i, i - 1);
        } 
      }
    }
  }

  public static void main(String args[]) //hadda lose 'static' for 'setLayout' to work
  {
    ArrayList<Integer> ary = new ArrayList<>();
    ary.add(2); ary.add(4); ary.add(7); ary.add(3);
    **bubbleSort(ary)**;
//method bubbleSort in class Sort<E> cannot be applied to given types; 
//required: ArrayList<E>
//found: ArrayList<Integer>
//reason: actual argument ArrayList<Integer> cannot be converted to ArrayList<E> 
//by method invocation conversion where E is a type-variable:
//E extends Object declared in class Sort
    for (int i = 0; i < ary.size(); i++) {
      System.out.println(ary.get(i));
    }
  }

  @Override
  public int compareTo(E o) {
    **return 0;** // fixing errors above may help this fall into place
  }
}

我正在努力学习我觉得准备好的东西，却发现我还没有完全准备好；关闭，无雪茄。

4

3 回答 3

4

这：

public  abstract class Sort<E> implements Comparable<E> {

表示 thatE是任意对象类型，并且Sort<E>可以将 的实例与 的实例进行比较E。（所以你的错误信息抱怨E.compareTo不存在，因为Object没有这样的方法。）你想要的是：

public abstract class Sort<E extends Comparable<E>> {

这意味着 thatE必须是其实例可以相互比较的类型。

编辑添加：实际上，正如 SLaks 一起指出的那样，没有真正的理由Sort要通用；您只需要该bubbleSort方法是通用的。此外，正如 MadProgrammer 暗示的那样，要么Sort应该是 non- abstract（因此您可以直接实例化它），要么bubbleSort应该是static（因此可以在不实例化实例的情况下调用它Sort）或两者兼而有之。例如：

public class Sort {
    private static <E> void swap(ArrayList<E> a, int i, int j) {
        ...
    }

    private static <E extends Comparable<E>> void bubbleSort(ArrayList<E> a) {
        ...
    }

    ...
}

更好的是，Sort可以是一个sort方法的接口，并且BubbleSort.sort(...)只是它的一个实现（而不是给出Sort一个特定的bubbleSort方法）。

于 2013-09-29T23:40:10.740 回答
1

如果可以的话，我只想发表评论。

学习 BubbleSort 是学习如何在 Java 中使用数据结构的好方法。我同意其他人的观点，在现实世界中，你永远不会使用 BubbleSort，因为它提供了除“StoogeSort”之外的所有排序算法中最差的性能。

尽管如此，如果它教你如何做重要的事情，如使用和应用泛型类型参数、使用控制流语句（例如 for 循环），甚至进行异常处理，那么作为新学习者进行练习仍然是有价值的。不要听那些反对者的话。冒泡排序的主要优点是算法简单。

在我看来，更简单的排序算法是“延迟替换排序”，也称为“选择排序”。延迟替换排序与 BubbleSort (O(n^2)) 具有相同的糟糕时间复杂度，但与 BubbleSort 不同的是，选择排序仍在某些应用程序中使用。它作为子算法被合并到一些优化的排序算法中，并且因为它最大限度地减少了排序集合所需的交换次数，所以当执行交换的成本很高时，仍然使用选择排序。

延迟替换排序的伪代码如下，在我看来，它甚至比冒泡排序更简单：

Begin DELAYEDSORT
 For ITEM=1 to maximum number of items in list-1
    LOWEST=ITEM
    For N=ITEM+1 to maximum number of items in list
       Is entry at position N lower than entry at position LOWEST?
          If so, LOWEST=N
    Next N
    Is ITEM different from LOWEST
       If so, swap entry at LOWEST with entry in ITEM
 Next ITEM
End DELAYEDSORT

延迟替换排序可以比冒泡排序快 50%，但仍不应用于对非常大的集合进行排序。

于 2013-10-03T22:35:06.750 回答
0

在接受了 SLaks 的建议并更加熟悉泛型（昨天制作了泛型堆栈和队列类）之后，今天我使用了 ruakh 的大纲（但不得不更改private为public“冒泡排序”行），这使得主要更改main为理智的东西（现在沸腾了）到一个做某事有用的行Sort.bubbleSort(ary);）并且它起作用了，但我有两个迫切的问题：

(1) 第一个在这一行中究竟是什么<E>意思/做/暗示：

private static <E> void swap(ArrayList<E> a, int i, int j) {

(2) 同样...<E extends Comparable<E>>这里发生了什么：

private static <E extends Comparable<E>> void bubbleSort(ArrayList<E> a) {

回答我自己的问题，“现在，为什么我没有想到这些？”......“我为什么会想到它们？？”

编辑：“参数化”或“通用”方法与参数化/通用类型一样合法，为什么不呢？

但是我仍然不知道为什么，“显然合法”与否，我会想到任何一个“技巧”。

编辑：一个词：经验

于 2013-10-03T20:17:41.983 回答