在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

您可以排序为普通数组。
E.g.

#include <stdio.h> 
#include <stdlib.h> 


int cmp(const void *a, const void *b){ 
    return *(int*)a - *(int*)b; 
} 

#define ROW_SIZE 3 
#define COL_SIZE 4 

int main(void){ 
    int M[ROW_SIZE][COL_SIZE]={{3,5,7,1},{4,9,2,0},{9,3,6,2}}; 
    int c,r,*p; 

    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){ 
     for(c=0;c<COL_SIZE;++c){ 
      printf("%d ",*p++); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
    qsort(&M[0][0], ROW_SIZE*COL_SIZE, sizeof(int), cmp); 
    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){ 
     for(c=0;c<COL_SIZE;++c){ 
      printf("%d ",*p++); 
     } 
     printf("\n"); 
    } 

    return 0; 
} 

Answer 2

不知道你是怎么实际上是由双维数组的意思，但也有具体的，可以达到Ø某些情况下的排序算法（N ）。一个例子是Counting sort，如果你想排序一个1000到1000的整数的数组，它可以用O（n）排序。

编辑：它是一个多维数组这一事实不会改变排序的逻辑。您可以将指数（该分开使用）转换为二维指数是这样的：

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

其中N是第一个维度的大小。