您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

JavaScript中常见排序算法详解

时间:2020-04-26 11:15:24  来源:  作者:

当年,想凭借抱JAVA大腿火一把而不惜把自己名字给改了的JavaScript(原名LiveScript),如今早已光芒万丈。node JS的出现更是让JavaScript可以前后端通吃。虽然Java依然制霸企业级软件开发领域(C/C + +的大神们不要打我。。。),但在Web的江湖,JavaScript可谓风头无两,坐上了头把交椅。

然而,在传统的计算机算法和数据结构领域,大多数专业教材和书籍的默认语言都是Java或者C/C+ +。这给最近想恶补算法和数据结构知识的我造成了一定困扰,因为我想寻找一本以JavaScript为默认语言的算法书籍。当我了解到O’REILLY家的动物丛书系列里有一本叫做《数据结构与算法JavaScript描述》时,便兴奋的花了两天时间把这本书从头到尾读了一遍。它是一本很好的针对前端开发者们的入门算法书籍,可是,它有一个很大的缺陷,就是里面有很多明显的小错误,明显到就连我这种半路出家的程序猿都能一眼看出来。还有一个问题是,很多重要的算法和数据结构知识并没有在这本书里被提到。这些问题对于作为一个晚期强迫症患者的我来说简直不能忍。于是乎,一言不合我就决定自己找资料总结算法。那么,我就从算法领域里最基础的知识点——排序算法总结起好了。

我相信以下的代码里一定会有某些bug或错误或语法不规范等问题是我自己无法发现的,所以敬请各位大神能够指出错误,因为只有在不断改错的道路上我才能取得长久的进步。

十大经典算法

一张图概括:

JavaScript中常见排序算法详解

 

名词解释:

n:数据规模

k:“桶”的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同

冒泡排序

作为最简单的排序算法之一,冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。。。冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。

什么时候最快

当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊。。。。)

什么时候最慢

当输入的数据是反序时(写一个for循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗。。。)

冒泡排序动图演示

JavaScript中常见排序算法详解

 

JavaScript代码实现

JavaScript

 

functionbubbleSort(arr){

varlen=arr.length;

for(vari=0;i<len;i++){

for(varj=0;j<len-1-i;j++){

if(arr[j]>arr[j+1]){//相邻元素两两对比

vartemp=arr[j+1];//元素交换

arr[j+1]=arr[j];

arr[j]=temp;

}

}

}

returnarr;

}

选择排序

表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序动图演示

JavaScript中常见排序算法详解

 

JavaScript代码实现

JavaScript

 

functionselectionSort(arr){

varlen=arr.length;

varminIndex,temp;

for(vari=0;i<len-1;i++){

minIndex=i;

for(varj=i+1;j<len;j++){

if(arr[j]<arr[minIndex]){//寻找最小的数

minIndex=j;//将最小数的索引保存

}

}

temp=arr[i];

arr[i]=arr[minIndex];

arr[minIndex]=temp;

}

returnarr;

}

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌,那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。对于这种算法,得了懒癌的我就套用教科书上的一句经典的话吧:感兴趣的同学可以在课后自行研究。。。

插入排序动图演示

JavaScript中常见排序算法详解

 

JavaScript代码实现

JavaScript

functioninsertionSort(arr){

varlen=arr.length;

varpreIndex,current;

for(vari=1;i<len;i++){

preIndex=i-1;

current=arr[i];

while(preIndex>=0&&arr[preIndex]>current){

arr[preIndex+1]=arr[preIndex];

preIndex--;

}

arr[preIndex+1]=current;

}

returnarr;

}

希尔排序

希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。在这里,我就使用了这种方法。

JavaScript代码实现

JavaScript中常见排序算法详解

 

归并排序

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第2种方法)
  • 自下而上的迭代

在《数据结构与算法JavaScript描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

说实话,我不太理解这句话。意思是JavaScript编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。

归并排序动图演示

JavaScript中常见排序算法详解

 

归并排序JavaScript代码实现:

JavaScript中常见排序算法详解

 

快速排序

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好,可是这是为什么呢,我也不知道。。。好在我的强迫症又犯了,查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是O(n²),比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ,且O(n log n)记号中隐含的常数因子很小,比复杂度稳定等于O(n log n)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

快速排序动图演示

JavaScript中常见排序算法详解

 

快速排序JavaScript代码实现:

