基本快速排序分析
以从小到大排序为例
- 选取一个主元（选取方式多样）
- 利用主元，将序列分为两个子序列，左侧都比主元小，右侧都比主元大。
- 对两个子序列重复此操作
快排图示
例如取第一个元素,代码表示如下：
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])
优化方案
- 主元的选取
上面的算法有很大的问题，对于升序或降序序列，效率很差，我优化后的方式是主元取序列首中尾
三个值取平均数，网上有些取三个值的中值的，我认为没必要，为了效率还要将中值换到首或尾。 - 序列中可能有一些和主元相等的元素，上面直接将其并入子序列中了，最好是将其和主元聚集
在一起，子序列缩减幅度也会更快
这样的话定义一个函数：
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 |
