3

我不确定标题是否正确地暗示了我要问的问题。假设我有一个二维 int 数组，如下所示：

int[][] x={{1,7,6},{2,4,8}};

现在我想对第一行进行升序排序，第二行的数据排序后必须在同一列，即排序后的数组应该是这样的：

x={{1,6,7},{2,8,4}}

正确的方法是什么？

4

6 回答 6

3

这可以通过实现您自己的排序例程来完成，但更好的方法是重构。

尝试将数据封装为一组数字对，每对数字都包含在自己的对象中。然后，您可以对第一个值进行排序并访问任一值。

class Pair<T extends Comparable<T>> implements Comparable<Pair<T>> {
  final T a;
  final T b;

  public Pair ( T a, T b ) {
    this.a = a;
    this.b = b;
  }

  @Override
  public int compareTo(Pair<T> o) {
    // Comparison on 'a' only.
    return a.compareTo(o.a);
  }

  @Override
  public String toString () {
    return "{" + a + "," + b + "}";
  }
}

public static void main(String args[]) {
  Pair[] pairs = {
    new Pair(1,2),
    new Pair(7,4),
    new Pair(6,8),
  };
  System.out.println("Before: "+Arrays.toString(pairs));
  Arrays.sort(pairs);
  System.out.println("After: "+Arrays.toString(pairs));
}

印刷

Before: [{1,2}, {7,4}, {6,8}]
After: [{1,2}, {6,8}, {7,4}]
于 2012-12-12T13:38:51.537 回答
3

这可以通过实现您自己的排序算法并在第二行中移动值来完成。

您可能有一个对象数组。每个对象都将保留值。然后实现您的自定义比较器并使用排序功能。

我还有一个想法：重新排列数组（如果可以的话）。然后将对保存在一个 int[] 表中。外部表是 int 表的容器：

int [][] a = {{2,5},{1,4},{3,6}};
Arrays.sort(a, new Comparator<int[]>() {
        @Override
        public int compare(int[] p_o1, int[] p_o2) {
            return Integer.valueOf(p_o1[0]).compareTo(p_o2[0]);
        }
});
于 2012-12-12T13:41:51.443 回答
1

最简单的方法是创建一个Pair包含对的对象，并使用仅比较 Pair 的第一项的自定义比较器对 Pair 的集合进行排序。

如果需要，您始终可以将您的 Pairs 转换回 2D 数组。

这可能不是最有效的方法，但对于大多数用例来说应该足够好。

于 2012-12-12T13:39:27.270 回答
0

如果第一行的所有元素都是唯一且非空的，您可以在排序之前填充一个映射，其中第一行元素指向它们的第二行对应元素。对第一行进行排序后，您可以使用地图查找第一行（已排序）与第二行的对应元素。

于 2012-12-12T13:43:02.273 回答
0

你基本上是在做一个Map，你为什么不使用一个Map实现来帮助你呢？

TreeMapimplements SortedMap，因此一个简单的解决方案是将所有映射值放入其中：

SortedMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(1, 2);
map.put(7, 4);
map.put(6, 8);

// You can iterate over map now, it'll be already sorted
for(Map.Entry<Integer, Integer> entry: map.entrySet())
{
    System.out.println(entry.getKey()+" : "+entry.getValue());
}

// This is not really necessary
Integer[][] x = {map.keySet().toArray(new Integer[0]), map.values().toArray(new Integer[0])};

// If you have Apache Commons you can:
int[][] y = {ArrayUtils.toPrimitive(map.keySet().toArray(new Integer[0])), ArrayUtils.toPrimitive(map.values().toArray(new Integer[0]))};
于 2012-12-12T13:51:24.887 回答
0

我从http://www.algolist.net/Algorithms/Sorting/Quicksort复制粘贴的 qSort 并稍作修改

    public static void main(String[] args) throws Exception {
        int[][] x = { { 1, 7, 6 }, { 2, 4, 8 } };
        qsort(x[0], x[1], 0, x[0].length - 1);
        System.out.println(Arrays.deepToString(x));
    }

    static void qsort(int[] x0, int[] x1, int left, int right) {
        int index = partition(x0, x1, left, right);
        if (left < index - 1)
            qsort(x0, x1, left, index - 1);
        if (index < right)
            qsort(x0, x1, index, right);
    }

    static int partition(int[] x0, int[] x1, int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = x0[(left + right) / 2];
        while (i <= j) {
            while (x0[i] < pivot)
                i++;
            while (x0[j] > pivot)
                j--;
            if (i <= j) {
                tmp = x0[i];
                x0[i] = x0[j];
                x0[j] = tmp;

                // swap x1 too
                tmp = x1[i];
                x1[i] = x1[j];
                x1[j] = tmp;

                i++;
                j--;
            }
        }
        return i;
    }
}

这个程序打印

[[1, 6, 7], [2, 8, 4]]

这可能看起来很长，但通常对于算法效率是至关重要的，而且这个解决方案似乎是最快的

于 2012-12-12T13:57:26.887 回答