Python3排序算法06 - 快速排序

  • 原创
  • Madman
  • /
  • 2018-09-16 16:02
  • /
  • 0
  • 95 次阅读

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:
            rightmark = rightmark - 1

        if rightmark < leftmark:  # 如果 leftmark 和 rightmark 交错而过了,说明 '基准' 值的正确位置已经找到了
            done = True
        else:  # 如果 leftmark 和 rightmark 还没有交错,则交换它们查找到的元素值
            L[leftmark], L[rightmark] = L[rightmark], L[leftmark]

    # 如果 leftmark 和 rightmark 交错而过了,说明 '基准' 值的正确位置已经找到了,设置 done = True
    # 将 '基准' 值放到正确的位置上,即 rightmark 最后一次所在的位置,交换它们的值即可
    L[first], L[rightmark] = L[rightmark], L[first]

    return rightmark  # 返回 '基准' 值的最终正确的下标,用于划分左右两个子序列


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

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

分析过程:

第1次分区操作,首先选择54作为基准(pivot)

Quick Sort 01

定义两个游标,leftmark从左向右查找比基准值大的元素,没找到就继续往右,直到找到时就停止; rightmark从右向左查找比基准值小的元素,没找到就继续往左,直到找到时就停止。当它们都找到时,再交换leftmark所在元素值和rightmark所在元素值。当leftmarkrightmark交错而过时(rightmark < leftmark),表示整个序列都查找完了,再将基准(pivot)值和rightmark所在元素值交换即可:

Quick Sort 02

此时,比基准值大的元素全部被移到了基准的右边(leftmark的作用),比基准小的元素全部被移到了基准的左边(rightmark的作用):

Quick Sort 03

再递归地对左右子序列进行同样的分区操作即可!

压力测试:

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, 0, len(L)-1)

def quick_sort(L, first, last):
    if 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_value = L[first]

    leftmark = first + 1
    rightmark = last

    done = False
    while not done:
        while leftmark <= rightmark and L[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        while L[rightmark] >= pivot_value and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            done = True
        else:
            L[leftmark], L[rightmark] = L[rightmark], L[leftmark]

    L[first], L[rightmark] = L[rightmark], L[first]

    return rightmark


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.3112104501085645 seconds.

2.3 算法3

算法导论中的分区操作只使用一层循环,依次比较基准值和整个序列,将小于基准值的元素放到左边,而基准值最后肯定就放置在左子序列的最后一个元素的后边即可:

def quick_sort(L, first, last):
    '''使用 '递归(recursive)' 的方式,实现快速排序算法
    first 和 last 都表示序列的下标
    '''
    if 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 都表示序列的下标
    '''
    smaller_index = first - 1  # index of smaller element (the last smaller element)
    pivot_value = L[last]  # takes last element as pivot

    for i in range(first, last):
        # If current element is smaller than or equal to pivot
        if L[i] <= pivot_value:
            # increment index of smaller element
            smaller_index += 1
            L[smaller_index], L[i] = L[i], L[smaller_index]

    # places the pivot element at its correct position (behind the last smaller element)
    L[smaller_index + 1], L[last] = L[last], L[smaller_index + 1]
    return smaller_index + 1  # return the index of pivot element


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

# 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, 0, len(L)-1)

def quick_sort(L, first, last):
    if 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):
    smaller_index = first - 1
    pivot_value = L[last]

    for i in range(first, last):
        if L[i] <= pivot_value:
            smaller_index += 1
            L[smaller_index], L[i] = L[i], L[smaller_index]

    L[smaller_index + 1], L[last] = L[last], L[smaller_index + 1]
    return smaller_index + 1

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.2525986459125311 seconds.

2.4 算法4

非递归方式实现的快速排序算法:

def quick_sort(L, left, right):
    '''使用 '迭代(iterative)' 的方式,实现快速排序算法
    first 和 last 都表示序列的下标
    '''
    temp_stack = []
    temp_stack.append((left, right))

    # main loop to pop and push items until stack is empty
    while temp_stack:
        left, right = temp_stack.pop()
        pivot_index = partition(L, left, right)
        # if items in the left of the pivot, push them to the stack
        if pivot_index - 1 > left:
            temp_stack.append((left, pivot_index-1))
        # if items in the right of the pivot, push them to the stack
        if pivot_index + 1 < right:
            temp_stack.append((pivot_index+1, right))


def partition(L, first, last):
    '''一次快速排序的分区过程,将选定的 '基准(pivot)' 放到正确的位置上,小于它的值都在它的左边,大于它的值都在它的右边
    first 和 last 都表示序列的下标
    '''
    smaller_index = first - 1  # index of smaller element (the last smaller element)
    pivot_value = L[last]  # takes last element as pivot

    for i in range(first, last):
        # If current element is smaller than or equal to pivot
        if L[i] <= pivot_value:
            # increment index of smaller element
            smaller_index += 1
            L[smaller_index], L[i] = L[i], L[smaller_index]

    # places the pivot element at its correct position (behind the last smaller element)
    L[smaller_index + 1], L[last] = L[last], L[smaller_index + 1]
    return smaller_index + 1  # return the index of pivot element


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

# 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, 0, len(L)-1)

def quick_sort(L, left, right):
    temp_stack = []
    temp_stack.append((left, right))

    while temp_stack:
        left, right = temp_stack.pop()
        pivot_index = partition(L, left, right)

        if pivot_index - 1 > left:
            temp_stack.append((left, pivot_index-1))

        if pivot_index + 1 < right:
            temp_stack.append((pivot_index+1, right))

def partition(L, first, last):
    smaller_index = first - 1
    pivot_value = L[last]

    for i in range(first, last):
        if L[i] <= pivot_value:
            smaller_index += 1
            L[smaller_index], L[i] = L[i], L[smaller_index]

    L[smaller_index + 1], L[last] = L[last], L[smaller_index + 1]
    return smaller_index + 1


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.27604121551193633 seconds.

3. 性能

3.1 时间复杂度

  • 最坏时间复杂度: O(n^2)
  • 最优时间复杂度: O(n log n)
  • 平均时间复杂度: O(n log n)

3.2 空间复杂度

O(n) auxiliary (naive); O(log n) auxiliary (Sedgewick 1978)

3.3 稳定性

它是不稳定的排序算法:

Quick Sort 04

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

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法06 - 快速排序

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录