如何在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