尝试在python中快速排序链接列表

我的教授要求我对链接列表执行Quicksort。由于所有的递归和链接对我来说还是很新的，这已经变得很混乱。问题似乎与无意中将某项分配为“无”有关到目前为止，这是我的代码：

class Node:
    def __init__(self,d,n):
        self.data = d
        self.next = n


class LinkedList:

    def __init__(self):
        self.head = None
        self.length = 0

    def append(self,d):
        if self.head == None:      
            self.head = Node(d,None) 
        else:
            ptr = self.head
            while ptr.next != None:
                ptr = ptr.next
            ptr.next = Node(d,None)
        self.length += 1

    def merge(self,other):
        ptr = self.head
        while ptr.next != None:
            ptr = ptr.next
        ptr.next = other.head

    def removeVal(self,d):
        if self.head == None:
            return
        if self.head.data == d:
            self.head = self.head.next
            self.length -= 1
        else:
            ptr = self.head 
            while ptr.next != None:
                if ptr.next.data == d:
                    ptr.next = ptr.next.next
                    self.length -= 1
                    break
                ptr = ptr.next  

    def sort(self):
        if self.head!=None:
            pivot=self.head.data
            self.removeVal(pivot)
            smaller=LinkedList()
            other=LinkedList()
            ptr=self.head
            while ptr.next!=None:
                ptr=ptr.next
                if ptr.data<pivot:
                    smaller.append(ptr.data)
                else:
                    other.append(ptr.data)
            smaller.sort()
            other.sort()
            self=smaller
            self.append(pivot)
            self.merge(other)


ls = LinkedList()
ls.append(0)
ls.append(1)
ls.append(3)
ls.sort()

运行此命令会出现以下错误

Traceback (most recent call last):
  File "main.py",line 71,in <module>
    ls.sort()
  File "main.py",line 58,in sort
    other.sort()
  File "main.py",line 51,in sort
    while ptr.next!=None:
AttributeError: 'NoneType' object has no attribute 'next'

任何帮助将不胜感激

您的sort（）函数失败，因为进入while循环时ptr可以为None。起初这并不明显，因为您在一开始就进行了检查

if self.head != None

但是，如果列表只有1个条目，则对self.removeVal(pivot)的调用会将您的头部指针设置为None。请注意，这最终将总是在快速排序期间发生，因为您要递归分解列表。最终，它必须是1元素列表，因此会失败。

发生这种情况时，您将获得张贴在堆栈跟踪上的消息：

AttributeError: 'NoneType' object has no attribute 'next'

要解决此问题，您可以重写while循环以直接查看ptr而不是ptr.next

         while ptr is not None:
                if ptr.data<pivot:
                    smaller.append(ptr.data)
                else:
                    other.append(ptr.data)
                ptr=ptr.next

我发现的另一个问题是您的作业：

self=smaller

这可能是合法的python代码，但我认为它很危险。我将其更改为

self.head = smaller.head

否则，您的示例从列表中删除了一个元素（尽管我没有确切地找到原因）请注意，这实际上并不会更新您的length属性，但我看不到为什么需要它，它在任何地方都没有使用。

关于效率的另一条注释：您在算法中执行了许多附加操作，而列表的使用非常昂贵，即实现它们的方式。这可能不是您在此处进行练习的重点。但是，当您遍历所有现有元素进行追加时，您将失去快速排序的效率。添加元素的成本为O（n），因此将列表拆分为较小的列表和其他列表的成本为O（n ^ 2）。

对于（链接的）列表，合并排序是一种更好的排序算法，它也可以像快速排序一样运行O（n * log（n））。

这是完整的代码

wchar_t

输出

#finding the pivot elemet
def partition(itemlist,low,high):
pivot=itemlist[high]
i=low-1
for j in range(low,high):
    if itemlist[j]<pivot:
        i=i+1;
        itemlist[i],itemlist[j]=itemlist[j],itemlist[i]
