快速排序
def quick_sort(a: list[int]) -> list[int]:
if len(a) <= 1:
return a
pivot = a[len(a) // 2]
left = [x for x in a if x < pivot]
middle = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
if __name__ == '__main__':
a = [5, 3, 1, 2, 4]
print(quick_sort(a)) # [1, 2, 3, 4, 5]
# 单向快速排序
def quick_sort(a: list[int], lo: int, hi: int):
if lo >= hi:
return
index = partition(a, lo, hi)
quick_sort(a, lo, index - 1)
quick_sort(a, index + 1, hi)
def partition(a, lo, hi):
pivot = a[hi]
i = lo - 1
for j in range(lo, hi):
if a[j] <= pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[hi] = a[hi], a[i + 1]
return i + 1
if __name__ == '__main__':
a = [5, 3, 1, 2, 4]
quick_sort(a, 0, len(a) - 1)
print(a) # [1, 2, 3, 4, 5]
递归部分：调用分区方法返回一个位置，然后以这个位置为分界，将数组分成两部分，递归的调用该方法
分区部分：好比一个人在最后一个位置，然后安排小弟1在开头前一位，小弟2从头开始遍历数组，当小弟2发现自己的值比老大还小，那么就让小弟1右移一位，并交换两个小弟的值，当小弟2遍历完成了，再让小弟1右移一位并和老大交换值
# 双向快速排序
from random import randint
def quick_sort(a: list[int], lo: int, hi: int):
if lo >= hi:
return
index = partition(a, lo, hi)
quick_sort(a, lo, index - 1)
quick_sort(a, index + 1, hi)
def partition(a, lo, hi):
r = randint(lo, hi)
a[lo], a[r] = a[r], a[lo]
pivot = a[lo]
i = lo + 1
j = hi
while True:
while a[i] < pivot:
if i == hi:
break
i += 1
while a[j] > pivot:
if j == lo:
break
j -= 1
if i >= j:
break
a[i], a[j] = a[j], a[i]
a[lo], a[j] = a[j], a[lo]
return j
if __name__ == '__main__':
a = [5, 3, 1, 2, 4]
quick_sort(a, 0, len(a) - 1)
print(a) # [1, 2, 3, 4, 5]
递归部分：同上
分区部分：好比一个人在第一个位置，然后安排小弟1在第一数组第二个位子，小弟2在最后一个位子，然后小弟1从左往右找比老大大的值，小弟2从右往左找比老大小的值，只要他两没碰头，然后交换两个小弟的值，当他们碰头后，交换老大和小弟2的值