对一个二维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]]

- krisha mahat

---

尝试仅移动引用而不是复制数组内容。如果没有中间缓冲区，您将遇到此问题。 - Mad Physicist

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，因此列表中的任何元素都不会被移动，也不会重新分配任何东西。

现在让我们看一下你的交换是如何编写的：

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

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

- Mad Physicist

Answer 2

在您的情况下，您并没有创建一个新的列表。相反，您正在使用您的列表的引用。因此：

greater = list.get(i);  //here greater _references_ the i'th element
                        //[1, sagarmatha, 5000, 7000, Two-Star, Two-Person-Room, 2, Resturant]

smaller = list.get(i+1); //here greater _references_ the i+1'th element
                         //[2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI]

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

让我们看看循环中会发生什么：

when k = 0: 
before assignment: list.get(i).get(0) = greater.get(0) = 1
                   list.get(i+1).get(0) = smaller.get(0) = 2

after assignment: list.get(i).get(0) = greater.get(0) = 2 which is the value of "smaller"

当您更改第一个列表的元素时， greater 的值也会更改，因为 greater 和 list.get（0）基本上是同一个对象，而不是彼此的副本。您需要创建另一个数组，然后在之后复制值。或者，您可以始终使用临时变量直接交换数组列表，例如：

private void swap (ArrayList list, int index1, int index2) {
    object temp = ArrayList[index1];
    ArrayList[index1] = ArrayList[index2];
    ArrayList[index2] = temp;
}

- Yamuk