arr = [4, 3, 2, 1, -1, 99, 12, 33, 99, 10]
print(arr)
def partition(arr: list, low: int, high: int, pivot: int):
while low <= high:
while arr[low] < pivot:
low = low + 1
while arr[high] > pivot:
high = high - 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low = low + 1
high = high - 1
return low
def quicksort(arr: list, low: int, high: int):
stack = []
stack.append(low)
stack.append(high)
while len(stack) > 0:
h = stack.pop()
l = stack.pop()
if l >= h:
continue
pivot = arr[l] # use first value as pivot
p = partition(arr, l, h, pivot)
if l < p:
stack.append(l)
stack.append(p - 1)
if h > p:
stack.append(p)
stack.append(h)
quicksort(arr, 0, len(arr) - 1)
print(arr)
快速排序 - 非递归
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 快速排序 在数组中选择一个元素K，然后将数组中大于该元素K的元素放在元素K的左边，小于的放在右边，形成左右两个新的...
