快排优化Python表示「建议收藏」

基本快速排序分析以从小到大排序为例*选取一个主元(选取方式多样)*利用主元,将序列分为两个子序列,左侧都比主元小,右侧都比主元大。*对两个子序列重复此操作例如取第一个元素,代码表示如下:defqsort(arr):iflen(arr)<=1:returnarrelse:pivot=arr[0]r

大家好,又见面了,我是你们的朋友全栈君。

基本快速排序分析


以从小到大排序为例
* 选取一个主元(选取方式多样)
* 利用主元,将序列分为两个子序列,左侧都比主元小,右侧都比主元大。
* 对两个子序列重复此操作

快排图示

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

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
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/128902.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • makefile 常用函数notdir、wildcard、patsubst

    notdir,wildcard和patsubst是makefile中几个有用的函数,以前没留意过makefile中函数的用法,今天稍微看看~ 1、makefile里的函数makefile里的函数使用,和取变量的值类似,是以一个‘$’开始,然后是一个括号里面是函数名和需要的参数列表,多个变量用逗号隔开,像这样return=$(functionname arg1,

  • Vue集成activity工作流

    Vue集成activity工作流情景:由于activiti与系统应用主题样式出入较大,协商后决定将activiti的editor-app放在前台。ps:内网开发,无图,凭记忆摘取主要内容。步骤:将activiti放在public即静态目录下。 通过iframe在相应的前台工作流界面引入activiti的model.html(最外层的主html,名字可能有出入)。 mounted时将this,即vuecompo…

  • php sql filestream,FileStream应用

    php sql filestream,FileStream应用FileStream:文件流,为了解决大对象BLOB(BinaryLargeObjects)的存储问题.对于大对象存储,并且不受2GB的限制.以往有两种方式:(1)存储在数据库里面,这种方式一般使用image字段,或者varbinary(max)来做,好处是可以统一备份,但实际效率较低;(2)存储在文件系FileStream:文件流,为了解决大对象BLOB(BinaryLargeOb…

  • 2021美赛A题解题思路(Fungi)

    2021美赛A题解题思路(Fungi)准时赴约。等待开题中……

  • 二进制数的运算方法

    二进制数的运算方法1.二进制数的算术运算二进制数的算术运算包括:加、减、乘、除四则运算,下面分别予以介绍。(1)二进制数的加法根据“逢二进一”规则,二进制数加法的法则为:0+0=00+1=1+0=11+1=0 (进位为1)1+1+1=1(进位为1)例如:1110和1011相加过程如下:(2)二进制数的减法根据“借一有二”的规则,二进制数减法的法则为:

  • WPF TextBox模仿PasswordBox的密码显示功能

    WPF TextBox模仿PasswordBox的密码显示功能WPFTextBox显示密码,模仿PasswordBox的功能

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号