如何在Python的链表上实现SelectionSort和InsertionSort？

Question

我已经实现了一个链接列表类，并且我创建了一个可在常规列表上工作的selectionSort和insertionSort函数。我需要让selectionSort和insertionSort工作在链表上，但我不确定从哪里开始，如果我是诚实的。

这里是我的链表类：

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

    def getData(self): 
     return self.data 

    def getNext(self): 
     return self.next 

    def setData(self,newdata): 
     self.data = newdata 

    def setNext(self, newnext): 
     self.next = newnext 

class unorderedList: 
    def __init__(self): 
     self.head = None 

    def isEmpty(self): 
     return self.head == None 

    def add(self, item): 
     temp = Node(item) 
     temp.setNext(self.head) 
     self.head = temp 

    def length(self): 
     current = self.head 
     count = 0 
     while current != None: 
      count = count + 1 
      current = current.getNext() 

     return count 

    def search(self, item): 
     current = self.head 
     found = False 
     while current != None and not found: 
      if current.getData() == item: 
       found = True 
      else: 
       current = current.getNext() 

     return found 

    def remove(self, item): 
     current = self.head 
     previous = None 
     found = False 
     while not found: 
      if current.getData() == item: 
       found = True 
      else: 
       previous = current 
       current = current.getNext() 

     if previous == None: 
      self.head = current.getNext() 
     else: 
      previous.setNext(current.getNext() 

这是我的选择排序和插入排序的代码。他们在常规列表上工作得很好，但我很难找出从哪里开始让他们在链表上工作（无序列表）。

def selectionSort(alist): 
    for fillslot in range(len(alist)-1,0,-1): 
      positionOfMax = 0 
      for location in range(1,fillslot+1): 
        if alist[location]>alist[positionOfMax]: 
          positionOfMax = location 

      temp = alist[fillslot] 
      alist[fillslot] = alist[positionOfMax] 
      alist[positionOfMax] = temp 

def insertionSort(alist): 
    for index in range(1,len(alist)): 

      currentvalue = alist[index] 
      position = index 

      while position>0 and alist[position-1]>currentvalue: 
        alist[position] = alist[position-1] 
        position = position-1 

      alist[position] = currentvalue 

任何建议/提示将不胜感激。

Answer 1

我试图执行insertionSort，代码是可读的。 SelectionSort应该是相似的，试着去实现它。

def insertionSort(h): 
    if h == None: 
     return None 
    #Make the first node the start of the sorted list. 
    sortedList= h 
    h=h.next 
    sortedList.next= None 
    while h != None: 
     curr= h 
     h=h.next 
     if curr.data<sortedList.data: 
      #Advance the nodes 
      curr.next= sortedList 
      sortedList= curr 
     else: 
      #Search list for correct position of current. 
      search= sortedList 
      while search.next!= None and curr.data > search.next.data: 
       search= search.next 
      #current goes after search. 
      curr.next= search.next 
      search.next= curr 
    return sortedList 

def printList(d): 
    s='' 
    while d: 
     s+=str(d.data)+"->" 
     d=d.next 
    print s[:-2] 

l= unorderedList() 
l.add(10) 
l.add(12) 
l.add(1) 
l.add(4) 
h= l.head 
printList(h) 

result= insertionSort(l.head) 
d= result 
printList(d) 

输出：

4->1->12->10 
1->4->10->12