JS排序算法

notebin 发布于2019-08-01 15:39 / 2765人阅读

摘要：冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。插入排序最好情况下时间复杂度是，其他情况下也都是。代码演示插入排序归并排序原生里面的方法，在里面是用归并排序实现的，而在里面是用快速排序的变体来实现的。

1、冒泡排序

冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。
假设一共有n项，那么一共需要n-1趟，第一趟需要交换n-1次，但是第一趟结束后，最后一项基本确定就是最大项了，所以第二次需要交换n-2次，第i次交换n-i次。

这种排序最好情况下时间复杂度是O(n),一般情况下时间复杂度是O(n²),最差情况下也是O(n²)。


这里是代码演示:

冒泡排序

2、选择排序

选择排序是找到最小的一项，然后和第一项交换位置，然后找到第二小的和第二项交换，依次类推，一共需要n-1次。

选择排序在所有情况下空间复杂度都是O(n²)。

代码演示：

选择排序

3、插入排序

插入排序是将前面的项看做数组，然后后面的项根据大小插入到对应的位置。比如第二项和第一项对比，他该插到第一项前面还是后面呢？第三项该插到一二项的哪个地方？
这个一般也需要插入n-1次。

插入排序最好情况下时间复杂度是O(n)，其他情况下也都是O(n²)。

代码演示：

插入排序

4、归并排序

原生js里面的sort方法，在firefox里面是用归并排序实现的，而在chrome里面是用快速排序的变体来实现的。

归并排序是一种分治的算法，他是将一个大数组分成无数的小数组，如果小数组里面只有一项，那么直接返回，如果大于一项，就继续分，接着小数组合并成一个大数组，合并的时候左右会进行比较大小，然后排序

代码演示:

归并排序

5、快速排序

快速排序也使用了分治的算法，也是把大数组分成小数组.
它会选择一个中间元，创建两个左右指针，然后分别从左右开始出发，如果左指针遇到比中间元大的数，它会停下来，而右边的如果遇到比中间元小的数，它也会停下来，然后两者交换位置。
接着两个指针继续前进，直到左指针超过了右指针，这样左边的数就会小于中间元，右边的数都会大于中间元，接下来分成左右数组，然后再进行上面的操作，直到数组完全排序。

代码演示:快速排序

超融合服务器专线服务 JS排序算法排序算法图解排序算法总结桶排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/50031.html

JS数据结构与算法_排序和搜索算法

摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。上一篇：JS数据结构与算法_树写在前面这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...

姘搁『 2019-08-23 16:26 评论0 收藏0
使用JS实现三种基本的排序算法以及三种算法的比较

摘要：介绍排序算法是算法中最常见的算法之一，我这里要介绍的是排序算法中的三种基本算法冒泡排序选择排序插入排序，在文章的后面我会对三种算法的速度进行对比。 1.介绍排序算法是算法中最常见的算法之一，我这里要介绍的是排序算法中的三种基本算法：冒泡排序、选择排序、插入排序，在文章的后面我会对三种算法的速度进行对比。 2.冒泡排序冒泡排序其名来源与其算法实现，会使得数组中的元素一个个从数组一端漂...

wh469012917 2019-08-20 19:09 评论0 收藏0
排序算法分析总结（附js实现）

摘要：本文对一些排序算法进行了简单分析，并给出了的代码实现。平均时间复杂度不好分析，它是冒泡排序是稳定的排序算法。冒泡排序是原地排序算法原地排序指的是空间复杂度是的排序算法。归并排序，会将数组从中间分成左右两部分。本文对一些排序算法进行了简单分析，并给出了 javascript 的代码实现。因为本文包含了大量的排序算法，所以分析不会非常详细，适合有对排序算法有一定了解的同学。本文内容其实不...

liaoyg8023 2019-08-23 17:11 评论0 收藏0
JS排序算法

摘要：冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。插入排序最好情况下时间复杂度是，其他情况下也都是。代码演示插入排序归并排序原生里面的方法，在里面是用归并排序实现的，而在里面是用快速排序的变体来实现的。 1、冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。假设一共有n项，那么一共需要n-1趟，第一趟需要交换n-1次，但是第一趟结束后，最后一项基本确定就...

sihai 2019-08-20 10:37 评论0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法，文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现，如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...

verano 2019-08-20 15:08 评论0 收藏0