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 - )  # 最左面到中间

        quit_sort(data, mid + , right)     # 中间到最后

def partition(data, left, right):

    tmp = data[left]

    while left < right:

        # 从右找到比中间小的值的索引

        while left < right and data[right] > tmp:

            right -=

        data[left] = data[right]

        # 从左找到比中间大的索引

        while left < right and data[left] < tmp:

            left +=

        data[right] = data[left]

    data[left] = tmp

    return left

li = list(range())

random.shuffle(li)

print(li)

quit_sort(li,,len(li)-)

print(li)

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

import sys

sys.setrecursionlimit()

快排的时间复杂度

最好情况 O(nlongn)

一般情况 O(nlongn)

最差情况 O(n²)

巴特西

python3 快速排序

最新文章

热门文章