java - 为任何可比较集合编写排序方法 (Java)

Question

这是我在 Stack Overflow 上的第一篇文章。如果我可以做些什么来改进它:请分享。

我正在尝试学习不同的排序算法(例如插入、选择、冒泡、合并、快速、桶、基数、堆、shell、gnome 和 bogo 排序)并用 Java 实现它们。

我如何编写一个排序方法，它可以与任何实现 Collection 的类(或实现 Comparable 的任何类)一起使用？我看了source Collections.sort() 的方法签名中有一些我不明白的语法。

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

以下是我对如何编写 SortNone 方法的最佳(可悲的)猜测，该方法不会对 Collection 进行排序，但具有正确的方法 header 来执行此操作。我会使用 SortNone.sort(myCollection) 来调用它，其中 myCollection 是实现 Comparable 的类的任何实现 Collection 的类的实例(假设之前导入了 com.tenembasj.sort.*，请参阅更多信息)。

package com.tenembasj.sort;

public class SortNone {

    public static<T> void sort(Collection<E> collection) { //don't know how to require the object (is it T or E?) to implement Comparable
        //code to sort
        //would I have to use collection.size(), .get(i), .set(i), and such to edit the class implementing Collection?
    }
}

此外，我想添加一个 sort 方法，为 Comparator 添加一个参数，我只需要知道形式参数是什么。我想一旦我知道如何编写常规排序，我就可以弄清楚实现。

再次，我尝试编写自己的排序方法，而不是使用 Collections.sort()、Arrays.sort() 或任何 Java.util 方法。你可能会说“不要重新发明轮子”，但我只是想学习。

更多信息

我想在完成后将这些方法导出到 jar 中，并将它们作为库导入到我 future 的项目中。我创建了一个新项目(在 Eclipse 中)，创建了一个名为 com.tenembasj.sort 的包，并将添加诸如 MergeSort 之类的类。我相信这是标准命名约定，但如果不是，请告诉我。我的目标是能够在未来的任何项目中输入 import com.tenembasj.sort.* 并调用 MergeSort.sort(myCollection); 或 MergeSort.sort(myCollection, myComparator);。

Answer 1

如何编写一个排序方法，该方法适用于任何实现 Collection 的类(或实现 Comparable 的任何类)？

为了编写可应用于所有类型对象的函数，您必须编写通用代码，例如您在上面从 Collections.sort() 源代码中发布的代码。

假设您是初学者，最好的起点是从 generic 开始学习然后一次一口地吃掉大象。

<小时/>

我将尝试解释您上面发布的代码。

T泛型中任意类型的方法

extends Comparable<? super T>意味着 T 必须是一个 Comparable 对象。它可以是 Object 类型扩展 Comparable接口(interface)或任何包含类似接口(interface)的对象。

sort(List<T> list)意味着排序函数可以接受任何 List T 类型的对象作为论证。

public static <T extends Comparable<? super T>> void sort(List<T> list) {

//  Copying the values from the List of objects to an array.
    Object[] a = list.toArray();

//  Applying the array.sort operation.
    Arrays.sort(a);

//  Setting the values from the sorted array to the listi of type T. 
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

首先学习 generic