冒泡排序对象

Question

我需要使用冒泡排序按名称对我的食品杂货库存进行排序。

显然，我的代码没有按名称对列表进行排序。

顺便说一句，存储清单的数据来自文件输入。

这是我的代码。

public void sortInventoryByName() {
    //TODO: use bubble sort and compareTo
    int n = inventory.size();
    GroceryItem temp;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (inventory.get(j).compareTo(inventory.get(j + 1)) > 0) {
                temp = inventory.get(i);
                inventory.set(i, inventory.get(i + 1));
                inventory.set(i + 1, temp);
            }
        }
    }
}

下面是我的超类(GroceryItem)中的compareTo方法

@Override
public int compareTo(Object o) {
    if(getClass() != o.getClass()) {
        throw new IllegalArgumentException();
    }
    else {
        GroceryItem other = (GroceryItem) o;
        return (this.name.compareTo(other.name));
    }
}

Answer 1

看起来您在比较正确的值时有一些不匹配的地方。

有两种方法可以实现带有两个for循环的冒泡排序算法。

下面使第一个循环增加了barrier变量，第二个循环减少了index。

因此，对于外部循环的每一次迭代，最低值将被移到第一位(就像最小的气泡将首先被移动一样)。下一次迭代将跳过第一个元素。它将一直持续到列表满列表结束。

您的示例显示了相反的行为->，对于外部循环的每次迭代，列表中最高的元素都被移到末尾。

你到底想如何迭代内部for循环并不是那么重要。最终的排序结果是我们的目标。

代码片段：

public void sortInventoryByName() {
    int n = inventory.size();
    for (int barrier = 0; barrier < n - 1; barrier++) {
        for (int index = n - 2; index >= barrier; index--) {
            if (inventory.get(index).compareTo(inventory.get(index + 1)) > 0) {
                GroceryItem temp = inventory.get(index);
                inventory.set(index, inventory.get(index + 1));
                inventory.set(index + 1, temp);
            }
        }
    }
}

您的compareTo()实现应该工作得很好。因此，inventory列表应该是正确排序的。

根据您的代码有以下几点注意事项：

• 你不需要在循环之外声明temp变量。它只是一个用于交换两个值的临时变量。内联声明和使用就足够了。

• 建议为循环变量添加更有意义的名称，而不仅仅是i和j。它在未来的

中增加了代码的可读性和理解性。

compareTo()上的

• else数据块是冗余的

@Override
public int compareTo(Object o) {
    if (getClass() != o.getClass()) {
        throw new IllegalArgumentException();
    }
    GroceryItem other = (GroceryItem) o;
    return this.name.compareTo(other.name);
}

Answer 2

我填上了你的代码中缺失的部分。你应该阅读How do I ask a good question和How to create a Minimal, Reproducible Example的链接。

下面的代码是GroceryItem类，它只包含一个成员，即name，它是杂货商品的名称。由于您的问题只涉及对此成员的操作，因此我没有尝试猜测该类需要哪些其他数据。

代码后面的解释。

import java.util.ArrayList;
import java.util.List;

public class GroceryItem implements Comparable<GroceryItem> {
    private String  name;

    public GroceryItem(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    @Override // java.lang.Comparable
    public int compareTo(GroceryItem other) {
        if (other == null) {
            return 1;
        }
        else {
            String otherName = other.getName();
            if (name == null) {
                if (otherName == null) {
                    return 0;
                }
                else {
                    return -1;
                }
            }
            else {
                if (otherName == null) {
                    return 1;
                }
                else {
                    return name.compareTo(otherName);
                }
            }
        }
    }

    @Override // java.lang.Object
    public boolean equals(Object other) {
        boolean equal = false;
        if (other instanceof GroceryItem) {
            GroceryItem otherItem = (GroceryItem) other;
            if (name == null) {
                equal = otherItem.getName() == null;
            }
            else {
                equal = name.equals(otherItem.getName());
            }
        }
        return equal;
    }

    @Override // java.lang.Object
    public int hashCode() {
        return name == null ? 0 : name.hashCode();
    }

    @Override // java.lang.Object
    public String toString() {
        return name;
    }

    public static void main(String[] args) {
        List<GroceryItem> inventory = new ArrayList<>();
        inventory.add(new GroceryItem("apple"));
        inventory.add(new GroceryItem("pear"));
        inventory.add(new GroceryItem("banana"));
        inventory.add(new GroceryItem("orange"));
        inventory.add(new GroceryItem("beetroot"));
        inventory.add(new GroceryItem("onion"));
        inventory.add(new GroceryItem("lettuce"));
        inventory.add(new GroceryItem("carrot"));
        inventory.add(new GroceryItem("guava"));
        inventory.add(new GroceryItem("lychee"));
        inventory.add(new GroceryItem("kiwi"));

        int n = inventory.size();
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (inventory.get(j).compareTo(inventory.get(j+1)) > 0) {
                    // swap inventory[j+1] and inventory[j]
                    GroceryItem temp = inventory.get(j);
                    inventory.set(j, inventory.get(j+1));
                    inventory.set(j+1, temp);
                }
            }
        }
        System.out.println();
    }
}

上面的代码创建了一个包含11个元素的GroceryItem对象的List。填充List之后，在两个嵌套的for循环中执行冒泡排序。最后，打印排序后的List。

请注意，类GroceryItem还实现了方法toString()，以便在打印GroceryItem实例时使输出变得可读。

如果将来需要使用GroceryItem作为java.util.HashMap的键，那么GroceryItem将需要重写方法hashCode()，如果一个类重写了方法hashCode()，那么它也应该重写方法equals()。因此，这就是为什么上面的代码包含那些被覆盖的方法。请注意，冒泡排序不需要这些方法中的任何一个- equals()、hashCode()和toString()。

运行上述代码时的oputput为：

[apple, banana, beetroot, carrot, guava, kiwi, lettuce, lychee, onion, orange, pear]