冒泡排序对象

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)

@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。它提高了将来代码的可读性和可理解性

• else块在compareTo()处是冗余的

@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

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

下面的代码是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()这些方法。

运行上述代码时的输出是:

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