2

我目前正在使用 Java 实现各种排序算法，主要是为了好玩，但我正在努力解决如何“正确”地做到这一点。也就是说，我希望用户能够在任何可比较的东西上调用选择的排序算法 - ints、longs、Strings、booleans（实际上，这些在 Java 中是否可比较？），他们自己的类；任何。问题是如何做到这一点。

我正在考虑使用一个类来表示排序算法，因此使用通用列表或其他任何东西（）存储要排序的东西List<E>。这也将允许我使用多个构造函数，从而允许用户以各种形式传入数据 - 列表、数组等。这是正确的方法吗？我目前的问题是我不希望用户在想要对某些东西进行排序时必须创建一个类，我宁愿它能够被称为类似System.out.println或类似的东西。

// Example:

int[] myInts = {5,4,3,2,1};

// This is what I do *not* want.
InsertionSort mySort = new InsertionSort();
int[] sortedInts = mySort.sort(myInts);

// This is more like what I want.
int[] sortedInts = Sorting.insertionSort(myInts);

对于一个看似基本的问题，我深表歉意，但我只是在学习编程语言。对于在一家软件公司从事暑期工作的 2 年级计算机专业学生来说，这有点可笑，但您会惊讶于我的大部分工作只需要很少的编程知识……通常需要更多的设计知识。

编辑：

为了清楚起见，我的三个主要问题是：

  • 是让用户创建一个类来进行排序，还是在用户导入的类中有一个静态方法更好？
  • 是否可以轻松处理原始数据类型和通用对象？由于我希望能够处理任何实现可比较（或类似）的通用对象，因此这会导致原语出现问题（因为它们没有实现任何东西；））。
  • 处理通用输入的最佳方法是什么 - 在尝试对它们进行排序之前我应该​​检查什么（例如，实现 Comparable）？
4

4 回答 4

1

您可以以提供 binarySearch 操作的方式为例Collections......事实上，

int[] sortedInts = Sorting.insertionSort(myInts);

更Java方式，即使我个人更喜欢

public class Sorting {
     public static <DataType extends Comparable> Iterable<DataType> insertionSort(Iterable<DataType> data);
}
  • <DataType>确保输出数据与输入数据类型相同
  • Iterable<DataType>data 输入数据是可迭代的，以确保最大的兼容性。显然，使用 List 非常简单，因为它允许内部项目重新排序。然而，使用可迭代确保此方法的实现者必须重新创建列表才能修改它，保证输入列表保持不变，而输出列表是另一个列表。

由于我刚刚看到您编辑了您的问题，因此让我逐点回复它（并考虑在此之后选择一个答案，因为添加新问题比无休止地编辑现有问题更容易 - 除非您将问题设为社区 wiki，就像我对这个回复所做的那样）

是让用户创建一个类来进行排序，还是在用户导入的类中有一个静态方法更好？

在我看来，在这种情况下使用静态方法更可取，因为您必须以一种非常“基本”的方式操作不是您创建的对象。

是否可以轻松处理原始数据类型和通用对象？由于我希望能够处理任何实现Comparable（或类似）的通用对象，因此这会导致原语出现问题（因为它们没有实现任何东西；））。

你听说过自动装箱吗？这是 Java 5 的一个特性，它使对象的主要类型“等效”。也就是说，int 会自动转换为 Integer，如您所知，它实现了 Comparable。

处理通用输入的最佳方法是什么 - 在尝试对它们进行排序之前我应该​​检查什么（例如，实现 Comparable）？

请注意，由于我的方法声明 (the )，检查输入数据是否实现 Comparable 不是由您完成的，而是由 Jav 编译器完成的，从而允许您的 IDE 向您显示错误。

于 2010-07-20T09:10:24.553 回答
1

我想你回答了你自己的问题？如果你想公开一个静态方法而不是让用户创建和对象并调用实例方法，那么就这样做。Sorting.insertionSort()对我来说看起来不错。

在内部，它可以发送到你喜欢的任何东西。在里面，如果你想用类和多态等等来实现它，请继续。不过，这似乎有点矫枉过正。我不确定继承和多态在这里有多大帮助。

于 2010-07-20T09:55:37.210 回答
1

