本文共 1646 字，大约阅读时间需要 5 分钟。

快速排序

    昨天说完了Low B三人组的插入排序，今天来说说NB三人组的快速排序。

1. 思路

1. 取一个元素p(第一个元素), 使元素P归位
2. 列表被p分为两部分, 左边都比p小, 右边都比p大
3. 递归完成排序

这里我用自己做的GIF来简单演示下列表中一个数的归位的部分过程(由于大小限制，这里只展示了部分过程，全过程视频请前往资源下载，是免费的哦: ):

2. 代码

def partition(li, left, right):    """    归位函数    :param li: 需要归位的无序列表    :param left: 左边开始的位置    :param right: 右边开始的位置    :return:     """    temp = li[left]    while left < right:        while left < right and li[right] >= temp:   # 从右边找比temp小的数            right -= 1     # 往左走一步        li[left] = li[right]   # 把右边的比temp小的值放到左边空位        while left < right and li[left] <= temp:  # 从左边找比temp大的数            left += 1      # 往右走一步        li[right] = li[left]  # 把左边的比temp大的值放到右边空位    li[left] = temp           # 把temp归位    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]quick_sort(li, 0, len(li)-1)print(li)

结果为:

[2, 7, 4, 6, 3, 1, 2, 9, 8][2, 7, 4, 6, 3, 1, 7, 9, 8][2, 1, 4, 6, 3, 1, 7, 9, 8][2, 1, 4, 6, 3, 6, 7, 9, 8][2, 1, 4, 3, 3, 6, 7, 9, 8][2, 1, 4, 3, 3, 6, 7, 9, 8][1, 1, 4, 3, 5, 6, 7, 9, 8][1, 1, 4, 3, 5, 6, 7, 9, 8][1, 2, 3, 3, 5, 6, 7, 9, 8][1, 2, 3, 3, 5, 6, 7, 9, 8][1, 2, 3, 4, 5, 6, 7, 9, 8][1, 2, 3, 4, 5, 6, 7, 9, 8][1, 2, 3, 4, 5, 6, 7, 9, 8][1, 2, 3, 4, 5, 6, 7, 9, 8][1, 2, 3, 4, 5, 6, 7, 8, 8][1, 2, 3, 4, 5, 6, 7, 8, 8][1, 2, 3, 4, 5, 6, 7, 8, 9]

3. 时间复杂度:

快速排序的时间复杂度: O(nlog(n))

转载地址：http://mfiwi.baihongyu.com/