请选择 进入手机版 | 继续访问电脑版
很久之前有过一次面试,被问到一个问题,能不能写一个冒泡排序?说实话,尽管在这之前曾经写过不少比这个更加复杂的处理逻辑,但很悲剧的是我当时真不知道什么是冒泡排序。。。只知道如果让我排序某段混乱序列,能很快搞定就是了,最后的结果显而易见,我被赤裸裸的鄙视了。。。(连个性能最差的冒泡排序思维都不会,要你何用= =),第二天回去,看了啥是排序,真的捶胸了半天,尼玛名字叫得那么好听,原来是这个。。。

    小插曲...其实作为一名前端,人家说搞好炫酷的界面,做好交互,熟悉各种框架就行了。也许吧,可能还是觉得自己比较笨,想找点算法,稍微提高下自己的思维。也从一个笨人的角度,描绘下我眼中看到的那隐隐约约的轮廓。

    简单的排序算法基本是下面这几种,其中的话冒泡排序,选择排序,插入排序是性能最差,实际应用基本不用但也是最简单,能提高你算法信心的几个小排序方式。

算法入门篇:简单的排序算法-1.jpg

    下面的话,我们一个个来实现,假如我们要让[1, 2, 32, 23, 321, 45, 8, 90, 227, 99]从小到大排列。
    既然要排列,我们第一反应肯定是比较,大的放后边小的放前边,对吧,两两进行比较。
1、冒泡排序
    先拿第1第2个数比较,谁大谁后面,接着第2个跟第3个,还是谁大谁后面,继续第3第4,第4第5。。。这样进行了一轮之后,你是不是可以很肯定,最后的那个数一定是最大的?接下来混乱的序列就少了一位了对吧?就继续剩下的序列继续上面的一轮。而你仔细想一想这个过程,12,    23,    34,...有没有种演唱会现场一波波人浪冒出来的感觉?嗯,没有错,这就是冒泡,像一块软绵绵的地毯,里面有一颗玻璃珠在滚动,滚着滚着这个地毯就有序了。= =嗯,这就是冒泡排序。下面看看它的代码是怎样。
算法入门篇:简单的排序算法-2.jpg
2、选择排序
    上面的是最简单的排序了,人的第一直觉就能产生的一种解决问题的思路。但是呢?思维肯定是不断进步的,不可能一直停滞不前的,为什么呢?人浪排序不是很好吗?额不对,冒泡排序不是还不错嘛?简单直观,但是你要知道,有些人的脑回路不一定如此直观,他们解决问题的思路是这样的:

    他觉得,我每次比较后符合要求的都去交换,有些处于中间值的,不是要不断的被交换?不是很浪费时间?我能不能选出这段序列中最大的那个数,然后放到最后边?

    答案是肯定的,怎么做呢?既然是序列,代码中是数组,那有一个下标,我先把第一个数据给存起来,这个数不断的从第1项比到最后一项,当谁的值比他大时,他就把他的值存起来,这样一轮过后,它拿到了最大值,这时候就把选出的这个数,仍最后。接下来那个第二大的仍这个最后的前面一项,一直到完成整个序列。这样这种通过不断选出剩余项最大值的方法叫做选择排序。

    一起看看它的代码是怎样的吧:
算法入门篇:简单的排序算法-3.jpg

    这种选择排序,虽说没有了交换的过程,但又多了赋值的过程,实际上并不比冒泡强哪去,也还是那样,理论上的性能能稍微好那么一丢丢,基本可以忽略不计。
3、插入排序
    跟冒泡和选择同一时期的,还有一个插入排序,插入排序的方式更加的简单,你想一个问题,假如你现在手上多了一个空的数组,那你会怎样排序?是不是先把第一个放到空数组后,往后拿过来的数都跟这个新数组的各个数比较,插入到某两个数(只需注意大的在你后面,小的在你前面就OK)之间,但是呢,实际上,新创建一个数组的开销是不算小的,没理由一个简单的算法都要这样做,所以可以这样:
    抽出第2个数,这样就变成了前半段(你的新数组),跟后半段(原来的大数组),这样不断的把你后半段的数,插入到前半段,前半段大的就往后挪腾位置给新数插入,对吧?是不是也可以实现你想要的?一起看看这个插入排序是怎样实现的吧。
