笑了。。。

哈喽,大家好,我是不务正业的吴师兄,今天给大家找点乐子,分享几个好玩的排序算法。

睡眠排序

根据CPU的调度算法实现的,对一组数据进行排序,不能存在负数值,这个数是多大,那么就在线程里睡眠它的10倍再加10,不是睡眠和它的数值一样大的原因是,当数值太小时,误差太大,睡眠的时间不比输出的时间少,那么就会存在不正确的输出结果。

猴子排序

随机打乱数组,检查是否排好序,若是,则输出,否则再次打乱,再检查…最佳情况O(n),平均O(n*n!),最坏可执行直到世界的尽头。

一个有趣的理论:一只猴子随机敲打打字机键盘,如果时间足够长,总是能打出特定的文本,比如莎士比亚全集。

面条排序

首先去买一捆面条,我喜欢手擀面。找到数组中最大和最小的两个数(O(n)),让最大的数对应一根很长的面条,最小的数对应一根很短的面条。

重新遍历数组,每遇到一个数,就取一根面条,把它切成这个数对应的长度,可以得到n根面条。这里的数与面条长度的对应可以用一个严格递增的函数来映射。

接下来,一手握住这n根面条,稍微用力,别握太紧,在平放的桌面上直立着放下,让所有的面条底端接触到桌面。另一只手平行于桌面,从面条上方缓慢往下移动,每当这只手碰到一根面条,移走它,并把对应的数输出到结果数组中,直到移走全部面条。

鸡尾酒排序

鸡尾酒排序,也就是定向冒泡排序,鸡尾酒搅拌排序,搅拌排序(也可以视作选择排序的一种变形),涟漪排序,来回排序或快乐小时排序,是冒泡排序的一种变形。

此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

排序过程:

  • 先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端
  • 再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端
  • 以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束

1、第一轮操作( 8 和 1 交换 )

2、第二轮操作 ( 从序列右边开始遍历 )

3、第三轮操作 ( 从左向右比较和交换 )

在这一轮操作中,没有元素位置交换,证明已经有序,排序结束。

对比冒泡排序,鸡尾酒排序只需要 3 轮操作就可以完成排序。

地精排序

“Gnome 排序(地精排序),起初由 Hamid Sarbazi-Azad 于 2000 年提出,并被称为 stupid 排序,后来被 Dick Grune 描述并命名为 “地精排序” 。 ”

地精排序和插入排序类似,除了移动一个元素到最终的位置,是通过交换一系列的元素实现,就像冒泡排序一样。概念上十分简单,不需要嵌套循环。

时间复杂度为O(n^2),但是如果初始数列基本有序,时间复杂度将降为O(n)。实际上 Gnome 算法可以和插入排序算法一样快。

平均运行时间为O(n^2)。

将无序数列:6,2,4,1,5,使用地精排序使其从小到大排序。

通过设计标识 i = 0 ,然后从头开始判断,什么时候 ( i < 4 ) 不成立,什么时候排序结束。

这里的核心点就是如何控制 i 的值。

1、第一轮操作「i = 0」

先让 i 自增 1 ,达到值为 1 才开始比较 :

交换前 [ 6 2 4 1 ] 『 i = 0 』

交换后 [ 6 2 4 1 ] 『 i = 1 』

第二轮操作「i = 1」

比较 6 和 2 ,发生交换,只要发生交换 i 就减 1 。

交换前 [ 6 2 4 1 ]『 i = 1 』

交换后 [ 2 6 4 1 ]『 i = 0 』

第三轮操作「i = 0」

i 变成 0 了,啥也不干,自增变成 1 再说。

交换前 [ 2 6 4 1 ]『 i = 0 』

交换后 [ 2 6 4 1 ]『 i = 1 』

第四轮操作「i = 1」

比较 2 和 6 ,不交换,只要不要换就自增 1。

交换前 [ 2 6 4 1 ]『 i = 1 』

交换后 [ 2 6 4 1 ]『 i = 2 』

第五轮操作「i = 2」

比较 6 和 4 ,发生交换,只要发生交换 i 就减 1 。

交换前 [ 2 6 4 1 ]『 i = 2 』

交换后 [ 2 4 6 1 ]『 i = 1 』

第六轮操作「i = 1」

比较 2 和 4 ,不交换,只要不要换就自增 1 。

交换前 [ 2 6 4 1 ]『 i = 1 』

交换后 [ 2 4 6 1 ]『 i = 2 』

第七轮操作「i = 2」

比较 4 和 6 ,不交换,只要不要换就自增 1 。

交换前 [ 2 4 6 1 ]『 i = 2 』

交换后 [ 2 4 6 1 ]『 i = 3 』

第八轮操作「i = 3」

比较 6 和 1 ,发生交换,只要发生交换 i 就减 1 。

交换前 [ 2 4 6 1 ]『 i = 3 』

交换后 [ 2 4 1 6 ]『 i = 2 』

第九轮操作「i = 2」

比较 4 和 1 ,发生交换,只要发生交换 i 就减 1 。

交换前 [ 2 4 1 6 ]『 i = 2 』

交换后 [ 2 1 4 6 ]『 i = 1 』

第十轮操作「i = 1」

