c - O(n) 时间内的双维数组排序

Question

我在面试中被问到一个问题，要求在 O(n) 时间内对双维数组进行排序。如何在 O(n) 时间内完成它。有人可以解释一下吗？谢谢。

输入:

3 5 7 1
4 9 2 0
9 3 6 2   

输出

0 1 2 2 
3 3 4 5  
6 7 9 9

Answer 1

不知道双维数组的实际含义是什么，但是有一些特定于某些情况的排序算法可以实现 O(n)。一个例子是 Counting sort ，如果要对一个包含 1 到 1000 范围内的 1000 个整数的数组进行排序，可以在 O(n) 内排序。

编辑:它是多维数组这一事实不会改变排序的逻辑。您可以将索引(通过排序使用)转换为二维索引，如下所示:

array[i / N][i % N];

其中 N 是第一维的大小。