itemlist[i+1],itemlist[high]=itemlist[high],itemlist[i+1]
return i+1
# generating the partition
def sort(itemlist,high):
    if low < high:
        partitonIndex=partition(itemlist,high)
        sort(itemlist,partitonIndex-1)
        sort(itemlist,partitonIndex+1,high)
# array to be sort
itemlist=[5,3,6,2,7,1,9]
print(itemlist);
sort(itemlist,len(itemlist)-1)
print(itemlist);

仔细阅读错误代码。它说

File "main.py",line 51,in sort
while ptr.next!=None:
AttributeError: 'NoneType' object has no attribute 'next'

这很好地指示了问题所在和位置。您正在从第51行访问空节点。将While ptr.next !=None更改为While ptr != None，错误消失了。您需要通过测试找出原因。

如上所述，请确保问题中显示的方法可以作为快速排序被接受。您可能考虑创建3个列表，节点枢轴，并且仅对2个节点列表==枢轴使用递归。向列表添加尾部引用将加快附加操作。快速排序重新链接节点以重新排列节点而不是不断分配节点的示例代码。

class Node(object):

    def __init__(self,data):
        self.data = data
        self.next=None

class Linkedlist(object):

    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def push_back(self,data):
        self.length += 1
        new = Node(data)
        if(self.tail is None):
            self.head = self.tail = new
        else:
            self.tail.next = new
            self.tail = new

    def pop_front(self):
        if(self.head is None):
            return self.head
        self.length -= 1
        data = self.head.data
        self.head = self.head.next
        return data

    def show(self,head,tail):
        arr = []
        if(head is None):
            print(arr)
            return
        while(True):
            if(head.data is not None):
                arr.append(head.data)
            if(head is tail):
                break
            head = head.next
        print(arr)

    def quicksort(self,tail):
        if(head is tail):               # if single node return
            return head,tail
                                        # using 3 dummy nodes for 3 lists
        hlt = Node(None)                # head,tail < pivot list
        tlt = hlt
        heq = Node(None)                # head,tail = pivot list
        teq = heq
        hgt = Node(None)                # head,tail > pivot list
        tgt = hgt
        pivot = head
        curr  = head
        end   = tail.next
        while(curr is not end):
            if(curr.data < pivot.data):
                tlt.next = curr
                tlt = curr
            elif(curr.data == pivot.data):
                teq.next = curr
                teq = curr
            else:
                tgt.next = curr
                tgt = curr
            curr = curr.next
        heq = heq.next                  # at least 1 node (should release node)
        if(hlt is tlt):                 # if none < pivot
            hlt = heq                   #  (should release dummy node)
            tlt = heq
        else:                           # else recurse on list < pivot
            hlt = hlt.next              #  (should release dummy node)
            hlt,tlt = self.quicksort(hlt,tlt)
            tlt.next = heq
        if(hgt is tgt):                 # if none > pivot
            hgt = teq                   #  (should release dummy node)
            tgt = teq
        else:                           # else recurse on list > pivot
            hgt = hgt.next              #  (should release dummy node)
            hgt,tgt = self.quicksort(hgt,tgt)
            teq.next = hgt
        return(hlt,tgt)

    def sort(self):
        if (self.head == None):         # if empty list return
            return
        self.head,self.tail = self.quicksort(self.head,self.tail)
        self.tail.next = None
        return

lists=Linkedlist()
lists.push_back(27)
lists.push_back(35)
lists.push_back(23)
lists.push_back(22)
lists.push_back(38)
lists.push_back(26)
lists.push_back(31)
lists.push_back(24)
lists.push_back(37)
lists.push_back(25)
lists.push_back(33)
lists.push_back(32)
lists.push_back(28)
lists.push_back(36)
lists.push_back(21)
lists.push_back(34)
lists.sort()
arr = []
while(True):
    data = lists.pop_front()
    if(data is None):
        break
    arr.append(data)
print(arr)

尝试在python中快速排序链接列表

ysh851216 回答：尝试在python中快速排序链接列表

大家都在问