0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

C语言排序中快速排序的技巧

C语言编程学习基地 来源:C语言编程学习基地 作者:C语言编程学习基地 2021-07-29 15:14 次阅读

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

算法步骤:

1 从数列中挑出一个元素,称为 “基准”(pivot)。

2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3 递归(recursive)的把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

C代码的实现如下:

613a930c-edfd-11eb-a97a-12bb97331649.png

下面开始单步分析,这里用一个数组的数据来分析

6155b786-edfd-11eb-a97a-12bb97331649.png

首先将0作为比较的基准,由于右边所有的数据都比0大,所以数据不做 移动。接下来将8作为比较基准,从最右边开始和8比较。此时6比8小,将6移动到8前面,其他数据依次后移。

6170fe9c-edfd-11eb-a97a-12bb97331649.png

接着在将2和8比较,2比8小,继续将2移动到8前面,其他的数据依次后移。

618a70ac-edfd-11eb-a97a-12bb97331649.png

这样将8小的数据移动到8的前面,比8大的数据在8后面保持不变。移动完成后如下:

61a3b332-edfd-11eb-a97a-12bb97331649.png

接下来比较的基准变为数字6,将比6小的数据移动到6前面。从最右边开始查找,找到1比6小,将1移动到6前面。

61bf9af2-edfd-11eb-a97a-12bb97331649.png

然后继续依次寻找比6小的数字,移动到6的前面,移动完成后如下:

61d63dde-edfd-11eb-a97a-12bb97331649.png

然后比较的基准变为数字5,从最右边开始寻找比5小的数移动到5前面。查找到的数据为2。

61f18e0e-edfd-11eb-a97a-12bb97331649.png

依次查找其他比5小的数据,移动完成后如下:

620c66ac-edfd-11eb-a97a-12bb97331649.png

到这里可以看到数据排序已经完成了。整体运行流程如下:

下面测试一下最坏情况下的排序情况

62398f06-edfd-11eb-a97a-12bb97331649.png

可以看到最坏情况下排序的次数并没有增多,反而感觉还减少了。在看一下最好情况下的排序情况:

62dcc02c-edfd-11eb-a97a-12bb97331649.png

最好情况下数据也要进行比较9次。

6322e912-edfd-11eb-a97a-12bb97331649.png

下来随机生成一个包含10000个数字的数组,测试下执行时间。

可以看到对10000个数字排序需要的时间为120ms。

634a06aa-edfd-11eb-a97a-12bb97331649.png

另外,对现在我们的大多数朋友来说还是学编程技术最重要!栽一棵树最好的时间是十年前,其次是现在。对于准备学习编程的小伙伴,如果你想更好的提升你的编程核心能力(内功)不妨从现在开始!

编辑:jq

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • C语言
    +关注

    关注

    180

    文章

    7604

    浏览量

    136762

原文标题:【数据结构】C语言排序方法——快速排序详解!

