快速排序

算法原理

1. 取一个元素p(第一个元素，最后一个元素，中间元素，随机 都可以)，使元素p归位。

2. 列表被p分成两部分，左边都比p小，右边都比p大。

3. 递归完成排序。

动态演示

python代码实现

import sys
import time# 修改递归最大深度
sys.setrecursionlimit(100000)def partition(li, left, right):"""归为算法，被递归调用:param li:待排序列表:param left:当前左下标，初始第一次 为0:param right:当前右下标 初始第一次 为列表最后一个元素:return:"""# 先把最左边的值拿出来，放入tmp变量临时存储，第一次取列表0索引元素tmp = li[left]# 循环条件 左边指针一直小于右边指针while left < right:# 从最右边找比tmp小的数，放入tmp位置while left < right and li[right] >= tmp:right -= 1# 把右边的值写道左边空位上li[left] = li[right]while left < right and li[left] <= tmp:left += 1# 把左边的值写道右边的空位上li[right] = li[left]# time.sleep(0.2)# 当左右指针相等，就是碰头了，把最左边取出来的值，放入中间左右指针碰头的地方li[left] = tmp  # 把tmp归位return leftdef quick_sort(li, left, right):""":param li:待排序列表:param left:列表:param right::return:"""# 至少两个元素if left < right:mid = partition(li, left, right)quick_sort(li, left, mid - 1)quick_sort(li, mid + 1, right)li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)

C++代码实现