題目：

　　給定一個無序鏈表的頭節點head，實現單鏈表的選擇排序。?
　　要求：空間復雜度O(1)。

基本思路

　　選擇排序的過程是從未排序的部分中找到最小值，然后放在已經排好序部分的尾部，逐漸將未排序的部分縮小，最后全部變成排好序的部分。時間復雜度O(N2)

class node:def __init__(self,value):self.value = valueself.next = Nonedef getSmallestPre(head):if head == None:returnsmallPre,small,pre,cur = None,head,head,head.nextwhile cur!=None:if cur.value < small.value:smallPre = presmall = curpre = curcur = cur.nextreturn smallPredef selectSort(head):tail,cur,smallPre,small = None,head,None,Nonewhile cur!=None:small = cursmallPre = getSmallestPre(small)if smallPre !=None:small = smallPre.nextsmallPre.next = small.nextif cur == small:cur = cur.nextelse:cur = curif tail == None:head = smallelse:tail.next = smalltail = smallreturn head

?

總結

以上是生活随笔為你收集整理的单链表的选择排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。