大家好,又见面了,我是你们的朋友全栈君。
基本快速排序分析
以从小到大排序为例
* 选取一个主元(选取方式多样)
* 利用主元,将序列分为两个子序列,左侧都比主元小,右侧都比主元大。
* 对两个子序列重复此操作
例如取第一个元素,代码表示如下:
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 |
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/128902.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...