Python中的快排优化

基本快速排序分析

---

以从小到大排序为例

• 选取一个主元（选取方式多样）
• 利用主元，将序列分为两个子序列，左侧都比主元小，右侧都比主元大。
• 对两个子序列重复此操作

快排图示

例如取第一个元素,代码表示如下：

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

---

优化方案

1. 主元的选取
   上面的算法有很大的问题，对于升序或降序序列，效率很差，我优化后的方式是主元取序列首中尾
   三个值取平均数，网上有些取三个值的中值的，我认为没必要，为了效率还要将中值换到首或尾。
2. 序列中可能有一些和主元相等的元素，上面直接将其并入子序列中了，最好是将其和主元聚集
   在一起，子序列缩减幅度也会更快

这样的话定义一个函数：

def getMidNum(list):
    return (list[0] + list[len(list) - 1] + list[len(list)/2])/3
def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = getMidNum(arr)
        return qsort([x for x in arr[0:] if x < pivot]) + \
               [x for x in arr[0:] if x == pivot] + \
               qsort([x for x in arr[0:] if x > pivot])        
            

---

对比

分别构造长度为10000的随机数列表，升序列表，将序列表和等值列表，对比二者的表现

方法\序列	随机	升序	降序	等值
快排	1.3990s	limit exceed	limit exceed	limit exceed
优化	0.6570s	0.9410s	0.9900s	0.0699s