Quick Sort
code: python
import random
# O(nlogn) 最悪 O(n^2), O(n)
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = random.choice(arr)
left = x for x in arr if x < pivot
middle = x for x in arr if x == pivot
right = x for x in arr if x > pivot
return quick_sort(left) + middle + quick_sort(right)
def test_quick_sort():
assert quick_sort(3, 5, 8, 1, 2, 9, 4, 7, 6) == 1, 2, 3, 4, 5, 6, 7, 8, 9