一道題看快排
- 2019 年 10 月 5 日
- 筆記
一道題看快排
0.說在前面
1.排序鏈表2.快排實現2. 1 概括2.2 挖洞法2.3 雙指針法3.作者的話
0.說在前面
今天除了早上沒課，一天的滿課，但是我仍然堅持發文了，仍然堅持做題了，你們嗎？演算法最優群各位同學加油啦！！！看最後有哪些堅持下來的！
今天研究的是排序鏈表，由這個排序鏈表衍生研究挖洞法與雙指針法實現快排！同時在做排序鏈表完成後，學習了一位大佬的思路，並且手推排序，各位看不懂的可以留言，畢竟我寫的字太搓了。。
1.排序鏈表
問題
在 O(n log n) 時間複雜度和常數級空間複雜度下，對鏈表進行排序。
示例 1:
輸入: 4->2->1->3 輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0 輸出: -1->0->3->4->5
直接法
【思路】
直接遍歷鏈表一次，O(n)時間複雜度，將所有節點值添加到list當中，並進行排序，排序時間複雜度O(logn)，那麼最終的時間複雜度為O(nlogn)，但是空間複雜度為O(n)。
【實現】
def sortList(self, head): l = [] while head: l.append(head.val) head = head.next l.sort() p = head = ListNode(0) for i in l: p.next = ListNode(i) p = p.next p = head.next del head return p
冒泡排序
【思路】
這裡採用冒泡排序演算法進行實現，首先遍歷一次鏈表，獲取總結點個數，時間複雜度為O(n)，緊接著採用冒泡的O(n^2)時間複雜度進行排序，鏈表當中，每次將節點值較大的放在最後，這就是冒泡排序的一個優勢，在每次排序後，可以得到一個節點在正確位置。空間複雜度為O(1)，這個學習一下就行，在網站上通不過。
【實現】
def sortList(self, head): p = head size = 0 while p: size += 1 p = p.next for i in range(size - 1): l = head for j in range(size - i - 1): p = l p1 = l.next if (p.val > p1.val): temp = p.val p.val = p1.val p1.val = temp l = l.next return head
快排一
【思路】
這裡建議各位模擬一下實現，定義一個快指針與一個慢指針，然後通過快指針的元素與樞椎值比較，如果比樞椎小，則交換快慢指針元素值，否則快指針一直走到結尾，最後將慢指針的位置元素與樞椎元素之相交換就得到了一次快排結果，然後利用分治法，遞歸即可！最壞時間複雜度O(n^2)，最好O(nlogn)。空間複雜度O(1)。leetcode通不過，，，遺憾~
【實現】
def sortList(self, head): self.quickSort(head,None) return head def quickSort(self,head,tail): if head: slow = head fast = head.next while fast: if fast.val<head.val: slow = slow.next tmp = slow.val slow.val = fast.val fast.val = tmp fast = fast.next tmp = head.val head.val = slow.val slow.val = tmp if head != tail: self.quickSort(head,slow) self.quickSort(slow.next,None)
快排二
【參考】
這裡參考自leetcode英文網站上的一個大佬程式碼：
https://leetcode.com/problems/sort-list/discuss/?orderBy=recent_activity
【思路】
【實現】
由於原始程式碼沒有注釋，為了更好的讓大家學習這個程式碼，這裡給出核心行注釋！
這裡說明一下一個鏈表的頭結點與起始結點(第一個結點)的區別，一般鏈表為了方便操作統一，會創建一個頭結點，也就是在一個鏈表的第一個結點前面創建一個結點，而這個結點就是頭結點，例如原始鏈表為：1->3->4，那麼加入頭結點這為，假設頭結點用x表示，則為x->1->3->4，那麼在這個帶有頭結點的鏈表中，x為頭結點，1為起始結點或者說第一個結點，對於頭結點一個更特殊點在於，頭結點沒有數據，不包含任何值，所以在創建頭結點的時候，直接創建一個空結點即可。在python中的創建頭結點實現為：head = ListNode(0)或者head = ListNode(None)。
def sortList(self, head): # 頭結點 hat = ListNode(None) # 指向鏈表起始節點 hat.next = head # 開始快排 self.quick_sort(hat, None) return hat.next def quick_sort(self,hat, tail): # 判斷一開始所給鏈表至少2個節點以上 if hat.next is tail or hat.next.next is tail: return # hat1為小於樞椎鏈表的頭結點 # hat2為等於樞椎鏈表的第一個結點 # hat3為大於樞椎鏈表的頭結點 hat1, hat2, hat3 = hat, hat.next, ListNode(None) # 三個鏈表尾結點 tail1, tail2, tail3 = hat1, hat2, hat3 p, pivot = hat2.next, hat2.val while p is not tail: if p.val < pivot: tail1.next, tail1, p = p, p, p.next elif p.val == pivot: tail2.next, tail2, p = p, p, p.next else: tail3.next, tail3, p = p, p, p.next # 下面三行程式碼實現，將三個鏈表進行連接，構成一次排序後的鏈表！ # 大於樞椎的鏈表尾節點直接鏈接尾部結點 tail3.next = tail # 等於樞椎的鏈表連接大於樞椎鏈表，由於hat3為頭結點，第一個結點為hat3.next tail2.next = hat3.next # 小於樞椎的鏈表連接等於樞椎鏈表的第一個結點 tail1.next = hat2 self.quick_sort(hat1, hat2) self.quick_sort(tail2, tail)
2.快排實現
2. 1 概括
由於這道題為鏈表，採用快排不是很方便，而在這裡，順時學了溫故一下快排，這裡給出兩個方法，一個是挖洞法實現快排，另一個是雙指針實現快排。
2.2 挖洞法
挖洞法實現快排思路是，選擇一個數作為樞椎，將其與樞椎值相比較，此時比較過程為，假設樞椎選擇第一個，那麼從後往前遍歷(左邊index小於右邊的index情況下)，直到找到比樞椎小的，將這個數挖去，也就是挖洞，然後填入前面樞椎位置，緊接著，從左往右找比樞椎大的(左邊index小於右邊的index情況下)，找到這個數，將其挖去，也就是挖洞，然後放在上一次的洞裡面，填補，然後重複上述操作，最後將樞椎值填入最後左邊與右邊index相等的位置即可！
模擬圖如下：
實現如下：
def qucikSort1(s,low,high): if low>high: return # 以第一個為樞椎 privor = s[low] i = low j = high while i<j: # 從右向左找比樞椎小的值，並挖洞 while i<j and s[j]>=privor: j-=1 # 開始填洞 if i<j: s[i]=s[j] i+=1 # 從左向右找比樞椎大的值，並挖洞 while i<j and s[i]<privor: i+=1 # 開始填洞 if i<j: s[j]=s[i] j-=1 # 樞椎填入ij相等位置 s[i] = privor # 分治法 qucikSort1(s,low,i-1) qucikSort1(s,i+1,high) return s l = [1,9,0,7,6] print("-------未排序前-------") print(l) print("-------排序後-------") print(qucikSort1(l,0,len(l)-1))
2.3 雙指針法
雙指針法實現快排，則是前後各一個指針，假設將第一個元素作為樞椎，那麼循環的時候右邊得先循環，這個解釋看下面圖即可！當左邊index小於右邊index的時候，先從右邊遍歷，找到比樞椎大的元素，然後找到了右邊的index，也就是上面的挖洞處，開始處理左邊的，找到比樞椎小的元素，然後找到了左邊的index，也就是上面的挖洞出，此時左右兩邊洞口都找到了，那麼讓這兩個位置元素進行交換，不斷重複這個過程即可!
模擬圖如下：
實現：
l = [1,9,0,7,6] def qucikSort(s,low,high): if low>high: return # 以第一個為樞椎 privor = s[low] i = low j = high while i<j: # 從右向左找比樞椎小的值 while i<j and s[j]>=privor: j-=1 # 從左向右找比樞椎大的值 while i<j and s[i]<=privor: i+=1 if i<j: tmp = s[i] s[i] = s[j] s[j] = tmp s[low] = s[i] s[i] = privor qucikSort(s,low,i-1) qucikSort(s,i+1,high) return s print("-------未排序前-------") print(l) print("-------排序後-------") print(qucikSort(l,0,len(l)-1))
