快速排序
快速排序最差情況
每一輪的partition沒有起到作用锨能，理想的分段是將數組均分炕泳，現在是全部都在一遍 所以partition是失敗的
image
partition示意圖
image
弊端
容易出現的失敗的partition 標定點位于數組的兩邊
image
雙路partition示意圖
對于相等的元素也會停下來 執(zhí)行交換 保證了partition的性能 標定點可以位于中間
等于pivot的元素分散到了左右兩個部分
代碼中的細節(jié)：
-
為啥左右指針可以相等勿锅？早抠？
還是需要明確變量的定義
我們始終維護的是 [l+1,i-1]<v 對于arr[i]不明確它的大小
同樣 arr[j+1,r]>v (下圖寫錯了) 對于arr[j]不明確它的大小
所以當i==j時 我們還沒有去判斷arr[i] 怎么能就此結束這個數有可能大于v也有可能小于v
這兩種情況顯然對應不同的狀況 所以還需要一輪的判斷決定這個數是大于v還是小于v
-
為啥
nums[i] < pivot不加等號- 對于相等的元素依然需要交換 因為對于出現大量重復元素的情況腌巾，保證了標定點可以位于中間而不是兩邊
while i <= j and nums[i] < pivot: # 這里不加等于號
i += 1
image
三路快速排序示意圖
很好的解決等于的元素
image
def quickSort2Ways(nums):
def quickSort(left, right):
if left >= right:
return
parti = partition2Ways(left, right)
quickSort(left, parti - 1)
quickSort(parti + 1, right)
def partition2Ways(left, right):
pivot = nums[left]
l, r = left + 1, right # l r 指向的位置都是當前不確定大于還是小于的位置
# while True:
# while l <= r and nums[l] < pivot:
# l += 1
# while l <= r and nums[r] > pivot:
# r -= 1
# if l > r: # 終止條件是兩指針交叉
# break
# else:
# nums[l], nums[r] = nums[r], nums[l]
# l += 1
# r -= 1
# 這里為啥要加等號 因為num[l] 這個數字沒有判斷過大小 事還沒辦完
while l <= r: # 拆分成三種基本情況
if nums[l] < pivot:
l += 1
elif nums[r] > pivot:
r -= 1
else:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
nums[left], nums[r] = nums[r], nums[left]
return r
return quickSort(0, len(nums - 1))
def quickSort3Ways(nums):
def quickSort(left, right):
if left > right:
return
lt, gt = partition3Ways(left, right)
quickSort(left, lt)
quickSort(gt, right)
def partition3Ways(left, right):
pivot = nums[left]
# [left+1,lt] < v [lt+1, i-1] = v 定義i是一個還沒有判斷大小的數 [gt,right] > v
lt, i, gt = left, left + 1, right + 1 # 初始化需要保證上面的定義成立
# while True:
# while i < gt and nums[i] < pivot:
# nums[lt + 1], nums[i] = nums[i], nums[lt + 1]
# lt += 1
# i += 1
# while i < gt and nums[i] == pivot:
# i += 1
# while i < gt and nums[i] > pivot:
# nums[gt - 1], nums[i] = nums[i], nums[gt - 1]
# gt -= 1
# i += 1
# if i >= gt:
# break
while i < gt: # 這里為什么不需要等號 因為gt是閉區(qū)間 nums[gt]這個數字已經判斷過大小
if nums[i] < pivot:
nums[lt + 1], nums[i] = nums[i], nums[lt + 1]
lt += 1
i += 1
elif nums[i] == pivot:
i += 1
else:
nums[gt - 1], nums[i] = nums[i], nums[gt - 1]
nums[left], nums[lt] = nums[lt], nums[left]
lt -= 1
return lt, gt
