java - 为名称数组创建快速排序

Question

所以我正在为我的类(class)开发一个项目，目前我正致力于创建一个 QuickSort 类来对 1000 个名称的数组进行排序。我有一个模板，来 self 们之前在类里面做的实验，我们应该以此为基础；但在实验室中我们使用了一个整数数组，我正在努力解决如何转换它以便它可以与字符串一起使用；名称。感谢您的帮助或任何建议，代码如下。

更新帖子；所以我在我的 Name 类中进行了比较

 public int compareTo(Object other) {
        int result;
        if (name.equals(((Name) other).name))
            result = name.compareTo(((Name) other).name);
        else
            result = name.compareTo(((Name) other).name);

        return result;
    }

我尝试重新设计我的快速排序..我正在努力使用交换方法。

    private ArrayList<Name> data;

public QuickSort(ArrayList<Name> initialValue){

    data=initialValue;
}

public void sort(ArrayList<Name> namelist, int i, int j){

    sort(0, data.size()-1);
}

public void sort(int from, int to){

    if (from >= to)
        return;
    int p = partition(from, to);
    sort(from, p);
    sort( p + 1, to);
}

private int partition(int from, int to){

    Name pivot = data.get(from);
    int i = from - 1;
    int j = to + 1;

    while(i<j){

        i++; while(data.get(i).compareTo(pivot) < 0) i++;
        j--; while(data.get(j).compareTo(pivot) < 0) j--;
        if(i<j) swap(i,j);

    }

    return j;
}

private void swap (int i, int j){

    Name temp = data.get(i);
    data.equals(i) = data.get(j);
    data = temp;

}

特别是“data.equals(i) = data.get(j) 行和 data = temp; 我确信我正在做一些愚蠢而简单的事情。

更新；

private void swap (int i, int j){

    Name temp = data.get(i);
    data.get(j).equals(data.get(i));
    data.get(j).equals(temp);

}

可能吗？

Answer 1

发布解决问题的代码很容易，但不会帮助您了解 QuickSort(或其他排序算法)的含义。

快速排序的核心是交换元素:

while(i<j){
    i++; while(data[i] < pivot) i++;
    j--; while(data[j] > pivot) j--;
    if(i<j) swap(i,j);
}

如您所见，您正在比较 data 的元素针对 pivot 的数组多变的。因为他们是int s，您可以使用 < 轻松比较它们。现在，您必须执行类似的操作，但对于 String s。值得庆幸的是，String可以使用 String#compareTo 进行比较方法。我将让您实现 String (否则我会把作业当作我的=P)。

要获得更通用的问题解决方案，您有两种选择:

• 让你的类(class)实现 Comparable 接口(interface)，所以你将有一个 compareTo方法。一个基本的示例实现:

  public class Name implements Comparable<Name> {
      @Override
      public int compareTo(Name name) {
          return ... //comparison logic...
      }
  }
  

  在 QuickSort 中使用它

  pivot.compareTo(...);
  

• 使用 Comparator 的实例界面。您将使用Comparator#compare为了这。基本示例实现:

  public class NameComparator implements Comparator<Name> {
      @Override
      public int compare(Name name1, Name name2) {
          return ... //comparison logic...
      }
  }
  

  在 QuickSort 中使用它

  NameComparator nameComparator = new NameComparator();
  nameComparator.compare(..., ...);