5

我有一个包含双值的二维 ArrayList：

ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>();

与经典数组类比，我想对该矩阵的“列”进行排序：我想在子 ArrayLists 中获取具有相同索引的项目，然后对它们进行排序。就像为每一列调用 Collections.sort() ... 我所说的行是指外层和内层是列。

这样做的正确方法是什么？我想过迭代矩阵以反转它，然后使用 Collections.sort() 对每一行进行排序？但也许这不是最好的解决方案，因为矩阵大约是 400*7000 。

我不能使用经典数组，因为矩阵的大小是未知的。

感谢帮助。

4

7 回答 7

3

做这样的事情：

    final int COLUMN = 5;
    Comparator<ArrayList<Double>> myComparator = new Comparator<ArrayList<Double>>() {
        @Override
        public int compare(ArrayList<Double> o1, ArrayList<Double> o2) {
            return o1.get(COLUMN).compareTo(o2.get(COLUMN));
        }
    };
    Collections.sort(list, myComparator);

将 COLUMN 设置为您要排序的任何列。

更新：

是的，这根本行不通。

我喜欢 ahanin 的第二个建议，即制作你自己的 List 来包装你的原始 List。您还必须包装 get() 返回的对象，以便变量 WrappedList 包含列值，并且 WrappedList.get(0) 也返回一列值。然后排序就可以工作了。我想知道您必须为 Collections.sort() 实施哪些最少的方法才能在您的列表上工作。

仅采用其他人的快速排序并使其与您的列表一起使用可能是最简单的。

这是一种实现：http ://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html

于 2012-04-05T20:43:34.257 回答
3

所以这里有一个类似于反转想法的选项，但不是反转整个事物，而是一次构建一列，对其进行排序并丢弃它。

ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

for(int c=0; c<data.get(0).size(); c++) {
    List<Double> col = new ArrayList<Double>();
    for( int r=0; r<data.size(); r++ )
        col.add( data.get(r).get(c) );

    Collections.sort(col);

    for( int r=0; r<col.size(); r++ )
        data.get(r).set( c, col.get(r) );
}

我怀疑您是否能够获得任何更有效的东西，除了可以选择创建自己的类，该类提供表中列的视图作为列表。

于 2012-04-05T21:11:29.620 回答
2

我有两个疯狂的想法：要么实现你自己的排序算法，它会知道你的倒置矩阵结构，要么编写一个 Collection 的实现来包装你的结构并表示列，以后可以将其用作 Collections 的参数。种类（）。使用 ArrayList 这应该相当快。

于 2012-04-05T20:29:32.180 回答
2

这是一种将数据转换为对象数组的方法。将列更改为您喜欢的任何内容。

final int column = 3;
ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

// Convert data into an object array
Object [] temp = data.toArray();

Arrays.sort(temp, new Comparator<Object>() {
    @Override
    public int compare(Object o1, Object o2) {
        // Get inner arrays to be compared by type-casting
        ArrayList<Double> temp1 = (ArrayList<Double>) o1;
        ArrayList<Double> temp2 = (ArrayList<Double>) o2;

        // Then compare those inner arrays' indexes
        return temp1.get(column).compareTo(temp2.get(column));
    }
});

// Clear the old one and add the ordered list into
data.clear();

for(Object o: temp)
{
    data.add((ArrayList<Double>) o);
}
于 2012-10-12T17:33:25.360 回答
0

我想如果存储不是问题，您可以在 ArrayList 中使用 SortedMap。这样您就不必担心对元素进行排序。

ArrayList<SortedMap<Double,byte>> data;
于 2012-04-05T20:42:10.653 回答
0

不确定我是否正确理解了您的 Q，但这将对所有“列”进行排序（假设外层是行，内层是列）：

    final ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 
    //...

    final Integer[] rows = new Integer[data.size()];
    for(int i=0;i<rows.length;i++)
        rows[i]=i;

    int cols = data.get(0).size();
    for(int c=0;c<cols;c++)
    {
        final int colidx = c;
        Arrays.sort(rows,new Comparator<Integer>(){
            @Override
            public int compare(Integer arg0,
                    Integer arg1) {
                return data.get(arg0).get(colidx).compareTo(data.get(arg1).get(colidx));        
            }});    

        for(int i=0;i<rows.length;i++)
            data.get(i).add(colidx+1,data.get(rows[i]).get(colidx));
        for(int i=0;i<rows.length;i++)
            data.get(i).remove(colidx);
    }
于 2012-04-05T20:59:36.963 回答
0

在任何情况下，您都必须访问所有元素才能对它们进行排序。所以你能做的就是这个。

int temp[] = new temp[col.length];
int x = 0;
while(x < row.length)
{
    for(int i = 0; i<col.length; i++)
    {
        temp[i] = mat[x][i];
    }
    sort(temp);
    for(int i = 0; i<col.length; i++)
    {
        mat[x][i] = temp[i];
    }
x++;
}

这里的运行时间是O(n^2logn)，但由于您只对 400 个双打进行排序，因此不会花费太多时间。并且由于您必须至少访问矩阵中的每个元素一次，因此您不能低于O(n^2)

于 2012-04-05T21:45:38.493 回答