python3 快速排序，,思路第一步：找到一个

python3 快速排序，,思路第一步：找到一个

思路

第一步：找到一个随机的数，一般都是第一个数，也就是left,递归中也用left，放到缓存中，专业叫 基准值，基准值是要放在中间的。

第二步：最左边空出一个位置就是索引left的位置，所以从右向左找比基准值小的索引 R ，找到并将值放在left位置，这样索引R 就会空出来。

第三步：从左向右找比基准值大的索引 L 并将值放在right的位置上。

第四步：循环到left = right，就是基准值的索引，将基准值赋值进去，并返回 基准值索引。

第五步：递归排序基准值左边的列表，

第六步：递归排序基准值右边的列表。

def quit_sort(data, left, right):    if left < right:        mid = partition(data, left, right)        quit_sort(data, left, mid - 1)  # 最左面到中间        quit_sort(data, mid + 1, right)     # 中间到最后def partition(data, left, right):    tmp = data[left]    while left < right:        # 从右找到比中间小的值的索引        while left < right and data[right] > tmp:            right -= 1        data[left] = data[right]        # 从左找到比中间大的索引        while left < right and data[left] < tmp:            left += 1        data[right] = data[left]    data[left] = tmp    return leftli = list(range(1000))random.shuffle(li)print(li)quit_sort(li,0,len(li)-1)print(li)

注：python中有最大的递归层数，如果超过会报错，我们需要设置一下

import syssys.setrecursionlimit(10000)

快排的时间复杂度

最好情况 O(nlongn)

一般情况O(nlongn)

最差情况 O(n²)

python3 快速排序