对多维数组进行快速排序

Question

编辑：我希望此方法根据用户想要的任何列按升序排序（同一行中的每个数据彼此 'attached'）。 table 中有 4 列。如果用户想根据第一列进行排序，那么他应该做类似

的事情

mySortedTable[][] = ClassName.quickSort(myUnsortedTable,0);

如您所见，我尝试对标题中的内容进行编码。由于某种原因，我们的数据 table 被组织在一个二维字符串数组中（这不方便，必须来回转换以实现 ArrayList）。我使用第一个数据作为数据中心。介意和我一起调试吗？ :)

public static String[][] quickSort(String[][] data,int column) {
    //1st step, create ArrayLists needed and compare the data by the pivot to determine which ArrayList to be filled.
    ArrayList<String[]> hiData = new ArrayList<String[]>();
    ArrayList<String[]> loData = new ArrayList<String[]>();
    ArrayList<String[]> pivots = new ArrayList<String[]>();
    String[] pivot = {data[0][0],data[0][1],data[0][2],data[0][3]};
    for(String[] row : data) {
        if(row[column].compareTo(pivot[column])<0)
            loData.add(row);
        else if (row[column].compareTo(pivot[column])>0)
            hiData.add(row);
        else pivots.add(row);
    }

    //To decide whether is needed to create the array from the ArrayList for recursively sort the parted data.
    if(loData.size()>0) {
        String[][] loDataArr = new String[loData.size()][4];
        for(int i=0;i<loData.size();i++)
            loDataArr[i]=loData.get(i);
        if(loData.size()>1)
            loDataArr = quickSort(loDataArr,column);
    }
    if(hiData.size()>0) {   
        String[][] hiDataArr = new String[hiData.size()][4];
        for(int i=0;i<hiData.size();i++)
            hiDataArr[i]=hiData.get(i);
        if(hiData.size()>1)
            hiDataArr = quickSort(hiDataArr,column);
    }

    //Combine parted data into new array and return it to feed the recursive back up until the first recursive call.
    String result[][] = new String[hiData.size()+loData.size()+pivots.size()][4];
    int j=0;
    for(String[] row : loData) {
        result[j]=row;
        j++;
    }
    for(String[] row : pivots) {
        result[j]=row;
        j++;
    }
    for(String[] row : hiData) {
        result[j]=row;
        j++;
    }
    return result;
}

它输出所有的数组，但没有排序，也不等于它开始的数组。另外一个问题，我想问一下ArrayList<String[]>是不是不臭，是吗？

Answer 1

在Java中，数组总是一维的——尽管它们的元素类型本身可能是数组。所以 Java 中的二维数组只是数组的数组。

当您想要对数组进行排序以使行粘在一起时，这一事实变得非常方便。您将每一行视为一个对象，并使用比较器来比较该对象。

这里有一个小演示：

public class SortDemonstration {

    public static void main(String[] args) {

        String[][] table = {
                {"The", "Quick",  "Brown"},
                {"Fox", "Jumped", "Over"},
                {"A",   "Lazy",   "Dog"}
            };

        Arrays.sort( table, new ColumnComparator(0));
        System.out.println( Arrays.deepToString(table));

        Arrays.sort( table, new ColumnComparator(1));
        System.out.println( Arrays.deepToString(table));

        Arrays.sort( table, new ColumnComparator(2));
        System.out.println( Arrays.deepToString(table));
    }

    private static class ColumnComparator implements Comparator<String []>{
        private final int index;
        public ColumnComparator(int index) {
            this.index = index;
        }
        @Override
        public int compare(String[] o1, String[] o2) {
            return o1[index].compareTo(o2[index]);
        }

    }

}

ColumnComparator class 是解决问题的关键。它实现了两个字符串数组（两行）的比较器。它根据实例化索引处的项目比较行。

因此 new ColumnComparator(0) 根据第一列比较两行。 A new ColumnComparator(1) 根据第二列比较两行，以此类推

现在您有了这个比较器 class，您可以使用它对 "rows" 的数组进行排序。该程序的输出是：

[[A, Lazy, Dog], [Fox, Jumped, Over], [The, Quick, Brown]]
[[Fox, Jumped, Over], [A, Lazy, Dog], [The, Quick, Brown]]
[[The, Quick, Brown], [A, Lazy, Dog], [Fox, Jumped, Over]]

Answer 2

我在我的代码中发现了问题。我使用未排序的 ArrayList 而不是排序的二维数组来构建分块数据。

//Second step... 
        String[][] loDataArr = new String[loData.size()][4];
        String[][] hiDataArr = new String[hiData.size()][4];
        if(loData.size()>0) {
            for(int i=0;i<loData.size();i++)
                loDataArr[i]=loData.get(i);
            if(loData.size()>1)
                loDataArr = quickSort(loDataArr,column);
        }
        if(hiData.size()>0) {   
            for(int i=0;i<hiData.size();i++)
                hiDataArr[i]=hiData.get(i);
            if(hiData.size()>1)
                hiDataArr = quickSort(hiDataArr,column);
        }
        String result[][] = new String[hiData.size()+loData.size()+pivots.size()][4];
        int j=0;
        for(String[] row : loDataArr) {
            result[j]=row;
            j++;
        }
        for(String[] row : pivots) {
            result[j]=row;
            j++;
        }
        for(String[] row : hiDataArr) {
            result[j]=row;
            j++;
        }
        return result;
    }

对多维数组进行快速排序

quick sort on multidimensional array

java

recursion

multidimensional-array

quicksort