「数据结构」C语言排序方法——快速排序详解
yuyutoo 2024-10-23 16:43 27 浏览 0 评论
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
算法步骤：
1 从数列中挑出一个元素，称为 "基准"（pivot）。
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大地摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归（recursive）的把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
C代码的实现如下：
下面开始单步分析，这里用一个数组的数据来分析
首先将0作为比较的基准，由于右边所有的数据都比0大，所以数据不做 移动。 接下来将8作为比较基准，从最右边开始和8比较。 此时6比8小，将6移动到8前面，其他数据依次后移。
接着再将2和8比较，2比8小，继续将2移动到8前面，其他的数据依次后移。
这样将8小的数据移动到8的前面，比8大的数据在8后面保持不变。移动完成后如下：
接下来比较的基准变为数字6，将比6小的数据移动到6前面。 从最右边开始查找，找到1比6小，将1移动到6前面。
然后继续依次寻找比6小的数字，移动到6的前面，移动完成后如下：
然后比较的基准变为数字5，从最右边开始寻找比5小的数移动到5前面。查找到的数据为2。
依次查找其他比5小的数据，移动完成后如下：
到这里可以看到数据排序已经完成了。 整体运行流程如下：
下面测试一下最坏情况下的排序情况
可以看到最坏情况下排序的次数并没有增多，反而感觉还减少了。 再看一下最好情况下的排序情况：
最好情况下数据也要进行比较9次。
下来随机生成一个包含10000个数字的数组，测试下执行时间。
可以看到对10000个数字排序需要的时间为120ms。
下面用一张动图来演示一下快速排序的过程：
另外，对现在我们的大多数朋友来说还是学编程技术最重要！栽一棵树最好的时间是十年前，其次是现在。对于准备学习编程的小伙伴，如果你想更好地提升你的编程核心能力（内功）不妨从现在开始！
编程学习书籍分享：
编程学习视频分享：
整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）
欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！
想学习C/C++编程，或者对编程感兴趣的话可以【私信】笔者粉丝群和大家一起交流~
- 上一篇：C语言数据结构2 c语言数据结构代码
- 下一篇：C语言数据结构8 c语言数据结构代码
相关推荐
- 自卑的人容易患抑郁症吗?（自卑会导致抑郁吗）
-
Filephoto[Photo/IC]Lowself-esteemmakesusfeelbadaboutourselves.Butdidyouknowthatovert...
- 中考典型同(近)义词组（同义词考题）
-
中考典型同（近）义词组...
- BroadcastReceiver的原理和使用（broadcast-suppression）
-
一、使用中注意的几点1.动态注册、静态注册的优先级在AndroidManifest.xml中静态注册的receiver比在代码中用registerReceiver动态注册的优先级要低。发送方在send...
- Arduino通过串口透传ESP 13板与java程序交互
-
ESP13---是一个无线板子，配置通过热点通信Arduino通过串口透传ESP13板与java程序交互...
- zookeeper的Leader选举源码解析（zookeeper角色选举角色包括）
-
作者：京东物流梁吉超zookeeper是一个分布式服务框架，主要解决分布式应用中常见的多种数据问题，例如集群管理，状态同步等。为解决这些问题zookeeper需要Leader选举进行保障数据的强一致...
- 接待外国人英文口语（接待外国友人的英语口语对话）
-
接待外国人英文口语询问访客身份： MayIhaveyourname,please? 请问您贵姓？ Whatcompanyareyoufrom? 您是哪个公司的？ Could...
- 一文深入理解AP架构Nacos注册原理
-
Nacos简介Nacos是一款阿里巴巴开源用于管理分布式微服务的中间件，能够帮助开发人员快速实现动态服务发现、服务配置、服务元数据及流量管理等。这篇文章主要剖析一下Nacos作为注册中心时其服务注册与...
- Android面试宝典之终极大招（android面试及答案）
-
以下内容来自兆隆IT云学院就业部，根据多年成功就业服务经验，以及职业素养课程部分内容，归纳总结：18.请描述一下Intent和IntentFilter。Android中通过Intent...
- 除了Crontab，Swoole Timer也可以实现定时任务的
-
一般的定时器是怎么实现的呢？我总结如下：1.使用Crontab工具，写一个shell脚本，在脚本中调用PHP文件，然后定期执行该脚本；2.ignore_user_abort()和set_time_li...
- Spark源码阅读:DataFrame.collect 作业提交流程思维导图
-
本文分为两个部分：作业提交流程思维导图关键函数列表作业提交流程思维导图...
- 使用Xamarin和Visual Studio开发Android可穿戴设备应用
-
搭建开发环境我们需要做的第一件事情是安装必要的工具。因此，你需要首先安装VisualStudio。如果您使用的是VisualStudio2010，2012或2013，那么请确保它是一个专业版本或...
- Android开发者必知的5个开源库（android 开发相关源码精编解析）
-
过去的时间里，Android开发逐步走向成熟，一个个与Android相关的开发工具也层出不穷。不过，在面对各种新鲜事物时，不要忘了那些我们每天使用的大量开源库。在这里，向大家介绍的就是，在这个任劳任怨...
- Android事件总线还能怎么玩?（android实现事件处理的步骤）
-
顾名思义，AndroidEventBus是一个Android平台的事件总线框架，它简化了Activity、Fragment、Service等组件之间的交互，很大程度上降低了它们之间的耦合，使我们的代码...
- Android 开发中文引导-应用小部件
-
应用小部件是可以嵌入其它应用（例如主屏幕）并收到定期更新的微型应用视图。这些视图在用户界面中被叫做小部件，并可以用应用小部件提供者发布。可以容纳其他应用部件的应用组件叫做应用部件的宿主（1）。下面的截...
欢迎 你 发表评论:
- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了，如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
推荐7个模板代码和其他游戏源码下载的网址
-
其实模版网站在开发工作中很重要，推荐几个参考站给大家
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
-
- 自卑的人容易患抑郁症吗?（自卑会导致抑郁吗）
- 中考典型同(近)义词组（同义词考题）
- WPF 消息传递简明教程（wpf messagebox.show）
- BroadcastReceiver的原理和使用（broadcast-suppression）
- Arduino通过串口透传ESP 13板与java程序交互
- zookeeper的Leader选举源码解析（zookeeper角色选举角色包括）
- 接待外国人英文口语（接待外国友人的英语口语对话）
- 一文深入理解AP架构Nacos注册原理
- Android面试宝典之终极大招（android面试及答案）
- 除了Crontab，Swoole Timer也可以实现定时任务的
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)