## Quick Select算法

import random

def quick_select(arr, k):
left = 0
right = len(arr) - 1
while True:
if left >= right:
return arr[left]
pivot_index = random.randint(left, right)
arr[right], arr[pivot_index] = arr[pivot_index], arr[right]
store_index = left
for i in range(left, right):
if arr[i] < arr[right]:
arr[store_index], arr[i] = arr[i], arr[store_index]
store_index += 1
arr[right], arr[store_index] = arr[store_index], arr[right]
if k - 1 == store_index:
return arr[store_index]
elif k - 1 < store_index:
right = store_index - 1
else:
left = store_index + 1

arr = [random.randint(0, 9) for i in range(0, 10)]
print(arr)
print(quick_select(arr, 3))

[2, 7, 7, 4, 4, 3, 2, 6, 9, 6]
3


## Heap Select算法

import random

def heap_select(arr, k):
build_heap(arr, k)

for i in range(k, len(arr)):
if arr[i] < arr[0]:
arr[0], arr[i] = arr[i], arr[0]
ajust_heap(arr, 0, k - 1)
return arr[0]

def build_heap(arr, k):
start = (k - 2) // 2
while start >= 0:
ajust_heap(arr, start, k - 1)
start -= 1

def ajust_heap(arr, root, tail):
while root * 2 + 1 <= tail:
left_child = root * 2 + 1
to_swap = root
if left_child <= tail and arr[to_swap] < arr[left_child]:
to_swap = left_child
right_child = left_child + 1
if right_child <= tail and arr[to_swap] < arr[right_child]:
to_swap = right_child
if to_swap != root:
arr[to_swap], arr[root] = arr[root], arr[to_swap]
root = to_swap
else:
return

arr = [random.randint(0, 9) for i in range(0, 10)]
print(arr)
print(heap_select(arr, 3))

[8, 6, 4, 9, 1, 1, 8, 4, 4, 7]
4


## BFPRT算法

import random

def bfprt_select(arr, k):
idx = select(arr, 0, len(arr) - 1, k)
return arr[idx]

def select(arr, left, right, k):
while True:
if left >= right:
return left
pivot_index = get_pivot(arr, left, right)
arr[right], arr[pivot_index] = arr[pivot_index], arr[right]
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[right], arr[store_index] = arr[store_index], arr[right]
if k - 1 == store_index:
return store_index
elif k - 1 > store_index:
left = store_index + 1
else:
right = store_index - 1

def get_pivot(arr, left, right):
if right - left < 5:
return select5(arr, left, right)
for i in range(left, right - 4, 5):
sub_right = i + 4
if sub_right > right:
sub_right = right
median_index = select5(arr, i, sub_right)
arr[median_index], arr[left + (i - left) // 5] = arr[left + (i - left) // 5], arr[median_index]
return select(arr, left, left + (right - left) // 5, (right - left) // 10 + 1)

def select5(arr, left, right):
for i in range(left + 1, right + 1):
temp = arr[i]
j = i - 1
while j >= left and arr[j] > temp:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = temp
return left + (right - left) // 2

arr = [random.randint(0, 9) for i in range(0, 10)]
print(arr)
print(bfprt_select(arr, 9))

[2, 3, 8, 7, 5, 2, 5, 7, 9, 6]
8


for i in range(0, 1000):
arr = [random.randint(0, 1000) for i in range(0, 1000)]
k = random.randint(1, 999)
quick_ret = quick_select(arr[:], k)
heap_ret = heap_select(arr[:], k)
bfprt_ret = bfprt_select(arr[:], k)
if quick_ret != heap_ret or heap_ret != bfprt_ret:
print(arr, k, quick_ret, heap_ret, bfprt_ret)


import timeit

N = 10000
def test_quick_select():
arr = [random.randint(0, N) for i in range(0, N)]
k = random.randint(1, N - 1)
quick_select(arr, k)

def test_heap_select():
arr = [random.randint(0, N) for i in range(0, N)]
k = random.randint(1, N - 1)
heap_select(arr, k)

def test_bfprt_select():
arr = [random.randint(0, N) for i in range(0, N)]
k = random.randint(1, N - 1)
bfprt_select(arr, k)

print(timeit.timeit('test_quick_select()', number=10, setup='from __main__ import test_quick_select'))
print(timeit.timeit('test_heap_select()', number=10, setup='from __main__ import test_heap_select'))
print(timeit.timeit('test_bfprt_select()', number=10, setup='from __main__ import test_bfprt_select'))

0.26961762097198516
0.35226804204285145
0.5465565109625459