JavaScript中常见排序算法详解

 

堆排序

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列

堆排序动图演示

JavaScript中常见排序算法详解

 

堆排序JavaScript代码实现:

JavaScript中常见排序算法详解

 

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

计数排序动图演示

JavaScript中常见排序算法详解

 

计数排序JavaScript代码实现:

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效,我们需要做到这两点:

  1. 在额外空间充足的情况下,尽量增大桶的数量
  2. 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

什么时候最快

当输入的数据可以均匀的分配到每一个桶中

什么时候最慢

当输入的数据被分配到了同一个桶中

桶排序JavaScript代码实现:

JavaScript中常见排序算法详解

 

基数排序

基数排序有两种方法

  1. MSD 从高位开始进行排序
  2. LSD 从低位开始进行排序

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

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

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

LSD基数排序动图演示:

JavaScript中常见排序算法详解

 

基数排序JavaScript代码实现:

JavaScript中常见排序算法详解

 

写在最后

排序算法实在是博大精深,还有hin多hin多我没有总结到或者我自己还没弄明白的算法,仅仅是总结这十种排序算法都把我写哭了。。。



Tags:JavaScript   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1、通过条件判断给变量赋值布尔值的正确姿势// badif (a === &#39;a&#39;) { b = true} else { b = false}// goodb = a === &#39;a&#39;2、在if中判断数组长度不为零...【详细内容】
2021-12-24  Tags: JavaScript  点击:(6)  评论:(0)  加入收藏
给新手朋友分享我收藏的前端必备javascript已经写好的封装好的方法函数,直接可用。方法函数总计:41个;以下给大家介绍有35个,需要整体文档的朋友私信我,1、输入一个值,将其返回数...【详细内容】
2021-12-15  Tags: JavaScript  点击:(20)  评论:(0)  加入收藏
作者:一川来源:前端万有引力 1 写在前面Javascript中的apply、call、bind方法是前端代码开发中相当重要的概念,并且与this的指向密切相关。本篇文章我们将深入探讨这个关键词的...【详细内容】
2021-12-06  Tags: JavaScript  点击:(19)  评论:(0)  加入收藏
概述DOM全称Document Object Model,即文档对象模型。是HTML和XML文档的编程接口,DOM将文档(HTML或XML)描绘成一个多节点构成的结构。使用JavaScript可以改变文档的结构、样式和...【详细内容】
2021-11-16  Tags: JavaScript  点击:(35)  评论:(0)  加入收藏
一、判断是否IE浏览器(支持判断IE11与edge)function IEVersion() {var userAgent = navigator.userAgent; //取得浏览器的userAgent字符串var isIE = userAgent.indexOf("comp...【详细内容】
2021-11-02  Tags: JavaScript  点击:(40)  评论:(0)  加入收藏
Null、Undefined、空检查普通写法: if (username1 !== null || username1 !== undefined || username1 !== &#39;&#39;) { let username = username1; }优化后...【详细内容】
2021-10-28  Tags: JavaScript  点击:(51)  评论:(0)  加入收藏
1、前言async函数,也就是我们常说的async/await,是在ES2017(ES8)引入的新特性,主要目的是为了简化使用基于Promise的API时所需的语法。async和await关键字让我们可以用一种更简...【详细内容】
2021-09-17  Tags: JavaScript  点击:(61)  评论:(0)  加入收藏
为什么要使用 debugger这篇文章将介绍如何使用断点来进行 JavaScript 调试。在读这篇文章之前,需要问一个问题:为什么要使用断点来进行调试?我们首先需要认可使用断点的是必要...【详细内容】
2021-08-26  Tags: JavaScript  点击:(66)  评论:(0)  加入收藏
JavaScript 可以做很多好玩的事, 从复杂的框架到处理API,有太多的东西需要学习。但是,它也能让我们只用一行就能做一些了不起的事情。1. 获得一个随机的布尔值(true/false)该函数...【详细内容】
2021-08-19  Tags: JavaScript  点击:(77)  评论:(0)  加入收藏
JavaScript 提供了大量不同的处理数组的方法,这里花几分钟时间介绍 8 个项目中可以用到的数组方法。1. Array.map()使用.map() 方法,可以创建一个基于原始数组的修订版数组。....【详细内容】
2021-08-19  Tags: JavaScript  点击:(95)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条