1、双指针法
def quick_sort(arr, start, end):
# 递归结束条件
if start >= end:
return
pivot = arr[start]
left = start
right = end
while left != right:
while right > left and arr[right] > pivot:
right -= 1
while left < right and arr[left] <= pivot:
left += 1
if left < right:
arr[right], arr[left] = arr[left], arr[right]
arr[start] = arr[left]
arr[left] = pivot
quick_sort(arr, start, left-1)
quick_sort(arr, left+1, end)
2、单指针法
def quick_sort2(arr, start, end):
# 递归结束条件
if start >= end:
return
pivot = arr[start]
mark = start
cur = start
while cur <= end:
if arr[cur] < pivot:
mark += 1
arr[mark], arr[cur] = arr[cur], arr[mark]
cur += 1
arr[start] = arr[mark]
arr[mark] = pivot
quick_sort2(arr, start, mark-1)
quick_sort2(arr, mark+1, end)
