<p>即使<a href="https://stackoverflow.com/a/62791654/913098">@Gulzar's solution</a>是正确的,它实际上并没有给我们<code>O(n + k * log k)</code>。
问题出在<code>sort_nk_unsorted_list</code>函数中。不幸的是,从Python列表中删除任意项不是固定时间<a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow noreferrer">It's actually ^{<cd3>}</a>。这使得整个算法的复杂度为<code>O(n + nk + k * log k)</code></p>
<p>要解决这个问题,我们可以使用不同的数据结构。如果使用双链接列表,则从该列表中删除项目实际上是<code>O(1)</code>。不幸的是,Python在默认情况下没有附带一个</p>
<p>这是我的解决方案,它实现了<code>O(n + k * log k)</code></p>
<p>解决问题的入口点函数:</p>
<pre class="lang-py prettyprint-override"><code>def sort(my_list):
in_order, out_of_order = separate_in_order_from_out_of_order(my_list)
out_of_order.sort()
return merge(in_order, out_of_order)
</code></pre>
<p>将有序元素与无序元素分开的函数:</p>
<pre class="lang-py prettyprint-override"><code>def separate_in_order_from_out_of_order(my_list):
list_dll = DoublyLinkedList.from_list(my_list)
out_of_order = []
current = list_dll.head
while current.next is not None:
if current.value > current.next.value:
out_of_order.append(current.value)
out_of_order.append(current.next.value)
previous = current.prev
current.next.remove()
current.remove()
current = previous
else:
current = current.next
in_order = list_dll.to_list()
return in_order, out_of_order
</code></pre>
<p>合并两个单独列表的函数:</p>
<pre class="lang-py prettyprint-override"><code>def merge(first, second):
"""
Merges two [sorted] lists into a sorted list.
Runtime complexity: O(n)
Space complexity: O(n)
"""
i, j = 0, 0
result = []
while i < len(first) and j < len(second):
if first[i] < second[j]:
result.append(first[i])
i += 1
else:
result.append(second[j])
j += 1
result.extend(first[i:len(first)])
result.extend(second[j:len(second)])
return result
</code></pre>
<p>最后,这是DoublyLinkedList实现(我使用了sentinel节点使事情变得更简单):</p>
<pre class="lang-py prettyprint-override"><code>class DoublyLinkedNode:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def remove(self):
if self.prev:
self.prev.next = self.next
if self.next:
self.next.prev = self.prev
class DoublyLinkedList:
def __init__(self, head):
self.head = head
@staticmethod
def from_list(lst):
sentinel = DoublyLinkedNode(-math.inf)
previous = sentinel
for item in lst:
node = DoublyLinkedNode(item)
node.prev = previous
previous.next = node
previous = node
return DoublyLinkedList(sentinel)
def to_list(self):
result = []
current = self.head.next
while current is not None:
result.append(current.value)
current = current.next
return result
</code></pre>
<p>以下是我用来验证代码的单元测试:</p>
<pre class="lang-py prettyprint-override"><code>import unittest
class TestSort(unittest.TestCase):
def test_sort(self):
test_cases = [
# ( input, expected result)
([1, 2, 3, 4, 10, 5, 6], [1, 2, 3, 4, 5, 6, 10]),
([1, 2, 5, 4, 10, 6, 0], [0, 1, 2, 4, 5, 6, 10]),
([1], [1]),
([1, 3, 2], [1, 2, 3]),
([], [])
]
for (test_input, expected) in test_cases:
result = sort(test_input)
self.assertEqual(expected, result)
</code></pre>