Сортировка 2d-массива по последнему ряду с Arrays.sort

Question

Можно ли отсортировать 2d-массив по последней строке с помощью Arrays.sort (,) в Java.Следующий фрагмент отлично работает для сортировки по последнему столбцу, но, похоже, его нельзя отрегулировать для сортировки по последней строке.

Первой мыслью было использовать преобразование столбцов в строки, выполнить сортировку, а затемпреобразование строк в столбец.Есть ли лучший способ для очень больших массивов?

int[][] twoDim = { {1, 2, 3}, {3, 7, 11}, {8, 9, 16}, {4, 2,8}, {5, 3, 9} };
Arrays.sort(twoDim, new Comparator<int[]>() {
     @Override
     public int compare(int[] o1, int[] o2) {
         return ((Integer) o1[2]).compareTo(o2[2]);
     }
});

Давайте проясним ситуацию в целом: вот где я нахожусь, когда мой массив инициализируется и по строкам и столбцам вы можете представить этот набор данных следующим образом:

{1, 2, 3}, //first row with three columns<br> {3, 7, 11}, //second row with three columns<br> {8, 9, 16},<br> {4, 2, 8},<br> {5, 3, 9} //last row with three columns<br>

Сортировка по последнему ряду означает изменение положения первого и второго столбца, поскольку 5 больше 3. Поэтому после перестановки набора данных это выглядит следующим образом:
2, 1, 3<br> 7, 3, 11<br> 9, 8, 16<br> 2, 4, 8<br> 3, 5, 9 //now it's ordered by last row (first and second column have changed they position, by chance third column is in a right place already)

Answer 1

На этот вопрос нельзя ответить, если я правильно понимаю, что вы подразумеваете под столбцами и строками.

Если вы посмотрите на набор данных следующим образом:

1, 2, 3
3, 7, 11
8, 9, 16
4, 2, 8
5, 3, 9

Теперь, если вы отсортируете их поВ последнем ряду вы получите следующие результаты:

{2, 7, 9, 2, 3}, {1,3,8,4,5}, {3, 11, 16, 8, 9}

Очевидно, что этого не произойдет, если вы замените строку 4, 2, 8 на строку 5,3,9.Итак, вам нужно либо придумать стандартный порядок, либо найти другой способ решения вашей реальной проблемы, с которой вы столкнулись.

Если вы имеете дело с матрицами, я настоятельно рекомендую библиотека .

Answer 2

Помните, что двумерные массивы являются массивами массивов. Каждому алгоритму сортировки требуется средство для перемещения записей, которые вы хотите отсортировать. Ваше решение для сортировки по последнему столбцу работает, потому что Arrays.sort видит ваши внутренние массивы как объекты для сортировки. То, что вы называете сортировкой по последней строке, не имеет эквивалентного объекта, который должен представлять столбцы.

Итак, у вас есть два варианта:

1. Реализуйте собственный алгоритм сортировки, который заменяет сразу все столбцы, но, пожалуйста, используйте алгоритм учебника.

2. Транспонировать вашу матрицу. Но помните, что это может быть бесплатно, если возможно поменять значение первого и второго индекса во всей программе.

Answer 3

Интересный вопрос.

Я бы сделал это, применив вариант быстрая сортировка . Вариации по сути в функции partition:

• вы используете последнюю строку вашей матрицы в качестве сортируемого массива
• при замене двух элементов вы на самом деле меняете два столбца матрицы

Вот реализация:

public void qsortOnLastRow(int[][] matrix, int left, int right) {
    if (left < right) {
        int i = partition(matrix, left, right);
        qsortOnLastRow(matrix, left, i - 1);
        qsortOnLastRow(matrix, i + 1, right);
    }
}

public int partition(int[][] matrix, int left, int right) {
    int lastrow = matrix.length - 1;
    int pivotValue = matrix[lastrow][left];
    int i = left;
    for (int j = left + 1; j <= right; j++) {
        if (matrix[lastrow][j] <= pivotValue) {
            i++;
            swapColumns(matrix, i, j);
        }
    }
    swapColumns(matrix, left, i);
    return i;
}

public void swapColumns(int[][] matrix, int c0, int c1) {
    if (c0 != c1) {
        for (int i = 0; i < matrix.length; i++) {
            int t = matrix[i][c0];
            matrix[i][c0] = matrix[i][c1];
            matrix[i][c1] = t;
        }
    }
}

Вы можете отсортировать int[][] matrix, позвонив по номеру qsortOnLastRow(matrix, 0, matrix[0].length - 1);

Сложность, если я не ошибаюсь, должна быть O(m * n * log n), где m = количество строк и n = количество столбцов в вашей матрице.

Примечание : Вы можете использовать тот же трюк (сортировка по последнему ряду и замена столбцов) также с другими алгоритмами сортировки.