快排优化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)


相关推荐

  • 数据挖掘的预测建模_数据挖掘建模培训

    数据挖掘的预测建模_数据挖掘建模培训数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。听起来比较抽象,我们举个例子。傍晚小街路面上沁出微雨后的湿润,和煦的细风吹来,抬头看看天边的晚霞,嗯,明天又是一个好天气。走到水果摊旁,挑了个根蒂蜷缩、敲起来声音浊响的青绿西瓜,心里期待着享受这个好瓜。由路面微湿、微风、晚霞得出明天是个好天气。根蒂蜷缩、敲声浊响、色泽青绿推断出这是个好瓜,显然,我们是根据以往的经验来对未来或未知的事物做出预测。人可以根据经验对未来进行

  • UpdatePanel简单用法

    UpdatePanel简单用法ScriptManager和UpdatePanel控件联合使用可以实现页面异步局部更新的效果。其中的UpdatePanel就是设置页面中异步局部更新区域,它必须依赖于ScriptManager存在,因为ScriptManger控件提供了客户端脚本生成与管理UpdatePanel的功能。几个重要的属性:   ScriptManager控件的EnablePartialRendering属性:t

  • html 简单表格代码「建议收藏」

    html 简单表格代码「建议收藏」&lt;!DOCTYPEhtml&gt;&lt;html&gt; &lt;head&gt; &lt;title&gt;&lt;/title&gt; &lt;/head&gt; &lt;body&gt; &lt;tablestyle="withd:600px"border="1"&gt; &lt;capti

  • httprunner(4)录制生成测试用例[通俗易懂]

    httprunner(4)录制生成测试用例[通俗易懂]前言写用例之前,我们应该熟悉API的详细信息。建议使用抓包工具Charles或AnyProxy进行抓包。har2case我们先来了解一下另一个项目har2case他的工作原理就是将当前主流的抓

  • http与https的区别与联系_http状态码

    http与https的区别与联系_http状态码HTTP与HTTPS握手的那些事

  • 亚马逊服务器购买_电商平台用什么服务器

    亚马逊服务器购买_电商平台用什么服务器Siteground主机空间怎么样?很多国内的小伙伴可能对siteground主机空间比较陌生,感觉不如bluehost或者Godaddy名气大,实际上siteground在国外是一家非常有名气和实力的美国主机服务商,也是wordpress、Drupal、Jommla这三家知名建站程序一致推荐的主机商。我们蓝鲨网络使用siteground也好多年,最近几年也有非常多的客户选购了他家的主机,这几年使用下来最明显的感觉就是稳定、速度快、客服解决问题的技术水平都比较高。siteground套餐配置区别首先

发表回复

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

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