通用数组列表冒泡排序问题

Question

我知道有内置的例程，但作为一个学习者，我想使用自己的方法进行排序。由于排序已经老掉牙了，所以我决定尝试制作自己的通用排序例程，可以用于数字或字符串，甚至日期，如果我能弄清楚它们在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
  }
}

我试图学习那些我感觉已经准备好了的东西，但却发现我还没有完全准备好；接近成功，但还是失败了。

- DSlomer64

---

作为一名学习者，我可以建议您学习比冒泡排序更好的排序算法吗？ - millimoose

此外，如果bubbleSort()是一个实例方法，你可能想要使用new Sort<Integer>().bubbleSort(ary);。如果它是一个静态方法，你将需要在方法本身上显式地传递类型参数，在声明方法时将其声明为public static <E extends Comparable<E>> bubbleSort(ArrayList<E> a) {...}，而不是将类型参数放在此案例中仅充当命名空间的Sort类上。 - millimoose

你完全误解了泛型。 - SLaks

除了Ruak的答案之外，Sort是抽象的，它不能被实例化，这意味着在你有一个具体的实现之前，你永远无法执行bubbleSort方法。根据你的代码，我认为没有必要将这个类声明为抽象的。 - MadProgrammer

我可以建议您不要对集合进行排序，而是对数组进行排序吗？您选择了计算机科学中最低效的排序算法之一，并且在最糟糕的方式下应用它。 - user207421

Answer 1

This:

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

这意味着 E 是任意对象类型，并且可以将 Sort<E> 的实例与 E 的实例进行比较。 (因此您的错误信息是在抱怨 E.compareTo 不存在，因为 Object 没有这样的方法。) 您需要的是这个：

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

这意味着 E 必须是一种类型，它的实例可以相互比较。

---

编辑补充: 实际上，就像SLaks指出的那样，没有真正的理由让 Sort 成为泛型；你只需要让 bubbleSort 方法成为泛型即可。此外，就像MadProgrammer所暗示的那样， Sort 应该是非抽象的（这样可以直接实例化），或者 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方法）。

- ruakh

---

评论一下最后一个问题，**bubbleSort(ary)**;，你就会得到完整的答案 ;) - MadProgrammer

实际上，该类根本不应该是泛型的。 - SLaks

Answer 2

我可以留下一条评论吗？

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

尽管如此，如果这让您学会如何使用和应用通用类型参数、使用控制流语句（例如for循环）甚至进行异常处理等重要操作，则对于新学习者来说通过这个练习也是有价值的。不要听信唱衰者的话。Bubblesort的主要优点是该算法简单易懂。

在我看来，一个更简单的排序算法是“Delayed Replacement Sort”，也称为“Selection Sort”。Delayed Replacement Sort与BubbleSort具有相同糟糕的时间复杂度（O（n ^ 2）），但与BubbleSort不同，Selection Sorting仍然在某些应用中使用。它被纳入一些优化排序算法的子算法中，并且由于它最小化了排序集合所需的交换次数，因此在执行交换的成本很高时仍然使用Selection Sort。

Delayed Replacement Sort的伪代码如下，我认为比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％，但仍不应用于对非常大的集合进行排序。

- scottb

---

scottb是正确的 - 作为Java学习者（不是最佳排序），冒泡排序确实帮助我克服了可能会非常困难的错误；现在他让我想要使用他的p-code或者实现快速排序，因为递归非常酷。 （同样很酷的是：在en.wikipedia.org/wiki/Quicksort上的动画） - DSlomer64

@DSlomer64：看看维基百科上“Stooge Sort”的动画吧，非常有趣。 - scottb

@scottb--你有注意到这个吗："该算法的名称来自于三个蠢货滑稽表演，其中每个蠢货都会打另外两个人[citation needed]"？我想知道需要引用的原因是确认例程命名的原因还是确认确实存在一集中Moe拍打了Larry和Curly，Larry拍打了Moe和Curly以及Curly拍打了Larry和Moe，如果是这样的话，就是哪一集或者什么情况？（我想象可能有多个这样的情节。） - DSlomer64

Answer 3

在接受SLaks的建议并更加熟悉泛型后（昨天制作了泛型堆栈和队列类），今天我使用了ruakh的大纲（但必须将“bubblesort”行中的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) {

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

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

但我仍然不知道为什么，“显然合法”还是不合法，我都没有想到任何一个“诀窍”。

编辑：一个词：经验。

- DSlomer64