实现排序算法的常规方法是实现静态方法，例如查看 Arrays.sort() 的源代码。您可以使用针对不同参数类型的不同实现来重载此方法（例如，实现可比较的对象与提供您自己的比较器与原始数组等）

这是我之前写的一篇：

public static <T> void swap(T[] a, int x, int y) {
    T t=a[x];
    a[x]=a[y];
    a[y]=t;
}

public static <T extends Comparable<? super T>> void mergeInOrder(T[] src, T[] dst, int p1, int p2, int p3, int p4) {
    if (src[p2].compareTo(src[p3])<=0) return; // already sorted!

    // cut away ends
    while (src[p1].compareTo(src[p3])<=0) p1++;
    while (src[p2].compareTo(src[p4])<=0) p4--;

    int i1=p1;
    int i3=p3;
    int di=p1;
    while(di<p4) {
        if (src[i1].compareTo(src[i3])<=0) {
            dst[di++]=src[i1++];
        } else {
            dst[di++]=src[i3++];
            if (i3>p4) {
                System.arraycopy(src,i1,dst,di,p2-i1+1);
                break;
            }
        }
    }

    System.arraycopy(dst, p1, src, p1, (p4-p1)+1);
}

public static <T extends Comparable<? super T>> void mergeSort(T[] src, T[] dst, int start, int end) {
    if (start+1>=end) {
        if (start>=end) return;
        if (src[start].compareTo(src[end])>0) {
            swap(src,start,end);
        }
        return;
    }

    int middle=(start+end)/2;
    mergeSort(src,dst,start, middle);
    mergeSort(src,dst,middle+1, end);
    mergeInOrder(src,dst,start,middle,middle+1,end);
}

private static ThreadLocal<Comparable<?>[]> mergeSortTemp=new ThreadLocal<Comparable<?>[]>();

@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] src) {
    int length=src.length;
    Comparable<?>[] temp=mergeSortTemp.get();
    if ((temp==null)||(temp.length<length)) {
        temp=new Comparable[length*3/2];
        mergeSortTemp.set(temp);
    }
    mergeSort(src,(T[])temp,0,length-1);
}

但是，我可以想到将排序算法实现为生成自己的实例的类的两个很好的理由：

  • 它允许您多态地传递排序算法的实例——例如，如果您正在创建排序算法的集合并希望在它们上运行大量基准测试，这可能会很有用。
  • 您可以在排序器实例中拥有私有状态 - 这对于某些排序算法很有用，例如有一些预先分配的数组用于临时存储，如果您希望能够同时使用不同的对来自多个线程的实例进行排序——静态方法实现需要某种形式的同步（例如，参见上面代码中 ThreadLocal 的使用）。
于 2010-07-20T12:07:01.387 回答
0

我不确定这是否是您正在努力解决的问题……但是几乎不可能实现一种既适用于引用类型又适用于（真实）原始类型的算法。原因是 Java 类型系统没有具有基本类型和子类型的概念通用类型Object。

正常的解决方法是使用它们对应的包装类来包装原始类型；例如Integerfor int, Booleanforbool等等。这允许您实现（例如）用于 anyCollection<T>或 any的排序算法<T>[]。

当应用于（比如说）整数的大型数组时，这种方法存在性能/内存使用问题。要么降低性能，要么为每个基本类型分别实现算法及其支持类。

（我说几乎不可能，因为可以抽象出一对数组元素的比较和一对数组元素的交换，而不是在接口中暴露实际元素类型；例如

public interface ArraySortAdapter {
  public abstract int compareElements(Object array, int pos1, int pos2);
  public abstract void swapElements(Object array, int pos1, int pos2);
}

并为不同的数组类型提供不同的实现；例如

public class IntArraySortAdapter implements ArraySortAdapter {
  public int compareElements(Object array, int pos1, int pos2) {
      int[] intArray = (int[]) array;
      if (intArray[pos1] < intArray[pos2]) {
          return -1;
      } else if (intArray[pos1] > intArray[pos2]) {
          return +1;
      } else {
          return 0;
      }
  }

  ...
}

但是，至少可以这样说，这既麻烦又低效……）

于 2010-07-20T09:58:26.980 回答