java - 对 2D ArrayList 进行冒泡排序

Question

我正在尝试对内部列表中有 7 列的 2d ArrayList 进行冒泡排序。第三列是价格。我正在尝试比较行的价格列，并将价格较高的行与价格较小的行交换。这意味着最后 ArrayList 应该有按价格升序排列的行。

但是每次交换行时，较大行中的所有元素都会更改为较小行中的相同元素。下面是代码。

boolean found = true;
do{
    found = false;
    for(int i = 0; i <= rc; i++) {
        if(i + 1 <= rc) {
            if(Integer.parseInt(list.get(i).get(3)) > Integer.parseInt(list.get(i + 1).get(3))) {
                ArrayList<String> greater = list.get(i);
                ArrayList<String> smaller = list.get(i + 1);
                for(int k = 0; k <= 7; k++) {
                    list.get(i).set(k, smaller.get(k));
                    list.get(i + 1).set(k, greater.get(k));
                }   
                found = true;
            }
        }
    }
} while(found == true);

原始数组列表:

[[1, sagarmatha, 5000, 7000, Two-Star, Two-Person-Room, 2, Resturant],
 [2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI]]

排序后:

[[2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI],
 [2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI]]

Answer 1

让我们从交换 ArrayList 中两个元素的最有效方法开始:

public void <T> swap(ArrayList<T> list, int i, int j)
{
    T tmp = list.get(i);
    list.set(i, list.get(j));
    list.set(j, tmp);
}

这是高效的，因为它不会以任何方式触及元素，只是四处移动引用。它使用 set ，因此列表中的任何元素都不会移动，也不会重新分配任何内容。

现在让我们看看你的swap是怎么写的:

ArrayList<String> greater = list.get(i);
ArrayList<String> smaller = list.get(i + 1);
for(int k = 0; k <= 7; k++) {
    list.get(i).set(k, smaller.get(k));
    list.get(i + 1).set(k, greater.get(k));
}

for 循环试图将一个列表的数据复制到另一个列表中，这从一开始就不是最佳选择。真正的问题是您没有使用临时变量来保存交换(注意我在上面的函数中是如何做到的)。让我们看一下交换期间数据的第 k 元素发生了什么:

1. 从 smaller.get(k) -> "A"和 greater.get(k) -> "B"开始
2. 在 list.get(i).set(k, smaller.get(k)); 之后，您将得到 smaller.get(k) -> “A”和 greater.get(k) -> “A”因为 list.get(i) == greater。
3. list.get(i + 1).set(k, greater.get(k)); 只是将“A”从第一行重新分配回 smaller破坏了 greater 中最初的内容。

要解决这个问题，您需要先将 greater.get(k) 的原始值存储到一个临时变量中:

ArrayList<String> greater = list.get(i);
ArrayList<String> smaller = list.get(i + 1);
for(int k = 0; k <= 7; k++) {
    String temp = greater.get(k);
    greater.set(k, smaller.get(k));
    smaller.set(k, temp);
}