Python3排序算法06 - 快速排序

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1398 次阅读

Synopsis: 快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 算法介绍

快速排序(Quick Sort)又称分区交换排序(partition-exchange sort),简称快排。于1961年由Tony Hoare首次发表,它是一种比较排序,是不稳定的排序算法,这意味着不会保留相等排序项的相对顺序

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists):

  1. 首先从原始序列中,挑选一个基准(pivot)元素,可以选择第1个元素、最后1个元素或中间元素
  2. 将小于基准值的元素放在基准的左边,将大于基准值的元素放在基准的右边,基准处于数列的中间位置,称为一趟分区(partition)操作。相当于将基准元素放置到它应该在的位置上,左边序列全比它小,右边序列全比它大,暂时不用管左右序列是否有序排列
  3. 对小于基准值的子序列和大于基准值的子序列重复进行步骤1和步骤2,直到子序列只有1个元素时(肯定是有序的啦)

2. Python实现

2.1 算法1

假设序列的第1个元素为基准(pivot),使用列表生成式(List Comprehensions)来查找比基准值小或大的元素序列:

def quick_sort(L):
    '''使用 '列表生成式(List Comprehensions)' 查找比 '基准(pivot)' 小或大的元素序列'''
    n = len(L)
    if n <= 1:
        return L

    pivot_value = L[0]
    lesser = [item for item in L[1:] if item <= pivot_value]
    greater = [item for item in L[1:] if item > pivot_value]

    return quick_sort(lesser) + [pivot_value] + quick_sort(greater)


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    sorted = quick_sort(L1)
    print('After: ', sorted)

# Output:
Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

也可以将上述排序函数改写为一行:

quick_sort = lambda L: L if len(L) <= 1 else quick_sort([i for i in L[1:] if i <= L[0]]) + [L[0]] + quick_sort([j for j in L[1:] if j > L[0]])

测试通过:

quick_sort = lambda L: L if len(L) <= 1 else quick_sort([i for i in L[1:] if i <= L[0]]) + [L[0]] + quick_sort([j for j in L[1:] if j > L[0]])

if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    sorted = quick_sort(L1)
    print('After: ', sorted)

# Output:
Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

压力测试:

from timeit import timeit

def test():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]
    quick_sort(L)

def quick_sort(L):
    n = len(L)
    if n <= 1:
        return L

    pivot_value = L[0]
    lesser = [item for item in L[1:] if item <= pivot_value]
    greater = [item for item in L[1:] if item > pivot_value]

    return quick_sort(lesser) + [pivot_value] + quick_sort(greater)


print('Quick sort function run 1000 times, cost: ', timeit('test()', 'from __main__ import test', number=1000), 'seconds.')

# Output:
Quick sort function run 1000 times, cost:  0.2375717348850251 seconds.

2.2 算法2

def quick_sort(L, first, last):
    '''使用 '递归(recursive)' 的方式,实现快速排序算法
    first 和 last 都表示序列的下标
    '''
    if first < last:  # 左、右子序列只剩一个元素时,退出递归 (first == last)
        pivot_index = partition(L, first, last)  # 返回 '基准' 值的最终正确位置的下标
        quick_sort(L, first, pivot_index-1)
        quick_sort(L, pivot_index+1, last)


def partition(L, first, last):
    '''一次快速排序的分区过程,将选定的 '基准(pivot)' 放到正确的位置上,小于它的值都在它的左边,大于它的值都在它的右边
    first 和 last 都表示序列的下标
    '''
    pivot_value = L[first]  # 可以选择序列的第1个元素、中间元素或最后1个元素为 '基准' 值,这里选择第1个

    leftmark = first + 1  # leftmark 游标从左向右查找比 '基准' 值大的元素
    rightmark = last  # rightmark 游标从右向左查找比 '基准' 值小的元素

    done = False
    while not done:
        # 当 leftmark 找到比 '基准' 值大的元素后,停下来
        while leftmark <= rightmark and L[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        # 当 rightmark 找到比 '基准' 值小的元素后,停下来
        while L[rightmark] >= pivot_value and rightmark >= leftmark:
            
                                
                            
  • ppiero
  • __
  • 1507850469
  • 郑孝章
  • lidongcheng88
  • Loner1024
  • RAINLFF
  • ppiero
  • xmyang
  • nokey
  • heqi
  • 闫珺
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法06 - 快速排序

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.