<p>你的列表在人眼看来可能是排序的。但是对于Python来说,您的输入并不是完全排序的,因为它按字典顺序对字符串进行排序。这意味着<code>'12'</code>按排序顺序在<code>'8'</code>之前,因为只比较前几个<em>字符</em>。在</p>
<p>因此,合并是完全正确的;在看到<code>'8.1'</code>字符串之后会遇到以<code>'12.1'</code>开头的字符串,但以<code>'8.1.1'</code>开头的字符串将在之后排序。在</p>
<p>必须使用键函数从字符串中提取<em>整数元组</em>才能正确排序:</p>
<pre><code>section = lambda s: [int(d) for d in s.partition(' ')[0].split('.') if d]
heapq.merge(sections, subsections, subsubsections, key=section))
</code></pre>
<p>请注意,<code>key</code>参数仅在python3.5及更高版本中可用;在早期版本中,您必须手动执行decorate merge undecorate dance。在</p>
<p>演示(使用Python3.6):</p>
^{pr2}$
<p>keyed merge很容易后移植到Python 3.3和3.4:</p>
<pre><code>import heapq
def _heappop_max(heap):
lastelt = heap.pop()
if heap:
returnitem = heap[0]
heap[0] = lastelt
heapq._siftup_max(heap, 0)
return returnitem
return lastelt
def _heapreplace_max(heap, item):
returnitem = heap[0]
heap[0] = item
heapq._siftup_max(heap, 0)
return returnitem
def merge(*iterables, key=None, reverse=False):
h = []
h_append = h.append
if reverse:
_heapify = heapq._heapify_max
_heappop = _heappop_max
_heapreplace = _heapreplace_max
direction = -1
else:
_heapify = heapify
_heappop = heappop
_heapreplace = heapreplace
direction = 1
if key is None:
for order, it in enumerate(map(iter, iterables)):
try:
next = it.__next__
h_append([next(), order * direction, next])
except StopIteration:
pass
_heapify(h)
while len(h) > 1:
try:
while True:
value, order, next = s = h[0]
yield value
s[0] = next() # raises StopIteration when exhausted
_heapreplace(h, s) # restore heap condition
except StopIteration:
_heappop(h) # remove empty iterator
if h:
# fast case when only a single iterator remains
value, order, next = h[0]
yield value
yield from next.__self__
return
for order, it in enumerate(map(iter, iterables)):
try:
next = it.__next__
value = next()
h_append([key(value), order * direction, value, next])
except StopIteration:
pass
_heapify(h)
while len(h) > 1:
try:
while True:
key_value, order, value, next = s = h[0]
yield value
value = next()
s[0] = key(value)
s[2] = value
_heapreplace(h, s)
except StopIteration:
_heappop(h)
if h:
key_value, order, value, next = h[0]
yield value
yield from next.__self__
</code></pre>
<p>装饰-排序-取消装饰合并非常简单:</p>
<pre><code>def decorate(iterable, key):
for elem in iterable:
yield key(elem), elem
sorted = [v for k, v in heapq.merge(
decorate(sections, section), decorate(subsections, section)
decorate(subsubsections, section))]
</code></pre>
<p>因为您的输入已经排序,所以使用合并排序更有效。最后,您可以使用<code>sorted()</code>但是:</p>
<pre><code>from itertools import chain
result = sorted(chain(sections, subsections, subsubsections), key=section)
</code></pre>