Hoare partition scheme
import random
nums = []
for x in range(10):
nums.append(random.randint(1, 101))
print(nums)
def partition(arr, low, high, pivot):
while low <= high:
while arr[low] < pivot:
low += 1
while arr[high] > pivot:
high -= 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low += 1
high -= 1
return low
def quicksort(arr, low, high):
if low >= high:
return
pivot = arr[low]
p = partition(arr, low, high, pivot)
quicksort(arr, low, p - 1)
quicksort(arr, p, high)
quicksort(nums, 0, len(nums) - 1)
print(nums)
网友评论