给定以下二维数组：
6 8 11 17
9 11 14 20
18 20 23 29
24 26 29 35
每一行和每一列都被排序，对角线也被排序（从左上到右下）。假设我们在数组中有 n² 个元素（n = 4在这种情况下），使用快速O(n² log(n²)) = O(n² log(n))排序对二维数组进行排序是微不足道的。我的问题是我们可以把它分类O(n²)吗？
目标是使用给定的半排序二维数组并提出一个聪明的解决方案。
目标输出是：
6 8 9 11
11 14 17 18
20 20 23 24
26 29 29 35
是的，我们可以在O(n^2)时间内对此进行排序。
简化为一维数组排序
首先让我们证明，这个对 2D 数组进行排序的新问题（使得每行、每列和从左上到右下对角线都排序）可以简化为对n^2的 1D 数组进行排序的问题的 1D 数组进行排序的问题元素。
假设我们有一个由n^2元素组成的已排序一维数组。我们可以通过将前n个数字设置为第一行，然后将接下来的n 个数字设置为第二行，将其重新排列为排序的nxn数组，然后重复直到耗尽数组。
因此，给定一个包含n^2 个数字的 2D 数组，我们可以在O(n^2)时间内将其转换为 1D 数组，对该数组进行排序，然后在O(n^2)时间内将其转换回所需的 2D 数组。因此，如果我们能在O(n^2)时间内找到一维数组的排序算法，我们就可以在O(n^2)时间内等效地解决这个新问题。
在线性时间内对一维数组进行排序
鉴于此，我们只需要提供线性时间排序。即给定n^2 个元素，在O(n^2)时间内对它们进行排序。方便的是，您可以使用多种算法来完成此操作，例如计数排序或基数排序，尽管它们确实有各种警告。然而，假设给定要排序的项目数量的数值范围合理，这些排序将以线性时间运行。
因此，给定nxn数组中的n^2 个元素，这个 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的n 个已排序数组开始，然后从那里开始合并。这将我们必须合并的层数减半，并为我们提供了O(n^2 log_2(n))的最终运行时间。
结论
实际上，这些附加信息可以加快比较排序的速度，从而使我们能够实现O(n^2 log_2(n))运行时间。
但为了实现在O(n^2)时间内运行的线性时间排序，我们必须依赖计数或基数排序等算法。