How to Sort a 2D array?

问题:

I need help with sorting 2D array. I've got array with two rows

[5, 3, 4, 1, 2]
[10,20,30,40,50]

and I need to sort it to look like this:

[1, 2, 3, 4, 5]
[40,50,20,30,10]

I know how to do that with bubble sort, but I need some faster algorithm, e.g. quicksort.

Here is my bubble sort code

   for (int i = 0; i < length-1; i++) {
         for (int j = 0; j < length-i-1; j++) { 

            if (array[0][j] > array[0][j+1]) {

               for (int k = 0; k < 2; k++) {
               int tmp = array[k][j];
               array[k][j] = array[k][j+1];
               array[k][j+1]=tmp;
               }
           }
       }
    }

回答1:

transpose the 2D array java multi-dimensional array transposing

use Arrays.sort(T[] a, Comparator<? super T> c) where the comparator compares on index 0 of each row

transpose the result again:

e.g.

from: [5,3,4,1,2] [10,20,30,40,50]

obtain [5, 10] [3, 20] [4, 30] [1, 40] [2, 50]

then sort them to [1, 40] [2, 50] [3, 20] [4, 30] [5, 10]

then transpose again to: [1,2,3,4,5] [40,50,20,30,10]

or implement quicksort by yourself.

回答2:

Edit (after OP changed formulations):

You may collect that all to Map and then sort it by keys. Collecting to Map is O(n) and you can get sorting for free using ordered Map implementation. Transposing looks more expensive to me

回答3:

Did you think about merge-sort-alorithm?

http://en.wikipedia.org/wiki/Merge_sort that should be the fastest in that case. (an abstract implementation is available in wiki too)

回答4:

You can use Comparator to do that. This thread has some useful information for C++ . Sample code in Java is like,

Arrays.sort(a, new Comparator<Long[]>() {

        @Override
        public int compare(Long[] o1, Long[] o2) {

            Long t1 = o1[1];
            Long p1 = o1[0];
            Long t2 = o2[1];
            Long p2 = o2[0];

            if (t1 == t2) {
                return (p1 > p2 ? 1 : (p1 == p2 ? 0 : -1));
            } else {
                return (t1 < t2 ? -1 : 1);
            }

        }
    });

Do your comparison login in compare method and return the relevant values to sort the array accordingly.