сортировка двумерных массивов в C++

Question

сортировка двумерных массивов в C++

Предположим, что у меня есть 2-d массив a[4][2], как это:

Я хотел бы отсортировать массивы в этом массиве в порядке возрастания их вторых чисел, т. е. после сортировки, я хотел бы, чтобы массив был таким:

Я подумал о создании карты, которая хранит индексы чисел во вторых столбцах, а затем делает массив чисел во втором столбце и сортирует этот массив, а затем восстанавливает массив из нового порядка второго столбца и второго столбца. карта. Проблема, однако, заключается в том, что два числа во втором столбце могут не различаться, поэтому, если число i появляется дважды, map[i] будет хранить только его последний индекс. Кроме того, ручная проверка позиций первых чисел, соответствующих вторым числам, займет O (n^2) времени. Я хочу сделать это в O (N log n). У кого-нибудь есть предложения? Существует ли какой-либо встроенный метод для этого (C++ 4.3.2 / 4.8.1)?

Заранее благодарю.

918 2

c++multidimensional-array sorting

2 ответов:

Comments

Ничего не найдено.

Goz · Accepted Answer · 2014-12-02 12:00:45

Вы можете легко сделать это с помощьюstd::sort . Вам нужно будет поставить специальный компаратор, но это не проблема.

Его гораздо проще, если вы используете std:: array для определения вашего 2-мерного массива, хотя следующим образом:
std::array< std::array< int, 2 >, 4 > twoDArray;
Затем вы можете отсортировать его следующим образом:
std::sort( twoDArray.begin(), twoDArray.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
{
    return a[1] < b[1];
}
Сделать то же самое с массивом в стиле C все еще возможно, но потребуется реализация пользовательского итератора, который продвигает всю "строку" за один раз, как стандартный итератор (т. е. указатель) будет рассматривайте 2D массив, как если бы он был 1D.

Вот полный пример использования массивов C++:
std::array< std::array< int, 2 >, 4 > arr   = {{ { 1, 4 },
                                                 { 2, 3 },
                                                 { 3, 2 },
                                                 { 4, 1 } }};

std::sort( arr.begin(), arr.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
    {
        return a[0] < b[0];
    } );

std::sort( arr.begin(), arr.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
    {
        return a[1] < b[1];
    } );

Jakub Arnold · Accepted Answer · 2014-12-02 11:38:31

Вы можете отсортировать их один раз по первому элементу, а затем снова по второму столбцу. Это похоже на то, как будет работать сортировка radix.