在Java中使用BUBBLESORT对二维字符串数组进行排序

Question

类似的问题已经被询问过了，但是从未涉及2D字符串数组，因此经过长时间的尝试，我找不到我想要的。我正在尝试使用BubbleSort在Java中对2D字符串数组进行排序。 作为输入，我会接收一个String的二维数组（表格）和您应该排序的“列”的索引。我应该通过指定列中的值来对行进行排序。 您可以将第一个索引视为行索引，将第二个索引视为列索引。例如，以下Java数组和表格是相互对应的：

String[][] table = {
  {"a", "b"},
  {"c", "d"}
};

-

0   1
  +---+---+
0 | a | b |
  +---+---+
1 | c | d |
  +---+---+

为了继续这个例子，table[0][1]将返回值"b"，因为它是第0行第1列的项目。

重要提示：我不允许使用Java库中的任何排序算法，例如Arrays.sort。

这是我目前尝试过的内容：

class Solution {
        public static void stableSort(String[][] table, int column) {
            int i;
            int j;
            String temp = null;
            for (i = 0; i < table.length - 1; i++) {
                for (j = 0; j < table.length - 1 - i; j++) {
                    if (table[i][j].compareTo(table[i][j + 1]) > 0) {
                        temp = table[i][j];
                        table[i][j] = table[i][j + 1];
                        table[i][j + 1] = temp;
                    }
                }
            }
        }
    }

我遇到了索引越界的错误，并且它无法正常工作，因为测试期望在table[0][0]中获得不同的结果。

感谢您的帮助。

- user9955719

---

你需要仅使用冒泡排序吗？ - Nicholas K

建议：先为单个数组编写排序，然后进行泛化：您要排序的项不再是整数，而是整行数据。将比较方式更改为适用列之间的比较。switch 部分不应更改！ - RealSkeptic

没有冒泡排序会更容易。此外，冒泡排序的时间复杂度非常高。1）对字符串进行排序2）现在只需将其放置在数组索引中即可。 - Nicholas K

@NicholasK 时间复杂度和易用性在这里不相匹配。冒泡排序是最容易实现和理解的排序算法之一。 - Thomas

@PabloBiedma 你是要按列、行或行列排序吗？我的答案将取 {[i,h,g],[f,e,d],[c,b,a]} 并返回 {[a,b,c],[d,e,f],[g,h,i]}，但我不确定这是否符合您的要求。 - caleb baker

Answer 1

public static String[][] stableSort(String[][] table, int column) {
    int i=0,j=0;
    String[] temp = null;
    boolean swap=true;
    while(swap)
    for (i = 0; i < table.length - 1; i++) {
        swap=false;
        if(table[i][column].compareTo(table[i+1][column]) > 0){
            temp = table[i];
            table[i] = table[i+1];
            table[i+1]=temp;
            swap=true;
        }
    }
    return table;
}

它会一直使用冒泡排序，直到不再进行交换为止。在那时，条件 while(swap) 不再满足，该方法返回。 在主函数中尝试并且能够正常工作（如果我理解你的意思的话）：

public static void main(String[] args) {
    String[][] table = {
            {"z", "b", "v"},
            {"s", "w", "a"},
            {"r", "c", "h"}
    };

    table = stableSort(table,1);
    for(int i = 0; i < table.length; i++){
        for(int j = 0; j < table[0].length; j++){
            System.out.printf("%5s ", table[i][j]);
        }
        System.out.println();
    }
}

这将输出：

z     b     v 
r     c     h 
s     w     a 

- Pierangelo Calanna

Answer 2

编辑：工作正常，没有错误

如果我采取您的确切排序但添加一条if语句来切换行，添加一个外部循环来运行2D数组长度和宽度的次数，并将for循环控制更改为'＜= '，则会得到以下结果

   for(int z = 0; z < table.length * table.length; z++) // exterior for loop to run through the loop multiple times
   {
       for (i = 0; i <= table.length - 1; i++) {
           for (j = 0; j <= table.length - 1; j++) {
              if(j == table.length -1 && i == table.length-1) // If we are at the end then we can continue either to the next iteration or to the end of program
                  continue;
              if(j == table.length -1) // If you are ate the end of the row compare to the next row
              {
                   if (table[i][j].compareTo(table[i+1][0]) > 0) {
                       temp = table[i][j];
                       table[i][j] = table[i+1][0];
                       table[i+1][0] = temp;
                   } 
              }
              else if (table[i][j].compareTo(table[i][j + 1]) > 0) {
                   temp = table[i][j];
                   table[i][j] = table[i][j + 1];
                   table[i][j + 1] = temp;
              }
           }
       }
   }

我看到你在尝试最小化放置时的检查次数

table.length - 1 - i

这对于效率来说很好，但首先尝试让排序工作。然后再将其修剪以提高性能。

另外，我面前没有编译器，所以代码可能会有一些错误。

- caleb baker

Answer 3

首先，将其变成一维数组或至少是可索引的一维数组，这样会更容易。公式：

x = (int)index/(int)rows
y = index % rows

通过这个，你可以使用一个变量索引和索引一个二维数组，这是一个冒泡排序。

def sort(self):
    for passnum in range(len(self.array)-1,0,-1):
        for i in range(passnum):
            if self.array[i]>self.array[i+1]:
                temp = self.array[i]
                self.array[i] =  self.array[i+1]
                self.array[i+1] = temp

- user10767355

---

这不是Python吗？ - caleb baker

Answer 4

我的解决方案是：

import java.util.Arrays;

public class MySolution {
    public static void stableSort(String[][] table, int column) {
        String[] temp = null;
        int rows = table.length;
        for (int i = 0; i < rows; i++) {
            for (int j = 1; j < (rows - i); j++) {
                if (table[j - 1][column].compareTo(table[j][column]) > 0) {
                    temp = table[j - 1];
                    table[j - 1] = table[j];
                    table[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        String[][] table = { { "c", "d" }, { "a", "b" } };
        printTable(table);
        stableSort(table, 1);
        printTable(table);
    }

    private static void printTable(String[][] table) {
        System.out.println("table:");
        for (int i = 0; i < table.length; i++) {
            System.out.println(Arrays.toString(table[i]));
        }
    }
}

给你一些注意事项：

1. 使用有意义的名称（rows比table.length更容易理解）
2. 冒泡排序循环有点问题，网上有很多如何做的例子
3. 如前所述，您应该先针对1d数组进行操作，然后再“概括”它
4. 你遇到的一个大问题是：将j（应该是要比较的行的索引）用作列（并忽略列）
5. 另一个大问题是仅替换元素（而不是行）

希望这能帮助到你！

编辑：我刚刚注意到你在代码中也切换了行和列（在你的解释中，第一个索引表示行，在你的代码中似乎相反是正确的）

- Roy Shahaf

---

这个是如何检查是否不再进行交换的呢？我认为当表格变得很大时，它将无法正确地对其进行排序。 - Pierangelo Calanna