Osheep

时光不回头,当下最重要。

python简洁代码实现快速排序

*快速排序 最优时间复杂度为nlogn,因为要完成n个嵌套调用,,但比冒泡排序要快
python实现逻辑过程是这样得。
1.设置两个游标 left跟right
2.设置基准值,网上有方案设置中间数为基准值,但计算比较麻烦,而且并不一定高效,这里设置列表最右的那个元素为基准值,
3.left游标 从左向右移动,当游标指向元素大于基准值时,停下,交换right游标指向的元素
4 同理 right右标向左移动
5 当左右游标相等时停止循环,赋值基准值给左游标指向的元素
6 对基准值左边的元素递归,重复以上步骤,
7 设置条件退出递归。
下面是代码实现

alist= [22,21,34,65,12,89,3,9,66]

def qucik_sort(alist,low, high):
    # 退出递归条件
    # left=right
    while low>high:
        return alist

    left = low
    right = high
    base_value = alist[right]

    while left < right:
        while left<right and alist[left] < base_value:
            left += 1
        # 跳出循环条件
        # alist[left]>=base_value
        alist[right]=alist[left]
        while right>left and alist[right]>base_value:
            right -= 1
        # 跳出循环条件
        # alist[right]<=base_value
        alist[left]=alist[right]
    # 把基准值赋值给游标停留的元素
    alist[right] = base_value
  # 继续对游标左右的队列递归快速排序
    qucik_sort(alist,low,left-1)
    qucik_sort(alist,left+1,len(alist)-1)
    print(alist)

if __name__ == '__main__':

    low = 0
    high = len(alist)-1
    qucik_sort(alist,low,high)

输出结果为 [3, 9, 12, 21, 22, 34, 65, 66, 89]

简洁的代码 ,很pythonic.

点赞