商务服务
【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序
2025-01-02 13:57

==冒泡排序(Bubble Sort==也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序

直接返回就好

 
 
  1. 冒泡排序是一种非常容易理解的排序

  2. 时间复杂度:O(N^2)

  3. 空间复杂度:O(1)

  4. 稳定性:稳定

  5. 什么时候最快
    当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

  6. 什么时候最慢
    当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止

📌思路一(Hoare版

步骤为

  1. 选取基准值

  2. 从数组右->左找到比基准值小于或等于的值的下标

  3. 从数组右->左找到比基准值大于或等于的值的下标

  4. 交换这两下标的值

  5. 继续执行二操作,直到操作2与操作3相遇

  6. 将基准值放在相遇位置

如下图所示

📌思路二(挖坑法

步骤为

  1. 选取基准值后,记录下基准值,假设该下标为空,相当于是个“坑”

  2. 从右->左找小于或等于基准值的值,就将该数放入坑中,然后该下标变为新的坑

  3. 从左->右找小于或等于基准值的值,就将该数放入坑中,然后该下标变为新的坑

  4. 回到步骤2继续执行,直到操作2与操作3所找数相同

  5. 将记录下的基准值放回坑里

📌思路三(前后指针

 
 

📌规模较小时的优化

每次递归的时候,数据都是再慢慢变成有序的

当数据量少且趋于有序的时候,我们可以直接使用插入排序进行优化

 

📌三数取中法

如果在选取基数时我们发现如果基数一边总是没有数,代码的执行次数会增加很多

所以我们的解决方法为
选取数组第一个数、中间的数、和最后一个数,进行比较

三数中间的数作为每次的基数

寻找中间数代码如下

 

使用如下

 
 

实现思路

  • 建立一个栈

  • 先让一组数据的起点入栈

  • 再让一组数据的终点出栈

  • 然后两次出栈,分别作为该数据的起点与终点

  • 然后经过我们上面所写的方法进行排序后

  • 再将两组数据进行入栈

  • 以此循环直到栈为空

🚩代码实现

 
 
  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

  2. 空间复杂度:O(logN)

  3. 稳定性:不稳定

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4. 重复步骤 3 直到某一指针达到序列尾

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

 
 
 
 
  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。

  2. 时间复杂度:O(N*logN)

  3. 空间复杂度:O(N)

  4. 稳定性:稳定

外部排序:排序过程需要在磁盘等外部存储进行的排序

前提:内存只有 1G,需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序

  1. 先把文件切分成 200 份,每个 512 M

  2. 分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以

  3. 进行 2路归并,同时对 200 份有序文件做归并过程,最终结果就有序了

    以上就是本篇文章【【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序】的全部内容了,欢迎阅览 ! 文章地址:https://sicmodule.kub2b.com/news/14694.html
     栏目首页      相关文章      动态      同类文章      热门文章      网站地图      返回首页 企库往资讯移动站 https://sicmodule.kub2b.com/mobile/ , 查看更多   
最新文章
手机贴膜硬核科普,一分钟搞懂8种手机膜的区别手机钢化膜「手机贴膜硬核科普,一分钟搞懂8种手机膜的区别」
创作立场声明:文中列举商品仅为示范作用,与品牌无关。说起手机贴膜,想必大家并不陌生,很多人拿到手机后的第一件事,就是贴膜
你以为它死了,其实它复活了,诺基亚手机回归带来十个疑问高颜值手机「你以为它死了,其实它复活了,诺基亚手机回归带来十个疑问」
  2008年1月16日,德国波鸿,在一次员工示威期间,一位诺基亚公司的女员工落泪。你以为它死了,其实它复活了,是的,说的就是
华为折叠手机2023新款价格 华为最新款手机折叠华为新款手机「华为折叠手机2023新款价格 华为最新款手机折叠」
折叠手机是智能手机的一种造型,柔性AMOLED屏幕是折叠手机的突破关键。寰宇舷窗,探索未来独创寰宇舷窗设计,以探索之姿洞见未⁠
139手机邮箱注册(139手机号邮箱注册)
  关于《139手机邮箱注册》的文章  在当今信息化社会,电子邮件已成为人们日常生活和工作中不可或缺的一部分。而手机邮箱因
信息门户手机信息「信息门户」
我校信息门户于2019年1月上线,与南京大学APP互为移动端服务补充,为师生提供在线服务、消息提醒、推文宣传等服务功能。 微信搜
手机能一直开着录音吗 手机一直开着录音行吗【详解】手机录音「手机能一直开着录音吗 手机一直开着录音行吗【详解】」
  能一直开着录音,但是要保证电量和储存空间的充足。一旦录音的储存空间被占满,录音就会停止,保证电量充足,可以边充边录音
张蔷属于昨天,更属于“明天”(音乐节)v i v o 手机「张蔷属于昨天,更属于“明天”(音乐节)」
张蔷,中国内地流行音乐代表人物,传奇天才女歌手,80年代中国流行文化偶像符号,21世纪迪斯科回潮的新女皇。 从小深受从事音乐
2k14手机(2k14手机版中文版下载)
  《2K14手机》:超越视觉的极致体验  在当今科技飞速发展的时代,手机已经成为了我们生活中不可或缺的一部分。而《2K14手机
适合情侣玩的手机游戏前五名 有适合两个人玩的游戏吗情侣手机「适合情侣玩的手机游戏前五名 有适合两个人玩的游戏吗」
游戏还是两个人一起玩有意思,特别是情侣之间,不但能娱乐,还能增进俩人之间的亲密感情。还有异地恋的情侣们,每天只能依靠煲电
创新之城,非凡园区!星海红领巾访园区展示中心v i v o 手机「创新之城,非凡园区!星海红领巾访园区展示中心」
创新之城 非凡园区红领巾寻访苏州工业园区展示中心 这里的街道宽敞整洁,很少见到密如蛛网的电线和凌乱的街边小店; 这里的马路