算法入门篇:简单的排序算法-4.jpg
    上面这3种排序,你是不是代码中要有两个for循环,而且是完全的遍历,一步步走的,对吧?一个用于每一轮的比较(这时候只是进行了某一个数的比较,或者说确定了某一个数在整个数组中它所处的位置),一个用于遍历整个数组,把每个成员都拿出来遛一遛。对吧,那就是n²,也就是时间复杂度O(n²)(个人理解,不一定非常准确,但个人认为还是比较好理解的,不至于说得很复杂)
    既然有了前人的摸索,后人站在这个巨人的肩膀上,那要创新创造一些更先进的思维模式来解决这样的问题,就简单很多,那他们这些的思维又是怎样的呢?

4、希尔排序
    比如说我们在说到无论是冒泡还是插入排序,有没有注意到“一个个的往后挪”这样的字眼?为什么要一个个的挪呢?能不能一大段一大段的挪?打个比方,如果排序一个1~100的数组(原序列是100,99,98...1),这个时候100是在第1位,光排完100这个数你就得挪99次,得调用上面的swap方法99次,但比如说把这个一个个挪切换成一半一半的挪,比如第一个数100跟51比较后交换然后99跟52比较,是不是就非常大的迈了一大步?这些迈完后,再把间隔变成25,再来迈,虽说可能迈偏对吧?没事最后做一个步伐为1的修正就好了。而这,就是鼎鼎有名的希尔排序。

    看一下希尔排序是怎么实现的哈:
算法入门篇:简单的排序算法-5.jpg

5、归并排序
    看了以前上面一个个的挪实在太费劲了,我要比较,我不挪,我直接就拿出来,分成小组,每个小组自己先弄成有序的,再汇总,这样这种分而治之思想的实际上就是归并排序。它的核心排序点在哪呢?你分治就分治嘛,怎么分?又怎么治?就是我为神马用这个排序,这个数据通过这个方法过一下就变有序了?核心就在于小组——这个小组的成员最多只有2个,比如说数组的长度是8,就分成了4个2,7就分成3个2跟1个1,多个数我们一眼排不出序来,两个总可以吧?没错,这就是分。那怎么治呢?我们看下下面比如说我现在A,B两个小组已经完成了他们内部的排序(他们的长度都是4)

    A            B

1568        2479
手工画,别嫌弃 = =


算法入门篇:简单的排序算法-6.jpg

    那一起看看它是怎么实现的吧:
算法入门篇:简单的排序算法-7.jpg

    6、快速排序
    这个时候呢,也诞生了另一个思想,个人看来也是一种分类,它是怎样的呢?有点类似于体育课的时候高个子站后面矮个子站前面,教练没办法一开始就一眼看出谁高谁矮对吧?那么多人,肯定是随便逮一个,来以他为基准,排序!!!一声令下,小个的站这家伙的前边,大个的站后边,对吧?而这就是快速排序的核心思想。有点像二分法,不过这个二分法有点不同,它不是按长度,它是按类,你高就占那边,矮就站这边,把整体分成两部分,那矮的那块还能不能再分,那是当然,矮的那块再随便找一个,再分,这样就完成了一个排序的内部过程。(左边小,右边大,那当长度为3的时候不就实现有序了吗?嗯,这就是快排的核心思想)

    具体的代码怎么实现呢?
    这样很直观的我们就想到,嘿我弄两个数组,装高个子跟矮个子,然后再concat回来对吧?当然记得把中间那家伙给放进去,别漏了。看下下面:

算法入门篇:简单的排序算法-8.jpg

    嗯,是不是很直观?呵呵,但是要知道,排序,特别是排序数据非常多的时候,最考验的就是性能,而代码中left = [], right = [];还递归,这个内存的开销是非常大的,所以我们不这样,那怎么做呢?
算法入门篇:简单的排序算法-9.jpg
    上面的虽然没重新创建数组,但是呢?通过交换,比如说大于参考点的放左边,小于的放右边,那我直接等待一下,一个从左边开始扫描,一个从右边,当左边扫描到比参考数大的数时,结束扫描,右边也扫描,当有一个数比参考数小时,就结束扫描,这时候把这两个数交换一下,是不是就实现了小的在前面大的在后面,你说,可他们不一定在参考点两边啊?没错,这个时候继续扫描,等到i和j在某个点相遇的时候,把这个参考点的值跟那个位置的值换一下,不就实现两边一边大一边小嘛。、

    嗯,有了一个了,当然得有无数次,左边那块再继续做这个事,右边的也一样,当右边跟左边再加上中间的数长度刚好为3或小于3的时候不就OK了?

    7、堆排序

    这时候还有一个性能也很不错的排序,用到完全二叉树的方式来的。

    它又是怎么想的?卧槽(没文化的我只会这一句= =),不就个排序,非得弄那么多乱七八糟的?嗯,怎么说呢,这是一种思想,先不扯远一起看看具体是怎么样的吧。

    堆,有大顶堆跟小顶堆之分,这里就不扯概念了,那个官方讲得很详细嗯也很官方= =,简单理解一下就是一个金字塔,你是帮主,你下面还有左右护法四大天王八大金刚十六罗汉,嗯就这样一直下去,而所谓的大顶堆就是作为帮主的你是住塔顶的,小顶堆呢?则相反,你们帮最小最小的那个小弟就在那。大概是这样哈:

    这个就是所谓的大顶堆,生活中是不是太常见了?(理解为主,请忽略图= =)

