设为首页 - 加入收藏
广告 1000x90
您的当前位置:三五彩图库香港正 > 布线程序 > 正文

和你一起一步步看懂排序算法的运行过程

来源:未知 编辑:admin 时间:2019-07-22

  本文全长 14237 字,配有 70 张图片和动画,和你一起一步步看懂排序算法的运行过程。

  冒泡排序无疑是最为出名的排序算法之一,从序列的一端开始往另一端冒泡(你可以从左往右冒泡,也可以从右往左冒泡,看心情),依次比较相邻的两个数的大小(到底是比大还是比小也看你心情)。

  首先比较第一个数和第二个数的大小,我们发现 2 比 8 要小,那么保持原位,不做改动。位置还是 8,2,5,9,7 。

  比较第二个数和第三个数的大小,发现 2 比 5 要小,所以位置交换,交换后数组更新为:[ 8,5,2,9,7 ]。

  比较第三个数和第四个数的大小,发现 2 比 9 要小,所以位置交换,交换后数组更新为:[ 8,5,9,2,7 ]

  比较第 4 个数和第 5 个数的大小,发现 2 比 7 要小,所以位置交换,交换后数组更新为:[ 8,5,9,7,2 ]

  下一步,指针再往右移动,发现已经到底了,则本轮冒泡结束,处于最右边的 2 就是已经排好序的数字。

  由于右边的 2 已经是排好序的数字,就不再参与比较,所以本轮冒泡结束,本轮冒泡最终冒到顶部的数字 5 也归于有序序列中,现在数组已经变化成了[ 8,9,7,5,2 ]。

  由于 8 比 7 大,所以位置不变,此时第三轮冒泡也已经结束,第三轮冒泡的最后结果是[ 9,8,7,5,2 ]

  9 和 8 比,位置不变,即确定了 8 进入有序序列,那么最后只剩下一个数字 9 ,放在末尾,自此排序结束。

  冒泡的代码还是相当简单的,两层循环,外层冒泡轮数,里层依次比较,江湖中人人尽皆知。

  冒泡有一个最大的问题就是这种算法不管不管你有序还是没序,闭着眼睛把你循环比较了再说。

  比如我举个数组例子:[ 9,8,7,6,5 ],一个有序的数组,根本不需要排序,它仍然是双层循环一个不少的把数据遍历干净,这其实就是做了没必要做的事情,属于浪费资源。

  针对这个问题,我们可以设定一个临时遍历来标记该数组是否已经有序,如果有序了就不用遍历了。

  选择排序的思路是这样的:首先,找到数组中最小的元素,拎出来,将它和数组的第一个元素交换位置,第二步,在剩下的元素中继续寻找最小的元素,拎出来,和数组的第二个元素交换位置,如此循环,直到整个数组排序完成。

  至于选大还是选小,这个都无所谓,你也可以每次选择最大的拎出来排,也可以每次选择最小的拎出来的排,只要你的排序的手段是这种方式,都叫选择排序。

  第一次选择,先找到数组中最小的数字 2 ,然后和第一个数字交换位置。(如果第一个数字就是最小值,那么自己和自己交换位置,也可以不做处理,就是一个if的事情)

  第二次选择,由于数组第一个位置已经是有序的,所以只需要查找剩余位置,找到其中最小的数字5,然后和数组第二个位置的元素交换。

  插入排序的思想和我们打扑克摸牌的时候一样,从牌堆里一张一张摸起来的牌都是乱序的,我们会把摸起来的牌插入到左手中合适的位置,让左手中的牌时刻保持一个有序的状态。

  那如果我们不是从牌堆里摸牌,而是左手里面初始化就是一堆乱牌呢? 一样的道理,我们把牌往手的右边挪一挪,把手的左边空出一点位置来,然后在乱牌中抽一张出来,插入到左边,再抽一张出来,插入到左边,再抽一张,插入到左边,每次插入都插入到左边合适的位置,时刻保持左边的牌是有序的,直到右边的牌抽完,则排序完毕。

  数组初始化:[ 8,2,5,9,7 ],我们把数组中的数据分成两个区域,已排序区域和未排序区域,初始化的时候所有的数据都处在未排序区域中,已排序区域是空。

  第一轮,从未排序区域中随机拿出一个数字,既然是随机,那么我们就获取第一个,然后插入到已排序区域中,已排序区域是空,那么就不做比较,默认自身已经是有序的了。(当然了,第一轮在代码中是可以省略的,从下标为1的元素开始即可)

  第二轮,继续从未排序区域中拿出一个数,插入到已排序区域中,这个时候要遍历已排序区域中的数字挨个做比较,比大比小取决于你是想升序排还是想倒序排,这里排升序:

  从代码里我们可以看出,如果找到了合适的位置,就不会再进行比较了,就好比牌堆里抽出的一张牌本身就比我手里的牌都小,那么我只需要直接放在末尾就行了,不用一个一个去移动数据腾出位置插入到中间。

  所以说,最好情况的时间复杂度是 O(n),最坏情况的时间复杂度是 O(n2),然而时间复杂度这个指标看的是最坏的情况,而不是最好的情况,所以插入排序的时间复杂度是 O(n2)。

  希尔排序这个名字,来源于它的发明者希尔,也称作“缩小增量排序”,是插入排序的一种更高效的改进版本。

  我们知道,插入排序对于大规模的乱序数组的时候效率是比较慢的,因为它每次只能将数据移动一位,希尔排序为了加快插入的速度,让数据移动的时候可以实现跳跃移动,节省了一部分的时间开支。

  假设计算出的排序区间为 4 ,那么我们第一次比较应该是用第 5 个数据与第 1 个数据相比较。

  调换后的数据为[ 7,2,5,9,8,10,1,15,12,3 ],然后指针右移,第 6 个数据与第 2 个数据相比较。

  如果交换数据后,发现减去区间得到的位置还存在数据,那么继续比较,比如下面这张图,12 和 8 相比较,原地不动后,指针从 12 跳到 8 身上,继续减去区间发现前面还有一个下标为 0 的数据 7 ,那么 8 和 7 相比较。

  当最后一个元素比较完之后,我们会发现大部分值比较大的数据都似乎调整到数组的中后部分了。

  假设整个数组比较长的线 个数据,那么我们的区间肯定是四五十,调整后区间再缩小成一二十还会重新调整一轮,直到最后区间缩小为 1,就是真正的排序来了。

  可能你会问为什么区间要以 gap = gap*3 + 1 去计算,其实最优的区间计算方法是没有答案的,这是一个长期未解决的问题,不过差不多都会取在二分之一到三分之一附近。

  归并字面上的意思是合并,归并算法的核心思想是分治法,就是将一个数组一刀切两半,递归切,直到切成单个元素,然后重新组装合并,单个元素合并成小数组,两个小数组合并成大数组,直到最终合并完成,排序完毕。

  数据量设定的比较少,是为了方便图解,数据量为单数,是为了让你看到细节,下面我画了一张更直观的图可能你会更喜欢:

  我们上面讲过,归并排序的核心思想是分治,分而治之,将一个大问题分解成无数的小问题进行处理,处理之后再合并,这里我们采用递归来实现:

  我们可以发现 merge 方法中只有一个 for 循环,直接就可以得出每次合并的时间复杂度为 O(n) ,而分解数组每次对半切割,属于对数时间 O(log n) ,合起来等于 O(log2n) ,也就是说,总的时间复杂度为 O(nlogn) 。

  关于空间复杂度,其实大部分人写的归并都是在 merge 方法里面申请临时数组,用临时数组来辅助排序工作,空间复杂度为 O(n),而我这里做的是原地归并,只在最开始申请了一个临时数组,所以空间复杂度为 O(1)。

  如果你对空间复杂度这一块不太了解,可以查看小吴之前的数据结构系列文章---冰与火之歌:「时间」与「空间」复杂度 。

  快速排序的核心思想也是分治法,分而治之。它的实现方式是每次从序列中选出一个基准值,其他数依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,然后再对左边和右边的两组数分别选出一个基准值,进行同样的比较移动,重复步骤,直到最后都变成单个元素,整个数组就成了有序的序列。

  (周知:动图里面的大于小于写反,小吴修正重新录制后,上传新动图到微信后台却一直失败)

  快速排序的关键之处在于切分,切分的同时要进行比较和移动,这里介绍一种叫做单边扫描的做法。

  我们随意抽取一个数作为基准值,同时设定一个标记mark 代表左边序列最右侧的下标位置,当然初始为 0 ,接下来遍历数组,如果元素大于基准值,无操作,继续遍历,如果元素小于基准值,则把 mark + 1 ,再将 mark 所在位置的元素和遍历到的元素交换位置,mark 这个位置存储的是比基准值小的数据,当遍历结束后,将基准值与 mark 所在元素交换位置即可。

  另外还有一种双边扫描的做法,看起来比较直观:我们随意抽取一个数作为基准值,然后从数组左右两边进行扫描,先从左往右找到一个大于基准值的元素,将下标指针记录下来,然后转到从右往左扫描,找到一个小于基准值的元素,交换这两个元素的位置,重复步骤,直到左右两个指针相遇,再将基准值与左侧最右边的元素交换。

  快速排序的时间复杂度和归并排序一样,O(n log n),但这是建立在每次切分都能把数组一刀切两半差不多大的前提下,如果出现极端情况,比如排一个有序的序列,如[ 9,8,7,6,5,4,3,2,1 ],选取基准值 9 ,那么需要切分 n - 1 次才能完成整个快速排序的过程,这种情况下,时间复杂度就退化成了 O(n2),当然极端情况出现的概率也是比较低的。

  所以说,快速排序的时间复杂度是 O(nlogn),极端情况下会退化成 O(n2),为了避免极端情况的发生,选取基准值应该做到随机选取,或者是打乱一下数组再选取。

  如果你不了解堆这种数据结构,可以查看小吴之前的数据结构系列文章---看动画轻松理解堆

  如果你了解堆这种数据结构,你应该知道堆是一种优先队列,两种实现,最大堆和最小堆,由于我们这里排序按升序排,所以就直接以最大堆来说吧。

  我们完全可以把堆(以下全都默认为最大堆)看成一棵完全二叉树,但是位于堆顶的元素总是整棵树的最大值,每个子节点的值都比父节点小,由于堆要时刻保持这样的规则特性,所以一旦堆里面的数据发生变化,我们必须对堆重新进行一次构建。

  既然堆顶元素永远都是整棵树中的最大值,那么我们将数据构建成堆后,只需要从堆顶取元素不就好了吗? 第一次取的元素,是否取的就是最大值?取完后把堆重新构建一下,然后再取堆顶的元素,是否取的就是第二大的值? 反复的取,取出来的数据也就是有序的数据。

  既然构建成堆结构了,那么接下来,我们取出堆顶的数据,也就是数组第一个数 9 ,取法是将数组的第一位和最后一位调换,然后将数组的待排序范围 -1。

  现在的待排序数据是[ 3,8,5,2,7 ],我们继续将待排序数据构建成堆。

  取出堆顶数据,这次就是第一位和倒数第二位交换了,因为待排序的边界已经减 1 。

  从堆顶取出来的数据最终形成一个有序列表,重复的步骤就不再赘述了,我们来看一下代码实现。

  计数排序是一种非基于比较的排序算法,我们之前介绍的各种排序算法几乎都是基于元素之间的比较来进行排序的,计数排序的时间复杂度为 O(n + m ),m 指的是数据量,说的简单点,计数排序算法的时间复杂度约等于 O(n),快于任何比较型的排序算法。

  首先,我们找到这组数字中最大的数,也就是 8,创建一个最大下标为 8 的空数组 arr 。

  有一个需求就是当对成绩进行排名次的时候,如何在原来排前面的人,排序后还是处于相同成绩的人的前面。

  解题的思路是对 countArr 计数数组进行一个变形,变来和名次挂钩,我们知道 countArr 存放的是分数的出现次数,那么其实我们可以算出每个分数的最大名次,就是将 countArr 中的每个元素顺序求和。

  我们把原数组[ 2,5,8,2,5,4 ]中的数据依次拿来去 countArr 去找,你会发现 3 这个数在 countArr[3] 中的值是 2 ,代表着排名第二名,(因为第一名是最小的 2,对吧?),5 这个数在 countArr[5] 中的值是 5 ,为什么是 5 呢?我们来数数,排序后的数组应该是[ 2,3,4,5,5,8 ],5 的排名是第五名,那 4 的排名是第几名呢?对应 countArr[4] 的值是 3 ,第三名,5 的排名是第五名是因为 5 这个数有两个,自然占据了第 4 名和第 5 名。

  所以我们取排名的时候应该特别注意,原数组中的数据要从右往左取,从 countArr 取出排名后要把 countArr 中的排名减 1 ,以便于再次取重复数据的时候排名往前一位。

  如果我要排的数据里有 0 呢? int[] 初始化内容全是 0 ,排毛线。

  如果我要排的数据范围比较大呢?比如[ 1,9999 ],我排两个数你要创建一个 int[10000] 的数组来计数?

  对于第一个 bug ,我们可以使用偏移量来解决,比如我要排[ -1,0,-3 ]这组数字,这个简单,我全给你们加 10 来计数,变成[ 9,10,7 ]计完数后写回原数组时再减 10。不过有可能也会踩到坑,万一你数组里恰好有一个 -10,你加上 10 后又变 0 了,排毛线。

  对于第二个 bug ,确实解决不了,如果是[ 9998,9999 ]这种虽然值大但是相差范围不大的数据我们也可以使用偏移量解决,比如这两个数据,我减掉 9997 后只需要申请一个 int[3] 的数组就可以进行计数。

  由此可见,计数排序只适用于正整数并且取值范围相差不大的数组排序使用,它的排序的速度是非常可观的。

  桶排序可以看成是计数排序的升级版,它将要排的数据分到多个有序的桶里,每个桶里的数据再单独排序,再把每个桶的数据依次取出,即可完成排序。

  第三步,对桶中的数据进行单独排序,只有第一个桶中的数量大于 1 ,显然只需要排第一个桶。

  桶当然是一个可以存放数据的集合,我这里使用 arrayList ,如果你使用 LinkedList 那其实也是没有问题的。

  桶的数量我认为设置为原数组的长度是合理的,因为理想情况下每个数据装一个桶。

  数据入桶的映射算法其实是一个开放性问题,我承认我这里写的方案并不佳,因为我测试过不同的数据集合来排序,如果你有什么更好的方案或想法,欢迎留言讨论。

  桶内排序为了方便起见使用了当前语言提供的排序方法,如果对于稳定排序有所要求,可以选择使用自定义的排序算法。

  在额外空间充足的情况下,尽量增大桶的数量,极限情况下每个桶只有一个数据时,或者是每只桶只装一个值时,完全避开了桶内排序的操作,桶排序的最好时间复杂度就能够达到 O(n)。

  比如高考总分 750 分,全国几百万人,我们只需要创建 751 个桶,循环一遍挨个扔进去,排序速度是毫秒级。

  但是如果数据经过桶的划分之后,桶与桶的数据分布极不均匀,有些数据非常多,有些数据非常少,比如[ 8,2,9,10,1,23,53,22,12,9000 ]这十个数据,我们分成十个桶装,结果发现第一个桶装了 9 个数据,这是非常影响效率的情况,会使时间复杂度下降到 O(nlogn),解决办法是我们每次桶内排序时判断一下数据量,如果桶里的数据量过大,那么应该在桶里面回调自身再进行一次桶排序。

  基数排序是一种非比较型整数排序算法,其原理是将数据按位数切割成不同的数字,然后按每个位数分别比较。假设说,我们要对 100 万个手机号码进行排序,应该选择什么排序算法呢?排的快的有归并、快排时间复杂度是 O(nlogn),计数排序和桶排序虽然更快一些,但是手机号码位数是11位,那得需要多少桶?内存条表示不服。

  其实它的思想很简单,不管你的数字有多大,按照一位一位的排,0 - 9 最多也就十个桶:先按权重小的位置排序,然后按权重大的位置排序。

  感谢你看到了这里,希望看完这篇文章能让你清晰的理解平时最常用的十大排序算法。

  文章出处:【微信号:rgznai100,微信公众号:AI科技大本营】欢迎添加关注!文章转载请注明出处。

  刚刚录制了一个fpga开发流程的视频,该视频为投石问路,主要是想听听大家对于小梅哥在录制视频时需要注意的内容以及希望系列

  只是想知道是否有任何示例代码或应用说明.... 问候 安东尼 以上来自于谷歌翻译 以下为原文 Just wondering ...

  嗨, 我正在开发基于AS3993,AKA ST25RU3993的产品。我一直在使用FEMTO模块(由AMS)来测试我的应用程序代码。...

  你好, 我是M24LR04E的初学者。 我使用X-NUCLEO-NFC02a1和NUCLEO-L053R8。 我在True Studio中使用S...

  当代码执行停止时,有没有办法阻止计时器?当我通过代码时,我被卡在毫秒计时器中断中,一遍又一遍地通过它。当我对设备进行编程...

  我在PIC24FJ256GB110上有一个连接到外部中断的线路。我需要让系统在这条线的前缘和下降边都打断我。这是用来从外部从属设...

  大家好, 我是来自意大利的学生,我正在开展一个测试平台是STM8S-Discovery板的项目。 我开发了我的项目没有问题,但现在...

  我下载了代码配置器,但是zip文件包含一个NETBEN文件,我不能打开它来安装配置器。 以上来自于百度翻译 &...

  我正在使用为E3631A提供的示例代码“Diode Test”。 我能够成功地向E3640A发送命令。 但是,在查询中,例如“Meas:Cu...

  你好 , 我是NFC的新手我正在使用Android st25sdk我需要使用iso15693命令读/写fom /到NFC标签。我的例子是读取电池电...

  我写这本书的本意其实是为了给自己做参考,在我想用 IDAPython 的时候能够随时找到一些关于 I....

  本人的的板子是up6410,是一个小众化的板子,不过这篇文章主要介绍的是移植,很少会涉及具体的代码内容,所以大家基本可以拿来作...

  1.软件测试的定义: 官方释义:a.用来促进鉴定软件的正确性、完整性、安全性和质量的过程。b.是一种....

  第三方代码的使用是企业能够快速高效建立新系统、新产品、新平台的关键因素,能大幅度缩短开发周期,减少人....

  一位来自加拿大的大四学霸,开发了一款”Deep TabNine“代码补全工具,实现了这一大胆的想法。

  为了能够更准确地构建模型,现在机器学习应用通常要处理大量的数据并生成多种特征,这已成为必要的。而 P....

  在第9章我们将介绍如何加载预训练网络(该网络是Keras提供的五个预训练网络之一),研究图像输入网络....

  .验证码的一个功能就是来规避机器的自动操作,所以我们需要通过轨迹来判断这个拖动过程是真实的人还是机器....

  他们很少用奇技淫巧。他们写的代码质量高,并清楚知道代码会如何演化,对整个代码结构胸有成竹。他们最多编....

  本文档的主要内容详细介绍的是龙格-库塔法的MATLAB代码及含义的详细资料说明。

  我们将会选择使用一些 vue 周边的库 vue-cli,vue-router,vue-resourc....

  请注意,这里的Style中用到了min-height,这个和height是不同的,min-heigh....

  本文档的主要内容详细介绍的是如何进行Strong手机模板首页默认风格配置的教程免费下载。

  电阻器颜色编码使用彩色波段轻松识别电阻器的电阻值及其百分比容差有许多不同类型的电阻器可用于电气和电子....

  机器人模型是如何创建的?需要工程师一行一行敲写代码吗?每一次模型创建都需要重新开始吗?创建过程总是艰....

  不论是对于团队还是企业,TRAINS都能将所有内容记录在一个中央服务器中,并实现可视化和出处,这样生....

  本文档的主要内容详细介绍的是Git的使用说明四个点详细说明包括了:一、创建版本库 ,二、VS2017....

  创建游戏不再是程序员的专利,普通游戏玩家也可以随心所欲地创造自己的游戏王国。

  6月13日,中国证监会和上海市人民政府联合举办了上海证券交易所科创板开板仪式。

  公司在研发嵌入式产品过程中,产品的功能会不断的添加和更新,产品的型号也会越来越多。这时产品的软件研发....

  本文档的主要内容详细介绍的是实验python进行图像识别的示例代码资料免费下载。

  近日,有开发人员用PyTorch实现了基本的RL算法,比如REINFORCE, vanilla ac....

  本文档的主要内容详细介绍的是Visual Basic程序设计教程完整课件PPT资料免费下载包括了:第....

  顺序扫描法:对5个文档依次查找,包含目标字段的文档就记录下来,最后查找的结果可能是在2,3文档中,这....

  我们经常会遇到比如需要输入密码,当你输错密码的时候,你不希望退出这个系统,而是重新输入密码;又或者是....

  分布式锁一般有三种实现方式:1. 数据库乐观锁;2. 基于Redis的分布式锁;3. 基于ZooKe....

  本文档的主要内容详细介绍的是DHT11温湿度传感器的应用程序代码免费下载。

  本文档的主要内容详细介绍的是行为和结构及表现分离的CSS选项卡的代码免费下载。

  微软代码评审是一种被广泛采用的工程实践。成千上万的工程师认为这是一个伟大的最佳实践。大多数高绩效团队....

  GitHub宣布推出了几款新的安全工具和功能,旨在帮助开发者保护代码的安全。

  指针和数组都是C语言的精髓所在,对于很多C程序员来说,如果你问这样一个问题:数组和指针有什么区别?他....

  本文档的主要内容详细介绍的是使用单片机进行24C02记忆开机次数代码的详细资料说明。

  ESLint组件会使用本地ESLint和配置规则来查找JavaScript代码中的常见模式问题,以便....

  随着摩尔定律(Moore’s Law)的放缓,以及单个处理器速度的加速放缓,并行化是提高性能的关键。....

  许多LabVIEW新手并不完全了解“数据流”执行背后的概念,而这些概念却是LabVIEW编程的基础。....

  Shader,是运行在GPU上的程序,中文称为着色器。它的主要用途是对三维物体进行着色处理,对光与影....

  据外媒报道,迪拜网络安全公司SpiderSilk的安全研究员莫萨布·侯赛因(Mossab Husse....

  Github发布重大功能性更新GitHub Package Registry

  在处理一个依赖于软件包的项目时,重要的是要信任、理解软件包的代码,并与构建项目的社区建立联系。在社区....

  为了训练FUNIT,我们使用来自一组对象类(例如各种动物物种的图像)中的图像,称为源类(source....

  本文档的主要内容详细介绍的是Android的UI界面设计的详细代码资料免费下载。

  G代码是数控程序中的指令。一般都称为G指令。使用G代码可以实现快速定位、逆圆插补、顺圆插补、中间点圆....

  本文主要测试MySQL执行update语句时,针对与原数据(即未修改)相同的update语句会在My....

  据GitLab安全总监Kathy Wang回应道,“我们根据Stefan Gabos昨天提交的赎金票....

  Anders Hejlsberg表示,他遵循了他所接触过的所有编程语言的共同原则,即“做某件事情的方....

本文链接:http://thacba.net/buxianchengxu/696.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top