大家好，又见面了，我是你们的朋友全栈君。
基本快速排序分析
以从小到大排序为例
* 选取一个主元（选取方式多样）
* 利用主元，将序列分为两个子序列，左侧都比主元小，右侧都比主元大。
* 对两个子序列重复此操作
例如取第一个元素,代码表示如下：
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 |
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/128902.html原文链接：https://javaforall.net