算法入门篇:简单的排序算法-10.jpg
    那它又是怎么做到排序的?
算法入门篇:简单的排序算法-11.gif

    还记得选择排序是怎么排序的?就是选择一个最大数不断的插入到最后的对吧?但是选择最大数的那个过程是通过不断的比较,一个个位置挪动去得到的,那能不能跳着走?跳着扫描。实际上,分成堆只是让我们更好理解。
    一起看看代码是怎么样实现的吧:

算法入门篇:简单的排序算法-12.jpg
    下面是做的一个简单的性能测试:

    ① 普通插入排序与快速排序的速度对比(数据量20万):
算法入门篇:简单的排序算法-13.jpg

    可以看到在20万随机数(0-10000)的排序中,快排所花的时间不足100个时间单位,而插入排序要超过50000个。普通的O(n²)的性能与最好情况O(nlogn)的快排是完全没法比(数据量越庞大结果越明显)。

    ② 希尔排序与快速排序对比(数据量2000万):
算法入门篇:简单的排序算法-14.jpg

     由于这两个排序都是极不稳定的,但是从测试的几次结果看,希尔排序的性能会略微优于快排(语言:javascript)

    ③归并排序与希尔排序

算法入门篇:简单的排序算法-15.jpg

    归并排序相对于希尔,快排的不稳定来说,归并排序最好跟最坏的情况均是nlogn,是稳定且快捷的排序算法。利用的正是完全二叉树的思维模式。
    ④堆排序与归并排序

算法入门篇:简单的排序算法-16.jpg

    也是2000万1-10000的随机数排序。
总结:
        人类的思维方式是不断进化的,一开始我们遇到问题时的解决办法就是类似于冒泡排序,选择排序,插入排序一样,简单直观易理解上手但效率较低,但随着时间的推移,不断的找到更好的办法来替代,就比如说插入排序,一开始的插入是靠着大的数一个个往后挪挪出一个位置来的,那既然可以一个位置一个位置的挪,为什么不可以一大段一大段位置的挪呢?这样效率不是更高?你说没一个个位置的挪可能挪偏了,比如可能挪偏大一点,没关系啊,后面继续进行一次挪动就好了。这个就是希尔排序的思想。而对于选择排序,同样的,我要选出一个最大数,通过传统的一个个位置扫描是最简单直观,但太慢了,我可不可以直接堆成堆来,不断的比较二分的数与该二分数位置再二分的数,这样跳着走完整个循环,是不是就可以快上好多?再看看快速排序,他的思想就有些不同,他的核心思想是一个序列,一定是可以分成大于某个数的一堆跟小于某个数的一堆,当这个序列只有3个数时,实际上这个序列就已经有序了。再看看归并(或者说完全二叉树的思想),分治,我无论多长的序列,最后,我一定是可以分成一个个长度为2的小组(或者剩余最后一个),我只要保证分出来的这些小组都被处理成有序,最终合并就好了。

作者:dorseyCh
链接:http://www.imooc.com/article/264180
来源:慕课网
本文首次发布于慕课网 ,转载请注明出处,谢谢合作
推荐阅读:
接手别人的代码,死的心有吗?
程序员都有哪些强迫行为?
网上黑程序员的现实依据是什么?程序员真的那么悲惨吗?
有哪些视频堪称有毒?
暴露真实IP真的没关系吗?
有哪些程序员特有的习惯?
月薪3万的程序员都避开了哪些坑?
双11特辑:狂欢的背后,都有哪些关键性技术值得你学习?
分享到 :
0 人收藏

2 个回复

倒序浏览
您的图片分辨率较低
有个错别字..扔最后不是仍最后
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|翁笔

© 2001-2018 Wengbi.com

返回顶部