在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是第一個維度的大小。