气泡排序对象

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);
            }
        }
    }
}

这是我的比较方法从我的超类（杂货店项目）

@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

我填写了你代码中缺失的部分。你应该阅读我如何提出一个好问题，以及如何创建一个最小的、可复制的示例的链接。

下面的代码是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对象的列表。填充列表后，将在两个嵌套的for循环中执行气泡排序。最后打印排序后的列表。

请注意，类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]

Answer 2

看起来在比较正确的值时存在一些不匹配。

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

下面使第一个循环递增障碍变量，第二个循环递减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（）的实现应该可以正常工作。所以，库存列表应该正确排序。

根据您的代码的几个通知：

>

建议为循环变量添加更有意义的名称，而不仅仅是i和j。它提高了未来代码的可读性和理解能力

其他块在comareTo（）处是冗余的

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