快速排序

简介:

针对冒泡排序我们进行一次优化,就引进了快速排序在此基础上进行优化

基本思想:

  • 任取一个记录(如第一个)作为 枢轴或支点,设其关键字为pivotkey。

  • 在一趟排序后,所有比它小的记录一律前放,比它大的记录一律后放,形成左右两个子表,将枢轴放在分界处的位置;

  • 然后,分别对各子表重新选择枢轴,并依此规则调整,直到每个子表的元素只剩一个,排序完成。

具体操作

(1)附设两个指针low和high,初始时分别指向表的上限和下限,设枢轴记录的关键字为pivotkey(第一趟时,low=1,high=L.length)

(2)从表的最右侧位置,依次向左搜索找到第一个关键字小于pivotkey的记录和枢轴记录交换。具体操作:当

low<high时,若high所指纪录的关键字大于等于pivotkey,则向左移动指针high(即–high),否则high所指纪

录与枢轴纪录交换。

(3)然后再从表的左侧位置,依次向右搜索第一个关键字大于pivotkey的记录和枢轴记录交换。具体操作:当low<high时,若low所指记录的关键字小等于pivotkey,则向右移动指针low(即++low),否则low所指记录与枢轴记录交换。

(4)重复(2)(3)步骤,直到low和high相等为止,此时low或high的位置即为枢轴在此趟排序中的最终位置,原表被分成两个子表。

这里写图片描述
这里写图片描述

  • 每一趟的子表的形成是采用从两头向中间交替式逼近法;

  • 由于每趟中对各子表的操作都相似,可采用递归算法。

    int Partition(SqList &L,int low,int high)
    {
        L.r[0]=L.r[low];
        pivotkey=L.r[low].Key;
        while(low<high)
    {
         while(low<high&&L.r[high].Key>=pivotkey)--high;
         L.r[low]=L.r[high];
     while(low<high&&L.r[low].key<pivotkey)++low;
    }
     L.r[high]=L.r[low];
         return low;
    }
    void QSort(SqList &L,int low,int high)
    {
        if(low<high)
    {
        pivotloc=Partition(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
    }
    }
        void QuickSort()
        {
        QSort(L,1,L.length);
    }
    

算法分析可以证明,平均计算时间是O(nlog2n)。

实验结果证明:就平均计算时间而言,快速排序是我们所学习的所有内排序方法中最好的一个。

快速排序是递归的,需要有一个栈存放每层递归调用时参数(新的low和high)。

最大递归调用层次数与递归树的深度一致,因此要求存储开销为O(log2n)。

最好:划分后,左侧右侧子序列的长度相同

最坏:从小到大排好序,递归树成单支树,每次划分只得到一个比上一次少一个对象的子序列,必须经过n-1
趟才能把所有对象定位,而且第i趟需要经过n-i次关键码比较才能找到第i个对象的安放位置

时间效率:O(nlog2n)—-每趟确定的元素呈指数增加

空间效率:O(log2n)—–递归要用到栈空间

稳定性:不稳定—–可选任一元素为支点。

目录
相关文章
|
存储 安全 Java
Spring Boot读取配置文件
Spring Boot读取配置文件
|
C++ 计算机视觉
Visual Studio新项目快速配置已有项目中编译好的C++第三方库的方法
Visual Studio新项目快速配置已有项目中编译好的C++第三方库的方法
367 1
|
传感器 数据采集 数据可视化
探究物联网技术的核心知识点:传感器、嵌入式系统和数据分析
探究物联网技术的核心知识点:传感器、嵌入式系统和数据分析
423 0
|
机器学习/深度学习 运维 Dubbo
全国首个政企采购云平台:政采云基于 Dubbo 的混合云跨网方案实践
Apache Dubbo 是一款易用、高性能的 WEB 和 RPC 框架,同时为构建企业级微服务提供服务发现、流量治理、可观测、认证鉴权等能力、工具与最佳实践。
423 57
全国首个政企采购云平台:政采云基于 Dubbo 的混合云跨网方案实践
|
监控 Java 测试技术
Spring Boot和XXL-Job:高效定时任务管理
Spring Boot和XXL-Job:高效定时任务管理
986 0
|
机器学习/深度学习 编解码 人工智能
|
前端开发
如何实现一个循环显示超长图片的控件
*本篇文章已授权微信公众号 guolin_blog (郭霖)独家发布 某次被问到如何实现一个滚筒状的控件,就是可以将一张很长的图片沿着Y轴无限旋转,如下图所示: 大概就是这个意思,当时还不知道图片可以裁剪,想不出整个流程怎么搞,后来得知Bitmap有裁剪功能,才想到这个功能怎么实现,花了一下午时间整了一下有了成果。
1115 0
|
8天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1192 4
|
7天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
950 12
|
6天前
|
机器学习/深度学习 物联网
Wan2.2再次开源数字人:Animate-14B!一键实现电影角色替换和动作驱动
今天,通义万相的视频生成模型又又又开源了!Wan2.2系列模型家族新增数字人成员Wan2.2-Animate-14B。
536 11