比较 2 和 1 ,发生交换,只要发生交换 i 就减 1 。

交换前 [ 2 1 4 6 ]『 i = 1 』

交换后 [ 1 2 4 6 ]『 i = 0 』

第十一轮操作「i = 0」

啥也不干,先让 i 自增1,达到值为 1 才开始真正的比较。

『 i = 1 』时,比较 1 和 2 ,不交换,只要不交换就自增 1 。 『 i = 2 』时,比较 2 和 4 ,不交换,只要不交换就自增 1 。 『 i = 3 』时,比较 4 和 6 ,不交换,只要不交换就自增 1 。 『 i = 4 』时,表达式 ( i < n ) 不成立,排序结束。

顺序输出为 [ 1 2 4 6 ]。

你学会了么。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-07-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 这代码注释太好笑了吧!

    代码注释的作用,不需要对程序员解释了。有时在查看他人代码,能看到一些令人不禁大笑的注释。比如:

    CSDN技术头条
  • 傲腾这么厉害?QLC闪存笑了!

    傲腾(Optane)是Intel在存储器方面的重量级产品。其采用3D Xpoint存储非易失介质来存储数据。3D Xpoint的一大特点就是延迟更加接近SDRA...

    冬瓜哥
  • 看完Java的动态代理技术——Pythoner笑了

    Java的动态代理常用来包装原始方法调用,用于增强或改写现有方法的逻辑,它在Java技术领域被广为使用,在阿里的Sofa RPC框架序列化中你能看到它的身影,H...

    老钱
  • 日期居然用字符串保存?我笑了

    我发现数据库有些日期居然用字符串保存?于是跟几个小伙伴讨论了关于数据库的日期应该要怎么保存的问题,其实我一直都建议直接用数值保存时间戳,为什么我要这么建议呢?

    张乘辉
  • 程序员大型甩锅现场,太搞笑了!

    TSW
  • 太搞笑了,小朋友都能看懂的HTTPS!

    相信大家或多或少都了解一点 HTTPS 了,但是可能有不少新人对它的作用和原理一知半解。本文就通过漫画的形式讲解 HTTPS 的作用,希望能让你一解心头之恨惑。

    张晓衡
  • 携程去哪儿在一起,百度地图笑了

    互联网正经历着史上最剧烈的『板块运动』,在资本力量的驱动之下,不同大陆正在合并、联合。10月26日,这一运动来到了旅游业:携程和去哪儿达成换股协议,在线旅游行业...

    罗超频道
  • 营销必备神器?看过的老板都笑了

    2018年以来,小程序一直处在风口浪尖的位置,BAT争先发布了各自的小程序。微信小程序更是作为社交小程序一直火热不减,更是很多人都认为微信小程序是电商和普通商户...

    微宝阁
  • 人类发现外星人信号?别开玩笑了

    昨天有媒体报道,天文学家发现了宇宙深处的“神秘”无线电信号,并且在不断重复。如果把它转成声音,听起来是这样的:

    量子位
  • 边缘计算将取代云计算?别开玩笑了

    任何人都知道,物联网并不是一个玩笑,而且它确实是云的一个组成部分。对于物联网来说有一个关键的问题,就是如何从大量的设备中获取数据。思科系统预测,到2020年,云...

    静一
  • 机器人会模仿人类微笑了,但我总觉得这笑容……

    哥伦比亚大学(Columbia Engineering)创意机器实验室(Creative Machines Lab)的研究人员一直对机器人与人类之间的互动感兴趣...

    量子位
  • 当面试官问我Mybatis初始化原理时,我笑了

    对于任何框架而言,在使用前都要进行一系列的初始化,MyBatis也不例外。本章将通过以下几点详细介绍MyBatis的初始化过程。

    Bug开发工程师
  • 当面试官问我Mybatis初始化原理时,我笑了

    来源:blog.csdn.net/luanlouis/article/details/37744073

    Java团长
  • 面试官让我讲下线程的 WAITING 状态,我笑了

    面试官Q:你讲下线程状态中的WAITING状态,什么时候会处于这个状态?什么时候离开这个状态?

    芋道源码
  • 面试官问,你使用过命令模式吗?我笑了!

    在软件设计中,我们经常需要向某些对象发送请求,但是并不知道请求的接收者是谁,也不知道被请求的操作是哪个,我们只需在程序运行时指定具体的请求接收者即可。此时,可以...

    sanshengshui
  • 美国出台无人机新规:粉丝笑了!快递业哭了!

    镁客网
  • FAA不同意无人机送货,亚马逊哭了,京东笑了…

    近日,美国联邦航空管理局FAA颁布了首部专门针对小型无人机的管理法则“Part107” ,并将于8月末生效。“Part107”适用于在美国领空内飞行的,重量低于...

    机器人网
  • 笑了,面试官问我知不知道异步编程的Future。

    文本主要分享这个 future 的调用方式,不讲 Dubbo 框架,这里只是一个引子。

    why技术
  • 面试官问我:创建线程有几种方式?我笑了

    多线程在面试中基本上已经是必问项了,面试官通常会从简单的问题开始发问,然后再一步一步的挖掘你的知识面。

    烟雨星空

扫码关注云+社区

领取腾讯云代金券