将列表分为 k 个部分的排序树 python

Question

我了解如何使用二叉树对列表进行排序。例如。将 [ 1,3,5,6,7,3,4,2] 从小到大排序。我每次递归地将数据分成2部分，直到变成n个列表。然后我一次比较 2 个列表并将较小的值附加到新列表中。当需要我每次将列表拆分为 k 个部分时，我不明白如何执行此操作。例如。 k=3。 [1,3,5] [6,7,3] [4,2] 。我只能在 Java 中找到解决方案所以有人可以使用 python 向我解释一下吗？

Answer 1

您有 k 个子列表。在每次迭代中，找到第一个元素最小的子列表；将该元素附加到结果列表；在该子列表中推进一个，在其他子列表中不推进。

如果您有函数 arg_min 或 min_with_index 可以提供最小元素及其索引（因此您知道它来自哪个子列表），这会更容易。

这里有两种等效的写函数 min_with_index 的方法，使用 python 的内置函数 min 获取最小值，并使用 enumerate 获取索引：

def min_with_index(it):
  return min(enumerate(it), key=lambda p:p[1])

import operator
def min_with_index(it):
  return min(enumerate(it), key=operator.itemgetter(1))

# >>> min_with_index([14,16,13,15])
# (2, 13)

这是为了合并。这里有两种不同的拆分方式，使用列表切片：

def split_kway_1(l, k):
  return [l[i::k] for i in range(k)]

def split_kway_2(l, k):
  j = (len(l)-1) // k + 1
  return [l[i:i+j] for i in range(0,len(l),j)]

def split_kway_3(l, k):
  j = len(l) // k
  result = [l[i:i+j] for i in range(0, j*(k-1), j)]
  result.append(l[j*(k-1):])
  return result

# >>> split_kway_1(list(range(10)), 3)
# [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]
# >>> split_kway_2(list(range(10)), 3)
# [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9]]
# >>> split_kway_3(list(range(10)), 3)
# [[0, 1, 2], [3, 4, 5], [6, 7, 8, 9]]

# versions 2 and 3 differ only when the length of the list is not a multiple of k

现在我们可以结合拆分和合并来写归并排序：

import operator

def split_kway(l, k):
  return [l[i::k] for i in range(k)]

def min_with_index(it):
  return min(enumerate(it), key=operator.itemgetter(1))

def merge_kway(list_of_sublists):
  result = []
  list_of_sublists = [l for l in list_of_sublists if len(l) > 0]
  while list_of_sublists:
    i,v = min_with_index(l[0] for l in list_of_sublists)
    result.append(v)
    if len(list_of_sublists[i]) > 1:
      list_of_sublists[i].pop(0) # advance in sublist i
    else:
      list_of_sublists.pop(i)    # remove sublist i which is now empty
  return result

def merge_sort_kway(l, k):
  if len(l) > 1:
    list_of_sublists = split_kway(l, k)
    list_of_sublists = [merge_sort_kway(l, k) for l in list_of_sublists]
    return merge_kway(list_of_sublists)
  else:
    return list(l)

另请参阅：Wikipedia on k-way merge

将列表分为 k 个部分的排序树 python

Sort tree which divides list into k parts python

python

sorting

merge

binary-tree