MergeSort返回排序列表的头，因此主代码中的调用应该是：
在链表上运行时，只有一些输入的Merge Sort函数。如果我在输入列表中包括0，那么从最后的print((调用中只返回0。我不知道我做错了什么
class StackNode(object):
def __init__(self, data):
self.data = data
self.prev = None
class Stack(object):
def __init__(self):
self.head = None
self.count = 0
def push(self, data):
if (self.head == None):
self.head = StackNode(data)
self.count += 1
return
node = StackNode(data)
node.prev = self.head
self.head = node
self.count += 1
return
def pop(self):
node = self.head
self.head = self.head.prev
self.count -= 1
return node
def print(self):
node = self.head
if(node == None):
return
print(node.data)
while(node.prev):
node = node.prev
print(node.data)
def MergeSort(self, h):
if h == None or h.prev == None:
return h
middle = self.GetMiddle(h)
nextToMiddle = middle.prev
middle.prev = None
left = self.MergeSort(h)
right = self.MergeSort(nextToMiddle)
sortedList = self.SortedMerge(left, right)
return sortedList
def SortedMerge(self, a, b):
if a is None:
return b
if b is None:
return a
if(a.data > b.data):
result = a
a.prev = self.SortedMerge(a.prev, b)
else:
result = b
b.prev = self.SortedMerge(b.prev, a)
return result
def GetMiddle(self, head):
if head == None:
return head
slow = head
fast = head
while(fast.prev != None and fast.prev.prev != None):
slow = slow.prev
fast = fast.prev.prev
return slow
a = Stack()
a.push(2)
a.push(5)
a.push(1)
a.push(4)
a.push(3)
a.push(7)
a.print()
a.MergeSort(a.head)
print("after: ")
a.print()
我直接从geeksfoeks.com上给出的链表合并排序示例中转录了我的代码，唯一的区别是我的代码创建了一个堆栈，而不是一个队列
a.head = a.MergeSort(a.head)
对于排序的堆栈，执行连续list.pop((的结果似乎应该按数据顺序返回节点，但代码在比较中使用">"而不是"<="，颠倒了顺序。
Python 2.7抱怨使用类打印函数的名称打印，还抱怨在"def SortedMerge(self，a，b(："之前有5个(而不是4个(空格
SortedMerge((为合并的每个节点执行一级递归。对于较大的列表，程序将出现堆栈溢出。由于列表类包括一个计数，代码可以使用list.count//2来确定要前进到中点的节点数，然后使用(count//2(表示左半部分的大小，使用(count-(count//((表示右半部分的尺寸。自下而上的合并排序速度更快。然而，对于python，解释代码的开销太大了，我不知道它是否会有所不同。以下是一个链接列表的自上而下和自下而上合并排序的链接，在java中，它使用了一个通用的合并函数：
Singly Linked List的Merge Sort似乎可以删除任何大于我输入到列表中的最终数字的数字
我将代码转换为python。两个示例的merge函数相同。请注意，排序逻辑是相同的，只有push和pop函数会导致链表充当堆栈。合并功能：
def Merge(self, a, b):
if a is None:
return b
if b is None:
return a
r = StackNode(0) # dummy node
d = r
while(True):
if(a.data <= b.data):
d.prev = a
d = a
a = a.prev
if(a == None):
d.prev = b
break
else:
d.prev = b
d = b
b = b.prev
if(b == None):
d.prev = a
break
return r.prev
自上而下的示例：
def MergeSort(self):
if(self.count < 2):
return
self.head = self.MergeSortR(self.head, self.count)
def MergeSortR(self, h, n):
if(n < 2):
return h
n2 = n//2
t = self.Scan(h, n2-1)
m = t.prev
t.prev = None
h = self.MergeSortR(h, n2)
m = self.MergeSortR(m, n-n2)
h = self.Merge(h, m)
return h
def Scan(self, h, n):
while(n > 0):
h = h.prev
n = n-1
return h
自下而上的示例：
def MergeSort(self):
if(self.count < 2):
return
an = [None] * 32
node = self.head
while(node != None):
prev = node.prev
node.prev = None
i = 0
while((i < 32) and (an[i] != None)):
node = self.Merge(an[i], node)
an[i] = None
i = i+1
if(i == 32):
i = i-1
an[i] = node
node = prev
for i in xrange (0, 32):
node = self.Merge(an[i], node)
self.head = node
512K节点的测试代码。在我的系统中，自上而下大约需要4.5秒，自下而上大约需要3.9秒。为了了解Python的开销，在C中自下而上大约需要0.06秒。
import random
from time import time
p = [random.randint(0, 2147483647) for r in xrange(512*1024)]
a = Stack()
for i in xrange (0, len(p)):
a.push(p[i])
s = time()
a.MergeSort()
e = time()
print e - s
for i in xrange (0, len(p)):
p[i] = a.pop().data
for i in xrange (1, len(p)):
if(p[i-1] > p[i]):
print("error")
break