import random
from collections import deque

def quick_sort1(arr):
queue = deque([0, len(arr) - 1])
while len(queue) > 0:
left = queue.popleft()
right = queue.popleft()
if left >= right:
continue
pivot_index = random.randint(left, right)
arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
store_index = left
for i in range(left, right):
if arr[i] < arr[right]:
arr[i], arr[store_index] = arr[store_index], arr[i]
store_index += 1
arr[store_index], arr[right] = arr[right], arr[store_index]
queue.extend([left, store_index - 1, store_index + 1, right])


def quick_sort2(arr):
queue = deque([0, len(arr) - 1])
while len(queue) > 0:
left = queue.popleft()
right = queue.popleft()
if left >= right:
continue
pivot_index = random.randint(left, right)
arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
i = left - 1
j = right
while i < j:
i += 1
j -= 1
while i <= j and arr[i] < arr[right]:
i += 1
while arr[j] > arr[right]:
j -= 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[i], arr[right] = arr[right], arr[i]
queue.extend([left, i - 1, i + 1, right])


def quick_sort3(arr):
queue = deque([0, len(arr) - 1])
while len(queue) > 0:
left = queue.popleft()
right = queue.popleft()
if left >= right:
continue
# 元素个数小于7个时，使用插入排序
if right - left < 7:
for i in range(left + 1, right + 1):
temp = arr[i]
j = i - 1
while j >= 0 and arr[j] > temp:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = temp
continue

pivot_index = random.randint(left, right)
arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
i = left - 1
j = right
while i < j:
i += 1
j -= 1
while i <= j and arr[i] < arr[right]:
i += 1
while arr[j] > arr[right]:
j -= 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[i], arr[right] = arr[right], arr[i]
queue.extend([left, i - 1, i + 1, right])


arr = [random.randint(0, 9) for i in range(0, 10)]
print(arr)
copy = arr[:]
quick_sort1(copy)
print(copy)
copy = arr[:]
quick_sort2(copy)
print(copy)
copy = arr[:]
quick_sort3(copy)
print(copy)

[8, 9, 4, 9, 2, 9, 3, 9, 0, 6]
[0, 2, 3, 4, 6, 8, 9, 9, 9, 9]
[0, 2, 3, 4, 6, 8, 9, 9, 9, 9]
[0, 2, 3, 4, 6, 8, 9, 9, 9, 9]


import timeit

N = 10000
M = N
def test_quick_sort1():
arr = [random.randint(0, M) for i in range(0, N)]
quick_sort1(arr)

def test_quick_sort2():
arr = [random.randint(0, M) for i in range(0, N)]
quick_sort2(arr)

def test_quick_sort3():
arr = [random.randint(0, M) for i in range(0, N)]
quick_sort3(arr)

print(timeit.timeit('test_quick_sort1()', number=10, setup='from __main__ import test_quick_sort1'))
print(timeit.timeit('test_quick_sort2()', number=10, setup='from __main__ import test_quick_sort2'))
print(timeit.timeit('test_quick_sort3()', number=10, setup='from __main__ import test_quick_sort3'))

0.6726022359216586
0.6794583379523829
0.5315109230577946


N = 10000
M = N / 100

print(timeit.timeit('test_quick_sort1()', number=10, setup='from __main__ import test_quick_sort1'))
print(timeit.timeit('test_quick_sort2()', number=10, setup='from __main__ import test_quick_sort2'))
print(timeit.timeit('test_quick_sort3()', number=10, setup='from __main__ import test_quick_sort3'))

1.1784412029664963
0.7004980799974874
0.47143277898430824