Да, мы можем отсортировать это за O (n ^ 2) время.
Сведение к сортировке 1D-массива
Давайте сначала покажите, что эта новая проблема сортировки 2D-массива (такая, что сортируются каждая строка, столбец и диагональ от верхнего левого угла к нижнему правому) может быть сведена к проблеме сортировки одномерного массива n ^ 2 элементов.
Предположим, у нас есть отсортированный одномерный массив из n ^ 2 элементов. Мы можем тривиально преобразовать это в отсортированный массив nxn , установив первые n числа в качестве первой строки, а затем следующие n числа в качестве второй строки , и повторяйте, пока мы не исчерпаем массив.
Следовательно, учитывая 2D-массив из n ^ 2 чисел, мы можем преобразовать его в 1D-массив в O (n ^ 2 ) time, отсортируйте этот массив, затем преобразуйте его обратно в желаемый 2D-массив за O (n ^ 2) time. Таким образом, если мы сможем найти алгоритм сортировки для одномерного массива за O (n ^ 2) , мы сможем эквивалентно решить эту новую проблему за O (n ^ 2) времени.
Сортировка одномерного массива за линейное время
Учитывая это, нам просто нужно обеспечить линейную временную сортировку. т.е. с учетом n ^ 2 элементов, отсортируйте их за O (n ^ 2) время. Для удобства есть несколько алгоритмов, которые вы можете использовать для выполнения sh этого, например сортировка с подсчетом или сортировка по основанию , хотя они имеют различные оговорки. Однако, предполагая разумный диапазон числовых значений с учетом количества элементов для сортировки, эти сортировки будут выполняться за линейное время.
Таким образом, учитывая n ^ 2 элементов в nxn массив, эта задача 2D-сортировки может быть уменьшена за O (n ^ 2) времени до задачи 1D-сортировки, которая затем может быть решена с помощью различных алгоритмов линейной сортировки по времени в O (n ^ 2) время. Следовательно, в целом эта проблема может быть решена за O (n ^ 2) время.
Сортировка со сравнительной сортировкой
После обсуждения в комментариях следующий шаг - спросить: а как насчет сортировок по сравнению. Сортировки сравнения полезны, потому что они позволят нам избежать ранее упомянутых предостережений относительно подсчета и сортировки по основанию.
Однако даже с этой дополнительной информацией сортировка линейного сравнения по времени маловероятна на практике, потому что для этого потребуется для вычисления окончательной позиции каждого числа за O (1) время. Мы знаем, что это невозможно с помощью сравнительной сортировки.
Давайте рассмотрим небольшой пример: какой должна быть окончательная отсортированная позиция числа в строке 1, столбце 2? Мы знаем, что это должно быть первое из чисел в столбцах 2 ... n. Однако мы не знаем, где он находится относительно чисел в столбце 1 (кроме числа в строке 1, столбце 1).
В общем, для любого числа в исходном квадрате мы не уверены его окончательной отсортированной позиции относительно всех чисел в нижнем левом углу и чисел в правом верхнем углу. Потребуется O (log_2 (n)) сравнений, чтобы найти относительное положение каждого числа, и есть O (n ^ 2) чисел для размещения. Эта неопределенность не позволяет нам достичь линейной временной сортировки на практике.
Но дополнительная информация, которая у нас есть, должна позволить нам добиться некоторого ускорения. Например, мы могли бы приспособить к этой проблеме сортировку слиянием . При стандартной сортировке слиянием мы начинаем с разделения нашего исходного массива пополам и повторяем, пока не получим массивы размера 1, которые гарантированно будут отсортированы, затем мы многократно объединяем эти подмассивы, пока не получим один единственный массив. Для элементов n ^ 2 мы должны создать двоичное дерево со слоями log_2 (n ^ 2) , и каждый слой занимает O (n ^ 2) время для слияния.
Используя дополнительную информацию в настройках вашей задачи, нам не нужно разделять массивы, пока они не достигнут размера 1. Вместо этого мы можем начать с n sorted массивы длиной n и начиная с них объединяться. Это вдвое сокращает количество слоев, которые мы должны объединить, и дает нам окончательное время выполнения O (n ^ 2 log_2 (n)) .
Заключение
На практике эта дополнительная информация позволяет немного ускорить сортировку сравнений, позволяя достичь O (n ^ 2 log_2 (n)) времени выполнения.
Но для того, чтобы для достижения линейной сортировки по времени, которая выполняется за O (n ^ 2) время, мы должны полагаться на такие алгоритмы, как подсчет или сортировка по основанию.