前言
QuickSort 算是面試中或是演算法中經典的問題,非常重要,
而且最容易搞錯「他的範圍」,因此這邊來將自己的常見錯誤做一個總整理。
先一個正式版本
基本上,要講出 QuickSort 的核心精神,人人幾乎都不太會犯錯,
但程式非常容易寫錯,特別是在區間的控制過程。
QuickSort 的核心精神
QuickSort 的核心精神就是選定一個 pivot (可以頭可以尾),
將剩下的數字透過 pivot 分成 「 < pivot 」 與 「 > pivot 」 兩組。
最容易出錯的地方 – 決定邊界
在撰寫程式的時候,如果沒有仔細思考,或甚至已經仔細思考了都還經常會寫錯。
注意:這邊示範的並「不是」主流的教科書寫法,而是用釐清觀念候「用自己的方式」寫的。
我們的目的如上圖,就是希望在循環結束時,能夠
- 讓 left 左邊的一切都是 smaller (than pivot)
- 讓 right 右邊的一切都是 bigger (than pivot)
因此 (以下為說明用的程式碼,並不完整)
while(left <= right):
while(left <= right and a[left] < pivot):
left += 1
while(left <= right and a[right] > pivot):
right -= 1
if left <= right:
a[left], a[right] = a[right], a[left]
注意啦! 光上面這裡有很多細節了!
left <= right
首先是 left <= right,如果寫 left < right 達不到交錯的效果,有可能出迴圈要多做處理
不是不能這樣寫,就是要多做一些處理,沒有什麼不能的寫法
a[left] < pivot, a[right] > pivot
注意這裡不處理等於,原因是處理等於也不一定好,
等於表示與 pivot 相等,用於處理重複的 array,
但如果硬要處理等於的情況,在 [1,1,1,1,1] 類似這樣的 case,
一定會用 worst case 的 O(n) 時間去解,而不是平均的 O(nlogN)。
可以先理解 QuickSort 的 worst case 是什麼情況及為什麼會發生,
這樣更能夠懂為什麼會舉到上面的例子。
此種類的完整的 QuickSort 程式碼
def partition(self, nums, start, end):
# recusion end
if start >= end:
return
# recursion define
left, right = start+1, end
pivot = nums[start]
while(left <= right):
while(left <= right and nums[left] < pivot):
left += 1
while(left <= right and nums[right] > pivot):
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
else:
nums[start], nums[right] = nums[right], nums[start]
print(nums, left, right)
# recursion split
self.partition(nums, start, right-1)
self.partition(nums, left, end)
抓 partition 與 pivot 的重點
我們設計的思想是
- 一開始:
pivot(start) < (left, start+1) < (right, end) 結束時,交換前 (注意交錯):
(start) < start+1 < right < left < end
務必注意交錯的位置的「 right < left 」,這是最最重要的部分。
- 結束時,交換後 (注意交錯):
start < right-1 < pivot(right) < left < end
而 start ~ right-1 都比 pivot 小
left < end 都比 pivot 大。
結束迴圈 recursion 「start >= end」
不論是
- self.partition(nums, start, right-1)
- self.partition(nums, left, end)
right 會越來越逼近 start,直到重疊 start >= end
而 left 也會越來越逼近 end (因為 left 與 right 是交錯,只會更逼近 end)
另外一種寫法
建議先嘗試閱讀以下程式碼,思考一下
(這我寫過的東西,我也想了很久為什麼)
while(left <= right)
if a[left] < pivot:
left += 1
elif a[right] > pivot:
right -= 1
else:
a[left], a[right] = a[right], a[left]
# left += 1
# right -= 1
建議想好後再看,這樣才會更印象深刻。
注意 left <= right
一樣要注意的 left <= right,因為一定要交錯。
「left += 1」、「right -= 1」可有可無
其中「left += 1」、「right -= 1」可有可無,
沒有當下處理也會在之後的迴圈被處理掉。
此種類的完整的 QuickSort 程式碼
def partition(self, nums, start, end):
# recusion end
if start >= end:
return
# recursion define
left, right = start+1, end
pivot = nums[start]
while(left <= right):
if nums[left] < pivot:
left += 1
elif nums[right] > pivot:
right -= 1
else:
nums[left], n