如何將n個排序列表中的平均長度K排序爲O（n * log K）時間？

Question

如何排序n個排序列表，其平均長度K在O（n * log K）時間？

Answer 1

正如在你的問題的評論中所提到的，O（nlog（k））是不可能的，但這裏有幾個關於this page的算法可以有效地完成你的任務;這裏是一個：

取每個列表中的第一個元素 並創建一個堆（大小爲k）。彈出 最小的元素。從 查找數組元素來（假設它來自列表編號我 ）。從列表i中取下一個 元素，並將其推入 堆。對於 合併列表中的每個元素，我們花費了log（k）時間。所以 的時間複雜度是O（N * logk）其中 N是 中所有K列表中元素的總數。

-written由：Abhishek Goyal

Answer 2

您可以調整合並排序來完成這項工作。合併排序利用將已排序的列表合併成新的排序列表的便利。

Answer 3

合併排序是關鍵。讓假設N是元件的總數是統一和K容器的含有它們的數量：你在追加單個載體的所有已排序的序列，但其中記住你所附他們

• 。更好的辦法是，如果你按照它們的第一個元素的值排序，它們會加速下一段。

• 然後你合併排序的序列對（std :: inplace_merge，如果你使用C++）。每一次合併都是Na + Nb，所以每一步都是N.你必須執行logK步驟。

因此NlogK。

Answer 4

我相信有可能實現O（N * log（K）），但不是在最壞的情況下。

考慮排序這些列表：

{0,1,2,3,4,5,6,7,8,9,10}, 
{10,11,12,13,14,15,16,17,18,19,20}, 
{20,21,22,23,24,25,26,27,28,29,30} 

我的人的大腦可以很容易地不讀每一個值的列表進行排序，所以應該有一個算法，可以做同樣的。我們需要合併，同時使用修改的二進制搜索來查找值的範圍。

在最壞的情況下，你得到O（N * K），因爲每個值都必須進行比較。例如：

{0,2,4,6,8}, 
{1,3,5,7,9} 

這是我在圍棋的解決方案，如果我知道的有序列表我只會用通常是相對較小的K重疊區域：

// variation of binary search that finds largest 
// value up to and including max 
func findNext(a []int, imin int, vmax int) int { 
    imax := len(a) - 1 
    best := -1 
    for imin <= imax { 
     imid := imin + ((imax - imin)/2) 
     if a[imid] == vmax { 
      return imid 
     } else if a[imid] < vmax { 
      best = imid 
      imin = imid + 1 
     } else { 
      imax = imid - 1 
     } 
    } 
    return best 
} 

func sortNSortedLists(in [][]int) []int { 
    var out []int 
    cursors := make([]int, len(in)) 
    for { 
     // Find the array indices that have the smallest 
     // and next to smallest value (may be same) at 
     // their current cursor. 
     minIdx1 := -1 
     minIdx2 := -1 
     minVal1 := math.MaxInt32 
     minVal2 := math.MaxInt32 
     for i, cursor := range cursors { 
      if cursor >= len(in[i]) { 
       continue 
      } 
      if in[i][cursor] < minVal1 { 
       minIdx2 = minIdx1 
       minVal2 = minVal1 
       minIdx1 = i 
       minVal1 = in[i][cursor] 
      } else if in[i][cursor] < minVal2 { 
       minIdx2 = i 
       minVal2 = in[i][cursor] 
      } 
     } 
     if minIdx1 == -1 { 
      // no values 
      break 
     } 
     if minIdx2 == -1 { 
      // only one array has values, so append the 
      // remainder of it to output 
      out = append(out, in[minIdx1][cursors[minIdx1]:]...) 
      break 
     } 

     // If inVal1 is smaller than inVal2, 
     // append to output all values from minVal1 to minVal2 found in 
     // the minIdx1 array, and update the cursor for the minIdx1 array. 
     if minVal1 < minVal2 { 
      firstCursor := cursors[minIdx1] 
      lastCursor := findNext(in[minIdx1], firstCursor, minVal2) 
      if lastCursor != -1 { 
       out = append(out, in[minIdx1][firstCursor:lastCursor+1]...) 
       cursors[minIdx1] = lastCursor+1 
       continue 
      } 
     } 
     // Append the single value to output 
     out = append(out, minVal1) 
     cursors[minIdx1]++ 
    } 
    return out 
}