Python3实现快速排序

2021/7/21 9:36:37

本文主要是介绍Python3实现快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

声明:参考B站视频,自学成长记录
https://www.bilibili.com/video/BV1mp4y1D7UP?p=16

'''
快速排序
    1. 取一个值归位
    2. 根据归位值分 左(比归位数小) / 右(比归位数大) 两部分
    3. 递归 1、2 步

'''
def kuaipai(lst, left, right):
    '''
    快速排序
    :param lst:  无序列表
    :param left: 最左下标
    :param right: 最右下标
    :return:
    '''
    # 将最左元素拿出来 存放到临时变量中
    tmp = lst[left]
    while left < right:
        # 右向左跳(从最右边开始找比列表left位置大的数)
        while left < right and lst[right] >= tmp:
            # 从右边往左挪一个位置
            right -= 1
        # 从右边起 将比tmp小的数 写到 列表的left位置
        lst[left] = lst[right]

        # 左向右跳(从次左边开始找比列表left位置大的数)
        while left < right and lst[left] <= tmp:
            # 从最左边往右挪一个位置
            left += 1
        # 从左边起 将比tmp大的数 写到 列表的right位置
        lst[right] = lst[left]

    # 将值归位
    lst[left] = tmp
    # 返回归位值得下标
    return left


def quick_sort(lst, left, right):
    if left < right:
        # 获取lst[left]归为后的下标
        mid = kuaipai(lst, left, right)
        # 递归处理左半部分
        quick_sort(lst, left, mid - 1)
        # 递归处理右半部分
        quick_sort(lst, mid + 1, right)


lst = [5, 6, 9, 4, 2, 7, 1, 8]
print(lst)
quick_sort(lst, 0, len(lst) - 1)
print(lst)

'''
运行结果
    [5, 6, 9, 4, 2, 7, 1, 8]
    [1, 2, 4, 5, 6, 7, 8, 9]
'''


这篇关于Python3实现快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程