时间戳

首页 > 解决方案 > 如何使用插入排序对单链表进行排序？

python - 如何使用插入排序对单链表进行排序？

问题描述

这是我的节点类：

class Node:
def __init__(self, initData, initNext):
    """ Constructs a new node and initializes it to contain
    the given object (initData) and link to the given next node. """

    self.data = initData
    self.cover = True
    self.next = initNext

    # Additional attributes

def getData(self):
    """ Returns the element """
    return self.data

def getNext(self):
    """ Returns the next node """
    return self.next

def getDisplay(self):
    #TODO
    if self.cover == True:
        return '_'
    elif self.cover == False:
        return self.data

def setData(self, newData):
    """ Sets newData as the element """
    self.data = newData

def setNext(self, newNext):
    """ Sets newNext as the next node """
    self.next = newNext

def setDisplay(self, newDisplay):
    #TODO
    if newDisplay == self.data:
        self.cover = False
    elif newDisplay != self.data:
        self.cover = True

我有一个单链表，需要使用插入排序进行排序。我对常规列表的插入排序有很好的理解，但对链表却没有。我找到另一个帖子，一位用户说：

让我们考虑一下插入排序是如何工作的：它（理论上）将列表“拆分”为三组：已排序的子集（可能为空）、当前项和未排序的子集（可能为空）。当前项目之前的所有内容都已排序。当前项目之后的所有内容可能会或可能不会排序。该算法检查当前项目，将其与下一个项目进行比较。请记住，当前项之后的第一项属于未排序的子集。

假设您正在按升序对整数进行排序（因此给定“3,1,5,2,4”，您希望得到“1,2,3,4,5”）。您将当前项目设置为列表中的第一项。现在开始排序：

如果下一项大于当前项，则不需要对该项进行排序。只需将其设为“当前项目”并继续。

如果下一项小于当前项，那么您还有一些工作要做。首先，将下一项保存在某处——比如说在一个名为 temp 的指针中——然后通过使 current->next = current->next->next 从列表中“删除”下一项。现在，您需要为删除的项目找到正确的位置。您可以通过两种方式做到这一点：

从列表的开头开始，继续前进，直到找到正确的位置。完成后，将项目插入那里并继续插入排序。如果您有一个单链表，这是最简单的解决方案。您向后走，直到找到该项目的正确位置。完成后，将项目插入那里并继续插入排序。这有点复杂，但如果你有一个双向链表，它可以很好地工作。您继续此过程，直到到达列表的末尾。一旦你到达它，你就知道你已经完成了插入排序并且列表处于正确的排序顺序。

我希望这有帮助。

答案链接

我试图在这篇文章之后制作我的代码，但不知道如何找到该项目的正确位置然后插入它。这是我的代码：

def sort(self):
    head = self.linkedList.head
    current = head
    while current != None:
        if current.getNext().getData() > current.getData():
            current = current.getNext()
        else:
            temp = current
            current.setNext(current.getNext().getNext())
            #I am not sure what to do here

谁能帮我？

标签： pythonsortinglinked-listinsertion-sort

解决方案

您必须将没有很好排序的后继节点移动到正确的位置。

循环的终止条件是：

while current != None:
while current.getNext() != None:

从列表中提取节点：

temp = current.getNext()
current.setNext(temp.getNext())

然后你必须区分2种情况。首先处理节点 ( temp) 是列表新头的情况：

if head.getData() > temp.getData():
    temp.setNext(head)
    self.linkedList.head = temp
    head = self.linkedList.head

在另一种情况下，您必须找到前驱节点。这意味着必须放置节点 ( inpos) 之后的节点 ( )：temp

inpos = head
while temp.getData() > inpos.getNext().getData():
    inpos = inpos.getNext()

temp 在之后插入inpos：

temp.setNext(inpos.getNext())
inpos.setNext(temp)

sort方法：

def sort(self):
    head = self.linkedList.head
    current = head
    while current.getNext() != None:
        if current.getNext().getData() > current.getData():
            current = current.getNext()
        else:
            temp = current.getNext()
            current.setNext(temp.getNext())
            if head.getData() > temp.getData():
                temp.setNext(head)
                self.linkedList.head = temp
                head = self.linkedList.head
            else:
                inpos = head
                while temp.getData() > inpos.getNext().getData():
                    inpos = inpos.getNext()
                temp.setNext(inpos.getNext())
                inpos.setNext(temp)

推荐阅读