0

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

更新帖子；所以我在我的 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);

}

可能吗？

4

4 回答 4

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变量进行比较。由于它们是ints，因此您可以使用 轻松比较它们<。现在，您必须为 s 做类似的事情String。值得庆幸的是，String可以使用String#compareTo方法来比较 s。我会让你这个实现String（否则我会把家庭作业作为我的=P）。

对于更通用的问题解决方案，您有两种选择：

  • 使您的类实现Comparable接口，因此您将拥有一个compareTo方法。一个基本的示例实现：

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

    在您的快速排序中使用它

    pivot.compareTo(...);

  • 使用Comparator接口实例。您将Comparator#compare为此使用。一个基本的示例实现：

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

    在您的快速排序中使用它

    NameComparator nameComparator = new NameComparator();
nameComparator.compare(..., ...);
于 2013-07-12T15:26:10.470 回答
0

您可以使用比较器： Comparator.compare(o1, o2) 如果对象小于、等于或大于，则返回 -1、0 或 1。

java中的字符串实际上是可比较的，某种伴随接口：

 int compareTo(T other);

API 做：http ://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html

于 2013-07-12T15:24:00.657 回答
0

请注意，字符串比较是通过 equals 方法进行的：

data.get(j) == pivot => data.get(j).equals(pivot)
于 2013-07-12T15:32:18.650 回答
0

您必须设置一个字符串值才能将其与某物进行比较。因此，通过设置枢轴值将其与自身进行比较，它将返回零。由于不太可能所有字符串都等于您的枢轴值，因此与枢轴值相比的任何内容都将返回为 -1 或 1。通过这样做，您的 if 语句将确定交换值的发送方式（更高或更低）然后是您的枢轴价值。

    ObjectQuickSorter sortStrings = new ObjectQuickSorter();
    sortStrings.sort(arrayHere);

    class ObjectQuickSorter{

    void sort(String[] array){
        doQuickSort(array, 0, array.length -1);
    }

    private static void doQuickSort(String[] array,int start, int end){
        int pivotPoint;

        if(start < end){
            pivotPoint = partition(array, start, end);

            doQuickSort(array, start, pivotPoint -1);

            doQuickSort(array, pivotPoint + 1, end);
        }
    }

    private static int partition(String[] array, int start, int end){
        String pivotValue;
        int endOfLeftList;
        int mid = (start + end)/2;

        swap(array, start, mid);

        pivotValue = array[start];

        endOfLeftList = start;

        for(int scan = start + 1; scan <= end; scan++){
            // trying to compare pivot = string value to array[scan] position value
            // doing this by setting pivot value compare to itself to return 0
            // then also comparing pivot value to array[scan] to return -1, 0, 1
            // if return is 0 or 1 then it ignores it
            if(  array[scan].compareTo(pivotValue) < array[start].compareTo(pivotValue)){
                endOfLeftList++;
                swap(array, endOfLeftList,scan);
            }
        }

        swap(array, start, endOfLeftList);

        return endOfLeftList;
    }

    private static void swap(String[] array, int a, int b){
        String temp;

        temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}
于 2015-03-10T12:37:09.907 回答