文章出处:【微信号:cyuyanxuexi,微信公众号:C语言编程学习基地】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    时间复杂度为 O(n^2) 的排序算法

    作者:京东保险 王奕龙 对于小规模数据,我们可以选用时间复杂度为 O(n2) 的排序算法。因为时间复杂度并不代表实际代码的执行时间,它省去了低阶、系数和常数,仅代表的增长趋势,所以在小规模数据情况下
    的头像 发表于 10-19 16:31 1150次阅读
    时间复杂度为 O(n^2) 的<b class='flag-5'>排序</b>算法

    TMS320LF240x DSP的C语言和汇编代码快速入门

    电子发烧友网站提供《TMS320LF240x DSP的C语言和汇编代码快速入门.pdf》资料免费下载
    发表于 10-18 10:14 0次下载
    TMS320LF240x DSP的<b class='flag-5'>C</b><b class='flag-5'>语言</b>和汇编代码<b class='flag-5'>快速</b>入门

    TPS54120排序和跟踪

    电子发烧友网站提供《TPS54120排序和跟踪.pdf》资料免费下载
    发表于 10-10 10:54 0次下载
    TPS54120<b class='flag-5'>排序</b>和跟踪

    手把手教你排序算法怎么写

    新记录插入。以{3,0,9,8,2}无序表按升序排列为例,有序表是一个虚拟的顺序表:1.插入排序刚开始,有序表没有数据,因此直接插入3即可。{3}2.插入0的时候要
    的头像 发表于 06-04 08:03 687次阅读
    手把手教你<b class='flag-5'>排序</b>算法怎么写

    具有先进排序和输出裕度的输入同步降压控制器TPS40101数据表

    电子发烧友网站提供《具有先进排序和输出裕度的输入同步降压控制器TPS40101数据表.pdf》资料免费下载
    发表于 04-22 10:26 0次下载
    具有先进<b class='flag-5'>排序</b>和输出裕度的<b class='flag-5'>中</b>输入同步降压控制器TPS40101数据表

    具有先进排序和输出裕度的输入同步降压控制器TPS40100数据表

    电子发烧友网站提供《具有先进排序和输出裕度的输入同步降压控制器TPS40100数据表.pdf》资料免费下载
    发表于 04-17 10:59 0次下载
    具有先进<b class='flag-5'>排序</b>和输出裕度的<b class='flag-5'>中</b>输入同步降压控制器TPS40100数据表

    3-A、3.3/5V输入、可调开关稳压器,具有自动跟踪TM排序功能PTH04000W数据表

    电子发烧友网站提供《3-A、3.3/5V输入、可调开关稳压器,具有自动跟踪TM排序功能PTH04000W数据表.pdf》资料免费下载
    发表于 04-17 09:32 0次下载
    3-A、3.3/5V输入、可调开关稳压器,具有自动跟踪TM<b class='flag-5'>排序</b>功能PTH04000W数据表

    Linux的sort命令介绍

    前面的空格字符 -c, --check, --check=diagnose-first 只检查文件是否已排序,不进行排序 -C, --check=quiet, --check=sil
    发表于 04-08 07:16

    支持 ACPI 的 10 轨电源排序器和监视器UCD9090A数据表

    电子发烧友网站提供《支持 ACPI 的 10 轨电源排序器和监视器UCD9090A数据表.pdf》资料免费下载
    发表于 03-29 09:12 0次下载
    支持 ACPI 的 10 轨电源<b class='flag-5'>排序</b>器和监视器UCD9090A数据表

    用FPGA实现双调排序的方法(2)

    典型的排序算法包括冒泡排序、选择排序、插入排序、归并排序快速
    的头像 发表于 03-21 10:28 638次阅读
    用FPGA实现双调<b class='flag-5'>排序</b>的方法(2)

    FPGA实现双调排序算法的探索与实践

    双调排序(BitonicSort)是数据独立(Data-independent)的排序算法,即比较顺序与数据无关,特别适合并行执行。在了解双调排序算法之前,我们先来看看什么是双调序列。
    发表于 03-14 09:50 645次阅读
    FPGA实现双调<b class='flag-5'>排序</b>算法的探索与实践

    想听听48和大对数光缆的排序

    48芯光缆和大对数光缆都是光缆的一种,它们的区别在于芯数不同。48芯光缆指的是光缆包含48根光纤,而大对数光缆则是指光缆芯数超过了48芯。 在实际的光缆应用,不同芯数的光缆需要
    的头像 发表于 03-12 10:44 614次阅读

    C语言实现经典排序算法概览

    冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。
    的头像 发表于 02-25 12:27 447次阅读
    <b class='flag-5'>C</b><b class='flag-5'>语言</b>实现经典<b class='flag-5'>排序</b>算法概览

    vb语言c++语言的区别

    Microsoft开发的一种面向对象的事件驱动编程语言。它的设计目标是简化编程过程,让初学者也能快速上手。与之相比,C++语言是一种通用的、面向对象的编程
    的头像 发表于 02-01 10:20 2290次阅读

    工业自动化编程语言演变的方向!

    最近在美国的一次技术会议上,ISA下属automation.com网站的资深编辑与Arlen Nipper(Cirrus Link Solutions的首席技术官和MQTT的共同发明者)交谈时,问及自动控制编程语言的演变,请他对自动化和控制工程师目前使用的编程
    的头像 发表于 01-05 17:02 1111次阅读
    工业自动化编程<b class='flag-5'>语言</b>演变的方向!