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

Question

这是我的节点类：

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 html" target="_blank">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的指针中，然后将下一个项目从列表中“删除”，方法是将其设置为当前-

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

我希望这有帮助。

答案链接

我试图让我的代码后，这篇文章，但不知道如何找到正确的地方项目，然后插入它。这是我的代码：

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

有人能帮我吗？

Answer 1

引用的文本简要描述了您需要执行的操作：

从列表的开头开始，一直向前，直到你找到正确的位置。完成后，在那里插入项目，然后继续进行插入排序。

您已经获得了对列表开头的引用，因此从那里开始再次迭代，以找到放置不合适节点的位置。您可能需要一些额外的逻辑来处理在列表的最开始插入一个新指针（因为您需要从外部对象更新head指针），但除此之外，一切都应该非常简单。

Answer 2

基本上需要两个指针，一个用于外循环，一个用于内循环。因为您通常使用while循环，例如：`while（curr-

Answer 3

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

循环的终止条件为：

而当前！=无：
而current.getNext（）！=无：

从列表中提取节点：

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

然后你必须区分两种情况。首先处理节点（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()

在inpos之后插入temp：

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

排序方法：

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)