1. 算法介绍
快速排序（Quick Sort）分区交换排序（partition-exchange sort）快排快速排序分治法（Divide and conquer）基准（pivot）分区（partition）基准2.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