十大经典排序算法的JS版

具体算法描述如下：

<1>. 找出待排序的数组中最大年夜和最小的元素;
<2>. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项;
<3>. 对所有的计数累加(大年夜C中的第一个元素开端，每一项和前一项相加);
<4>. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

Javascript代码实现：

2.选择排序(Selection Sort)

(3)算法分析

当输入的元素是n 个0到k之间的┞符数时，它的运行时光是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。因为用来计数的数组C的长度取决于待排序数组中数据典范围(等于待排序数组的最大年夜值与最小值的参加上1)，这使得计数排序对于数据范围很大年夜的数组，须要大年夜量时光和内存。

最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n+k)
平均情况：T(n) = O(n+k)

9.桶排序(Bucket Sort)

桶排序是计数排序的进级版。它应用了函数的映射关系，高效与否的关键就在于这个映射函数切实其实定。

(1)算法简介

桶排序 (Bucket sort)的工作的道理：假设输入数据服大年夜平均分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再应用其余排序算法或是以递归方法持续应用桶排序进行排

(2)算法描述和实现

具体算法描述如下：

<1>.设置一个定量的数组算作空桶;
<2>.遍历输入数据，并且把数据一个一个放到对应的桶里去;
<3>.对每个不是空的桶进行排序;
<4>.大年夜不是空的桶里把排好序的数据拼接起来。

Javascript代码实现:

桶排序图示(图片来源收集)：

(3)算法分析

桶排序最好情况下应用线性时光O(n)，桶排序的时光复杂度，取决与对各个桶之间数据进行排序的时光复杂度，因为其它部分的时光复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时光也会越少。但响应的空间消费就会增大年夜。

最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n+k)
平均情况：T(n) = O(n2)

10.基数排序(Radix Sort)

基数排序也长短比较的排序算法，对每一位进行排序，大年夜最低位开端排序，复杂度为O(kn),为数组长度，k为数组中的数的最大年夜的位数;

(1)算法简介

基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次类推，直到最高位。有时刻有些属性是有优先级次序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级雷同的低优先级高的在前。基数排序基于分别排序，分别收集，所所以稳定的。

媒介

(2)算法描述和实现

具体算法描述如下：

<1>.取得数组中的最大年夜数，并取得位数;
<2>.arr为原始数组，大年夜最低位开端取每个位构成radix数组;
<3>.对radix进行计数排序(应用计数排序实用于小范围数的特点);

Javascript代码实现：

基数排序LSD动图演示：

(3)算法分析

最佳情况：T(n) = O(n * k)
最差情况：T(n) = O(n * k)
平均情况：T(n) = O(n * k)

基数排序有两种办法：

MSD 大年夜高位开端进行排序
LSD 大年夜低位开端进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都应用了桶的概念，但对桶的应用办法上有明显差别：

基数排序：根据键值的每位数字来分派桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储必定范围的数值

先将全部待排序的记录序列瓜分成为若干子序列分别进行直接插入排序，具体算法描述：

<1>. 选择一个增量序列t1，t2，…，tk，个中ti>tj，tk=1;
<2>.按增量序列个数k，对序列进行k 趟排序;
<3>.每趟排序，根据对应的增量ti，将待排序列瓜分成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，全部序列作为一个表来处理，表长度即为全部序列的长度。

【编辑推荐】

状况决定视图——基于状况的前端开辟思虑
JavaScript代码风格要素
为什么在JavaScript中应用getter和setter是一个坏主意
JavaScript与异步编程
摸索前端黑科技——经由过程png图的rgba值缓存数据

【义务编辑：枯木 TEL：（010）68476606】

10/11 首页上一页 8 9 10 11 下一页尾页

　　推荐阅读

　　一文读懂矩阵的秩和行列式的意义

【技巧沙龙】AI开辟者拭魅战营-7分钟打造1个定制技能。7月22号，我们等你一路！作为一个工科的学生,我们经久以来会应用比如像是矩阵以及行列式这些在线性代数上的常识,在这篇文┞仿中,我>>>详细阅读

本文标题：十大经典排序算法的JS版

地址：http://www.17bianji.com/lsqh/36267.html

1/2 1