首先感谢朋友们对第一篇文章的鼎力支持,感动中.......
今天说的是选择排序,包括“直接选择排序”和“堆排序”。
话说上次“冒泡排序”被快排虐了,而且“快排”赢得了内库的重用,众兄弟自然眼红,非要找快排一比高下。
这不今天就来了两兄弟找快排算账。
1.直接选择排序:
先上图:
说实话,直接选择排序最类似于人的本能思想,比如把大小不一的玩具让三岁小毛孩对大小排个序,
那小孩首先会在这么多玩具中找到最小的放在第一位,然后找到次小的放在第二位,以此类推。。。。。。
,小孩子多聪明啊,这么小就知道了直接选择排序。羡慕中........
对的,小孩子给我们上了一课,
第一步: 我们拿80作为参照物(base),在80后面找到一个最小数20,然后将80跟20交换。
第二步: 第一位数已经是最小数字了,然后我们推进一步在30后面找一位最小数,发现自己最小,不用交换。
第三步:........
最后我们排序完毕。大功告成。
既然是来挑战的,那就5局3胜制。
堆排序:
要知道堆排序,首先要了解一下二叉树的模型。
下图就是一颗二叉树,具体的情况我后续会分享的。
那么堆排序中有两种情况(看上图理解):
大根堆: 就是说父节点要比左右孩子都要大。
小根堆: 就是说父节点要比左右孩子都要小。
那么要实现堆排序,必须要做两件事情:
第一:构建大根堆。
首先上图:
首先这是一个无序的堆,那么我们怎样才能构建大根堆呢?
第一步: 首先我们发现,这个堆中有2个父节点(2,,3);
第二步: 比较2这个父节点的两个孩子(4,5),发现5大。
第三步: 然后将较大的右孩子(5)跟父节点(2)进行交换,至此3的左孩子堆构建完毕,
如图:
第四步: 比较第二个父节点(3)下面的左右孩子(5,1),发现左孩子5大。
第五步: 然后父节点(3)与左孩子(5)进行交换,注意,交换后,堆可能会遭到破坏,
必须按照以上的步骤一,步骤二,步骤三进行重新构造堆。
最后构造的堆如下:
第二:输出大根堆。
至此,我们把大根堆构造出来了,那怎么输出呢?我们做大根堆的目的就是要找出最大值,
那么我们将堆顶(5)与堆尾(2)进行交换,然后将(5)剔除根堆,由于堆顶现在是(2),
所以破坏了根堆,必须重新构造,构造完之后又会出现最大值,再次交换和剔除,最后也就是俺们
要的效果了,
发现自己兄弟被别人狂殴,,堆排序再也坐不住了,决定要和快排干一场。
同样,快排也不甘示弱,谁怕谁?
堆排序此时心里很尴尬,双双被KO,心里想,一定要捞回面子,一定要赢,
于是堆排序提出了求“前K大问题”。(就是在海量数据中找出前几大的数据),
快排一口答应,小意思,没问题。
双方商定,在2w随机数中找出前10大的数:
求前K大的输出结果:
最后堆排序赶紧拉着直接选择排序一路小跑了,因为求前K大问题已经不是他原本来的目的。
ps: 直接选择排序的时间复杂度为:O(n^2)
堆排序的时间复杂度:O(NlogN)
相关推荐
算法系列15天速成——第六天-五大经典查找【下】,算法数据结构 五大常用算法
算法系列15天速成——第四天-五大经典查找【上】 五大常用算法
算法系列15天速成——第五天-五大经典查找【中】,算法数据结构 五大常用算法
五大经典查找【下】 算法系列15天速成——第五天 五大经典查找【中】 算法系列15天速成——第四天 五大经典查找【上】 算法系列15天速成——第三天 七大经典排序【下】 算法系列15天速成——第二天 七大经典排序【中】...
算法系列15天速成 数据结构 算法 树、图、堆栈、队列
计算机系的教材,算法导论————————————————————————————————
今天是大结局,说下“图”的最后一点东西,“最小生成树“和”最短路径
今天说下最后一种树,大家可否知道,文件压缩程序里面的核心结构,核心算法是什么?或许你知道,他就运用了赫夫曼树
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867026
算法之NlogN排序算法(csdn)————程序
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867321
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1871731
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867491
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1868188
今天说的是选择排序,包括“直接选择排序”和“堆排序”
代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码...
在第一版的基础上新加了对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结篇,方便大家复习,合适作为笔试面试前的复习资料。
思维进化算法优化BP神经网络——非线性函数拟合.zip
垃圾回收GC经典算法(csdn)————程序