Как эффективно отсортировать многомерный массив - PullRequest
Новая
       13

Как эффективно отсортировать многомерный массив

1 голос
/ 22 апреля 2019

Мне было дано задание отсортировать многомерный массив в порядке возрастания без использования готовых функций в классе Array (например, .sort).

Я пытался спросить идеи у некоторых моих друзей... Многие из них превращают массив в одномерный массив, сортируют его так, как вы бы отсортировали одномерный массив, а затем превращаете его обратно в многомерный массив.

Мне просто интереснознать, есть ли другие способы сделать это без необходимости проходить через такие неприятности.

Ответы [ 3 ]

0 голосов
/ 22 апреля 2019

сортировка многомерного массива в порядке возрастания:

Вы можете сортировать массив multi-d по строкам или столбцам.

Если вы не хотитеВыровняйте массив, который преобразует его в 1-й, тогда это означает, что вам придется проходить каждую строку или столбец в зависимости от вашего выбора и применять быструю сортировку (лучшую производительность для небольшого набора данных, если оптимально выбран сводный) или сортировку слиянием.

Таким образом, вы можете сделать оба в (с учетом среднего случая) O(nlogn) и сказать, что есть n строк или n столбцов, сложность времени будет O(n^2(logn)).

Теперь выше предположениячто вы хотите сортировать либо по строкам, либо по столбцам.Если вы хотите получить оба (строку и столбец), то лучше преобразовать массив в 1-й, а затем применить сортировку и затем преобразовать ее обратно.В противном случае, следуя вышеприведенному подходу, временная сложность может пойти O(n^2(logn)), но в другом случае она будет O((n+m)log(n+m)), где n amd m - нет.строк и столбцов в массиве плюс O(n+m) сложность пространства.

По моему мнению, иметь немного пространственной сложности, чтобы вы могли сократить время выполнения, предпочтительнее.

0 голосов
/ 30 апреля 2019

Я нашел решение ... Спасибо всем

public static void sortAscending (int array [] []) {

    int temp = 0;

    for(int i = 0; i < array.length; i++) {
        for(int j = 0; j < array[i].length; j++) {
            for(int k = 0; k < array.length; k++) {
                for(int l = 0; l < array[k].length; l++) {
                    if(array[i][j] < array[k][l]) {
                        temp = array[i][j];
                        array[i][j] = array[k][l];
                        array[k][l] = temp;
                    }
                }
            }
        }
    }
}
0 голосов
/ 22 апреля 2019

вот полный пример, вы можете три 

import java.util.Arrays;
import java.util.Comparator;

public class PartNumberQuantityDetailer {
// initialize a two dimensional array
static Integer[][] itemIdAndQty = new Integer[5][2];

public static void main(String[] args) {
    // initialize array values
    itemIdAndQty[0][0] = 1234;
    itemIdAndQty[0][1] = 46;
    itemIdAndQty[1][0] = 5443;
    itemIdAndQty[1][1] = 564;
    itemIdAndQty[2][0] = 362;
    itemIdAndQty[2][1] = 24;
    itemIdAndQty[3][0] = 6742;
    itemIdAndQty[3][1] = 825;
    itemIdAndQty[4][0] = 347;
    itemIdAndQty[4][1] = 549;
    System.out.println("Before sorting");
    // show the contents of array
    displayArray();
    // sort the array on item id(first column)
    Arrays.sort(itemIdAndQty, new Comparator<Integer[]>() {
        @Override
                    //arguments to this method represent the arrays to be sorted   
        public int compare(Integer[] o1, Integer[] o2) {
                            //get the item ids which are at index 0 of the array
            Integer itemIdOne = o1[0];
            Integer itemIdTwo = o2[0];
            // sort on item id
            return itemIdOne.compareTo(itemIdTwo);
        }
    });
    // display array after sort
    System.out.println("After sorting on item id in ascending order");
    displayArray();
    // sort array on quantity(second column)
    Arrays.sort(itemIdAndQty, new Comparator<Integer[]>() {
        @Override
        public int compare(Integer[] o1, Integer[] o2) {
            Integer quantityOne = o1[1];
            Integer quantityTwo = o2[1];
            // reverse sort on quantity
            return quantityOne.compareTo(quantityTwo);
        }
    });
    // display array after sort
    System.out.println("After sorting on quantity in ascending order");
    displayArray();

}

private static void displayArray() {
    System.out.println("-------------------------------------");
    System.out.println("Item id\t\tQuantity");
    for (int i = 0; i < itemIdAndQty.length; i++) {
        Integer[] itemRecord = itemIdAndQty[i];
        System.out.println(itemRecord[0] + "\t\t" + itemRecord[1]);
    }
    System.out.println("-------------------------------------");
}

}]

...