那些搞笑的排序算法
本帖最后由 knismooth 于 2013-12-27 17:32 编辑无聊写了个排序算法演示。
其实网上早就有这样的东西了，而且人写了16种算法还配了声音。
我就是单纯觉得排序算法很搞笑，所以想自己玩玩。
为什么说搞笑，是因为我觉得排序过程可视化以后，就像在给狗（狼？）顺毛。
要考虑用什么样的手法顺的快，顺的狗舒服233333。
当然排序算法还有种用点表示的方法，那个的感觉给我有点像撸管2333333。
首先是冒泡排序。这可能是所有人在学算法时第一个接触的排序算法，甚至是算法。简单，稳定，形象。
当时老师对他的描述就是好像金鱼在吐泡泡，泡泡越往上越大。
冒泡的原理就是把无序区域中能遇到的最大值放到最后面去。
从图中可以看出来，无序部分最长的线总是在最右侧。
动画过程看的话，会有些像编麻花辫。
选排。选择排序，基本原理是把无序区域中最长（最短）的线选择出来，然后放到区域的最后（最前）去。
听描述来说它好像不过是冒泡排序的逆过程。但是实际上因为选择这个动作的原因，让它变成了一个不稳定算法，最好情况下时间复杂度只有n。实际动画演示效果来说，它确实比冒泡快得多。
插排。插入排序，其原理是先把第一个元素当做是有序的数组，然后取出无序区域中的值，插入到这个有序数组中合适的位置上去。可以看出这个图中有序区域并不是那么的平滑，这就是因为有的值还在无序区域中，没有被插入。
从严格的数学意义来说，这个排序在小规模排序上比较优秀，但是效率也只能跟选排打个平手。
不过就我实际动画演示效果来说，这个排序速度远远快于前几种，我还没打开程序他就已经排序完成了。
希尔排序。这个算法又被人叫龟排或者壳排，不过实在是有点冤枉了它的发明人DL.Shell,他只是用自己的名字给这种算法命名而已，跟乌龟没关系。
希尔排序是插排的改进版。插入排序有个特点，就是插入次数越少，效率越高，如果数组一开始就是初步有序的，那么这种排序的效率可以突破天际。依照这个原来，乌龟……哦不，希尔同志想了个办法，先把数组分割成小块，然后使用插排，这样数组就是初步有序的了，然后再对整体插排，使得整体有序。图中可以看出，整个图像被分割成了很多小块有序的区域，就像是毛刺，最后一次插排会把这些毛刺全部捋平。
说是改进版，其实他只是把插排的效率稳定下来了，在小规模排序上效率反而低于插排。在我的动画演示中就能感觉出来。
快排。这个算法被认为是不使用特殊数据结构情况下的终极排序算法。大规模排序表现优异，但是是个不稳定算法。
快排的基本思想是分治，将数组从某一个地方切开，然后对着其中的内容重新进行快排，如此递归下去，直到分割数组到每个端只有1或者2个元素，然后对着2个元素进行比较，放正他们的顺序。
图像特征可以看出，整个空间被分成了好几个块，而每个块都很相似，并且每个块中又被分割出了许多跟他相似的小块。这就是递归的一个特征表现。
这个算法有时候表现很糟糕，问题出在分段点的选取上，所以后来人们发明了随机快排，随机选取一个分段点，利用统计学原理使快排的效率稳定下来。当然同希尔排序一样，稳定下来的效率并不比原始最优效率高，在数组基本有序的情况下还是原始快排更为优秀。
桶排。这种排序是使用了额外的数据结构而达到了让人匪夷所思的效率，它的大概原理和选橙子一样。传送带上有很多大小不一的孔，将孔按从小到大排列好，橙子滚过的时候就会自动被从小到大分装。
放到这个算法里，就是把原始区域分割成几个连续的区间，就跟桶一样。然后把数以此放入其中，最后将几个桶连接起来，整个空间就变成有序的了。
这个算法的图像看起来会跟快排有点像，图像也被分割成很多相似的块。不过这个算法并不是分治的，他不使用递归。之所看上去很像，是因为桶排一开始的分割十分粗略，800个数被分成了8个桶，可是每个桶里面的100个元素还是无序的，这时候就要对它们使用相同的办法进行排序。所以图像表现出来就成了这样。
这个算法的效率是nc，匪夷所思的线性效率，而且他是稳定算法，百万级别的排序在人为控制下可以达到毫秒级别处理完毕。但是就像我刚才说的，它使用了额外的数据结构，空间消耗非常严重，所有排序中我见过的只有它需要考虑空间复杂度。忘记说的一点是，我给这个算法的计算过程加了前面几种算法的100倍延时时间，才使得它的排序过程肉眼可见。。。。。。前面的几种都加的是1ms，这个加的是100ms，而冒泡没有加……
最后还有一种算法叫bogo sort，又叫猴子排序。原理么……………………来自著名的无限猴子算法。有兴趣可以百度一下。
至于效率……我半小时前启动的程序，现在还排着呢。它的最糟时间复杂度是无限大………………
这个学期刚好学了前面三个………剩下的不知道什么时候学啊……
另外:卡尔好厉害的说。 氣泡排序法,對嗎? 話說我在 visual basic 學過了,但現在全忘了{:ml51:} 猴子排序赛高！
那个演示各种算法+配音的视频
看到猴子排序直接喷了出来233 长知识了呢。。。
表示这些排序算法的思想好像现在我正在纠结的排列组合系列故事，尤其是快排，虽然复杂得多吧
最后的那个猴子算法好想笑wwwwwww这才是真正的看运气啊! 好有趣 教练我要学编程
目前只百度了猴子算法从而得到一点新知识。。 看楼主涨知识~ 猴子排序笑cry。 我记得B站专门有这么个视频来着
页:
[1]
2