最有效的方法来排序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++; 
    }