Python小程序：一行快排

Python一行代码实现快速排序

Let’s go

快速排序采用分而治之的思想。

快速排序是找出一个元素作为基准(pivot),然后对要排序的序列进行分区操作, 使基准左边的元素值都小于基准值, 基准右边的元素值都不小于基准值。使用递归进行快速排序, 将基准左边和右边看做两个要排序的序列, 调整元素正确位置, 排序完成。

待排序的序列L, 如果L的元素个数不大于1, 那么无需排序, 结果仍然是L。
如果L的元素个数大于1, 那么选择任意一个元素作为基准, 比如选择第一个元素a, 把小于a的元素移到a的左边, 大于等于a的元素移到右边, 这样会形成L1, a, L2的序列, L1的元素的值都比a小, L2的元素的值都不小于a。
然后对L1重复进行上述操作, 形成L3, b, L4, a, L2的序列, 对每次生成的左右两个序列递归操作, 直到子序列只有一个元素就停止, 当所有子序列都只有一个元素时排序结束。

在C语言中, 使用递归实现快速排序少说也有几十行, 但是Python中因为有列表推导式, 生成序列非常简单, 快速排序的函数体只需一行！！！

def qsort(L):  
  return L if len(L) <= 1 else qsort([l for l in L[1:] if l < L[0]]) + [L[0]] + qsort([g for g in L[1:] if g >= L[0]])

对于待排序序列L, 如果L的元素个数不大于1, 返回L, 否则返回一个新序列, 该序列由三部分组成, [l for l in L[1:] if l < L[0]] 的意思对于序列L的其他元素 如果比第一个元素L[0]小, 就挑出来, 挑出来的这些元素组成一个新的序列L1, 同理 [g for g in L[1:] if g >= L[0]] 可得元素不小于L[0]的序列L2, 再把三个部分拼接起来, 形成新序列L1, L[0], L2, 然后一直递归调用 qsort(L1) 和 qsort(L2)。

为了测试该快排的性能, 写了个主函数测试, 与系统自带的sort()函数比较, 因为是使用递归实现, 时间复杂度比较高, 几乎是sort的10倍, 在数据量1w级别时看不出什么区别, 在10w和100w级别区别比较明显

# -*- coding: utf-8 -*-
import time
import random
  
def qsort(L):  
  return L if len(L) <= 1 else qsort([l for l in L[1:] if l < L[0]]) + [L[0]] + qsort([g for g in L[1:] if g >= L[0]])
  
if __name__ == '__main__':
  L = list(range(100000))   # 生成一个10万个数的序列, 分别从0到99999
  random.shuffle(L)         # 随机打乱该序列
  temp = L[:]               # 复制该序列
    
  # 对L使用自带的sort, 输出排序时间
  start = time.time()
  L.sort()
  end = time.time()
  print end - start
    
  # 对副本temp使用qsort, 输出排序时间  
  start = time.time()
  qsort(temp)
  end = time.time()
  print end - start

运行结果如下(单位:秒):
1w数据
0.00300002098083
0.0279998779297
    
10w数据
0.0450000762939
0.392999887466
    
100w数据
0.730999946594
5.35800004005