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

Question

这是我的节点Class:

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

我有一个单向链表，需要用插入排序进行排序。我对使用常规列表而不是链接列表的插入排序有很好的理解。我找到了另一个 post，一位用户这样说：

Let's think about how Insertion Sort works: It "splits" (in theory) the list into three groups: the sorted subset (which may be empty), the current item and the unsorted subset (which may be empty). Everything before the current item is sorted. Everything after the current item may or may not be sorted. The algorithm checks the current item, comparing it with the next item. Remember that the first item after the current item belongs to the unsorted subset.

Let's assume that you are sorting integers in increasing order (so given "3,1,5,2,4" you want to get "1,2,3,4,5"). You set your current item to the first item in the list. Now you begin sorting:

If the next item is greater than the current item, you don't need to sort that item. Just make it "current item" and continue.

If the next item is less than the current item then you have some work to do. First, save the next item somewhere - let's say in a pointer called temp - and then "remove" the next item from the list, by making current->next = current->next->next. Now, you need to find right place for the removed item. You can do this in two ways:

Either start from the beginning of the list, going forward until you find the correct position. Once you do, you insert the item there and you continue your insertion sort. This is the simplest solution if you have a singly-linked list. You go backwards, until you find the correct spot for the item. Once you do, you insert the item there and you continue your insertion sort. This is a bit more involved but can work well if you have a doubly-linked list. You continue this process until you reach the end of the list. Once you reach it, you know that you have completed your insertion sort and the list is in the correct sorted order.

I hope this helps.

Link of answer

我曾尝试在此 post 之后制作我的代码，但不知道如何找到该项目的正确位置，然后将其插入。这是我的代码：

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

你基本上需要两个指针，一个用于外循环，一个用于内循环。由于您通常使用 while 循环，例如：`while (curr->next != null)，因此在外循环结束时您希望将内循环初始化回指向头部。

Answer 2

引用的文字简要描述了您需要做什么：

start from the beginning of the list, going forward until you find the correct position. Once you do, you insert the item there and you continue your insertion sort.

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

Answer 3

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

循环的终止条件为：

~~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()

在inpos之后插入temp:

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)

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

How to sort a Singly Linked List with Insertion Sort?

python

sorting

linked-list

insertion-sort