最有效的方法來排序2d數組排序到1d排序數組

Question

給定一個2行數組（矩陣）與N行和K列，與它的行排序，列未指定，什麼是最有效的算法來排序它？

對於〔實施例：

Input (n = 3 ; k = 4): 
1 5 8 10 
3 4 5 6 
2 3 3 9 

Output: 
1 2 3 3 3 4 5 5 6 8 9 10 

這是純粹的算法問題，所以有些語言沒有具體的.sort（）方法，幫助我，因爲我在運行復雜性實際上intereseted。

我腦子裏想的是什麼將是一個算法如下：

- Build a Binary Search tree with n nodes. Each node contains: 
    ID - of the row it refers to; 
    Value - The number at the "head" of the row. 
- Sort the tree where the sorting key are the values. 
- Find the lowest valued node. 
- Do while the tree has a root: 
    - Take the lowest value and append it to the new array. 
    - Update the node's value to the next one in the same row. 
    - If the updated value is null, delete that node. 
    - else re-sort the tree. 
    - If the node moved, the first node it swapped with will be the next lowest 
    - else, if it didn't move, it's the new lowest. 

如果我沒有記錯的運行時間複雜度爲O(n*k * log n)，由於我選樹n*k倍，這需要時間O(log n)，並找到下一個最低的過程是O(1)。

如果我的複雜度計算錯誤，請告訴我。

有沒有比這更高效的方法？

Answer 1

您基本上有n排序的列表，每個大小爲k。您需要推廣merge-sort，這是k路合併。

想法是保留一個min-heap，它包含每個列表中最小的元素。

現在，迭代地彈出堆的最小值。讓這個數字是x，並且說它是從第i行取得的。現在，將x附加到結果列表中，並將最小堆添加到行i中的下一個元素（如果存在此元素）

重複，直到所有元素都耗盡。

複雜性是O(n*k*logn)，考慮到您正在排序n*k元素，並且需要遍歷所有元素，這非常高效。使用二進制堆的常量非常好。

請注意，這通常被認爲是external sort（或確切地說是與外部排序的第二部分緊密相關的變體）。

這與您建議的算法非常相似，但由於使用堆而不是效率較低的樹，可能運行得更快（具有更好的常量）。
另請注意，如果使用「常規」二叉樹，則複雜度爲O(n^2k)，因爲樹的高度無法保證。您需要一個self balancing binary search tree才能獲得O(nklogn)運行時間。

Answer 2

這可以通過使用Sorted Merge來完成，它將採用o（rows * cols）時間，即元素總數和o（行）空間複雜度。

針對此問題的Java代碼如下：（考慮行= 3和cols = 4）

for(int i=0;i<3;i++) 
    { 
     index[i] =0; 
    } 

    int count=0; 
    int a; 
    int b; 
    int c; 

    while(count<(ROWS*COLS)) 
    { 
     int smallest; 
     if(index[0]>=COLS) 
      a= Integer.MAX_VALUE; 
     else 
      a= matrix[0][index[0]]; 
     if(index[1]>=COLS) 
      b = Integer.MAX_VALUE; 
     else 
      b = matrix[1][index[1]]; 
     if(index[2]>=COLS) 
      c = Integer.MAX_VALUE; 
     else 
      c = matrix[2][index[2]]; 
     if(a<=b && a<=c){ 
      // a is smallest 
      smallest = a; 
      index[0] = index[0] +1; 

     }else if(b<=c && b<=a){ 
      //b is smallest 
      smallest = b; 
      index[1] = index[1] + 1; 
     }else{ 
      //c is smallest 
      smallest = c; 
      index[2] = index[2] + 1; 
     } 
     System.out.print(smallest + ", "); 
     count++; 
    }