一些排序算法

记得有一个明星程序员说,做一个 web developer 是不用学习数学的。那么自然也不用学习算法了。作为一个前端,在实际工作中确实很少实现什么排序算法,因为在 JavaScript 的语言层面,就已经实现 sort 函数了。但是学习这些排序算法,依然有助于我们理解这些语言相关内置函数的原理。

人类从来不给自己设限,才是我们一直前进的动力。

冒泡排序

冒泡排序的基本思想很简单,通过两层循环,来逐渐交换相邻的位置,大的放在右边,小的放在左边,外层的第一次循环选出最大的数字,第二次选出第二大的数字,以此类推。代码如下:

选择排序

选择排序的核心思想是从排序的元素中选择最小的元素,放在第一位;再从余下最小的元素中,选择最小的,再放到第二位,以此类推,直到排序成功。

核心代码如下:

插入排序

插入排序的思想也非常简单,只是把这种思想转化为代码就要难一点。我们从一堆乱序的元素中选出一个放在已排序好元素中的合适位置,我们具体看代码:

短短几行代码,需要仔细看看。

下面我们来介绍一下希尔排序、归并排序和快速排序这几种高级排序算法。我清晰的记得一次电话面试中,tx 面试官让我说一下快速排序的核心思想。

希尔排序

在了解希尔排序之前,可以先看一下这个视频(需要翻墙)。希尔排序和插入排序的思想非常类似,只不过希尔排序定义了一个间隔位置,用来减少交换的次数。

希尔排序要解释清楚还是挺费劲的,如果看懂了上面的视频,那么理解起来也不难。核心代码如下。

对于初学者可能需要花一定的时间去理解上面的代码,可以再查查其它的相关文章。

归并排序

在理解归并排序前,我们还是先看一个视频。代码我就不贴出了,行数有点多。

快速排序

在视频面前,文字显得不够直白,还是看视频吧。

JavaScript 版本的快速排序实现如上,实现起来还是挺简洁的。

参考链接

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

曾小乱

作者: 曾小乱

喜欢写点有意思的东西

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.