JS排序之快速排序详解
本文为大家分享了JS快速排序的具体代码,供大家参考,具体内容如下
说明
时间复杂度指的是一个算法执行所耗费的时间
空间复杂度指运行完一个程序所需内存的大小
稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面
不稳定指,如果a=b,a在b的前面,排序后可能会交换位置
--JS快速排序--
原理
从数组中选定一个基数,然后把数组中的每一项与此基数做比较,小的放入一个新数组,大的放入另外一个新数组。然后再采用这样的方法操作新数组。直到所有子集只剩下一个元素,排序完成。
时间复杂度,空间复杂度,稳定性
- 平均时间复杂度O(nlogn)
- 最好情况O(nlogn)
- 最差情况O(n*n)
- 空间复杂度O(logn)
- 稳定性:不稳定
快速排序的写法
var examplearr=[8,94,15,88,55,76,21,39]; function fastsort(arr){ if(arr.length<2){ return arr; } var left=[]; var right=[]; var pivotIndex=Math.floor(arr.length/2); var pivot=arr.splice(pivotIndex,1)[0]; for(i=0;i<arr.length;i++){ if(arr[i]<pivot){ left.push(arr[i]); }else{ right.push(arr[i]) } } return fastsort(left).concat([pivot],fastsort(right)); } console.log(fastsort(examplearr));
解析
pivotIndex是将数组的长度除2向下取整得到的一个数值,数组的长度是不断减半的,所以最后它的值为0
pivot是利用splice方法从数组里获取一个基数
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
Vue.js bootstrap前端实现分页和排序
写之前先抱怨几句.本来一心一意做.net开发的,渐渐地成了只做前端.最近项目基本都用java做后台,我们这些.net的就成了前端,不是用wpf做界面,就是用html写web页面. 深知自己前端技术不足,以前虽说用asp.net前后台都做,但是,对于前端都是用现成的js库和页面模板,对于vue.js等框架基本没有接触过. 只怪自己不会写java,最近做一个项目,负责前端,后台传来数据不分页,前端收到所有数据后自己分页.我尽是无语. 正好最近在看vue.js.这个页面就用它来实现吧.顺便总结下. 效
-
利用JavaScript对中文(汉字)进行排序实例详解
前言 在网页上展示列表时经常需要对列表进行排序:按照修改/访问时间排序.按照地区.按照名称排序. 对于中文列表按照名称排序就是按照拼音排序,不能简单通过字符串比较-- 'a' > 'b'--这种方式来实现. 比如比较 '北京' vs '上海',实际是比较 'běijīng' vs 'shànghǎi':比较 '北京' vs '背景',实际是比较 'běijīng' vs 'bèijǐng'. 一般需要获取到字符串的拼音,再比较各自的拼音. 实现方法 JavaScript 提供本地化文字排序,比如
-
基于JavaScript实现的快速排序算法分析
本文实例讲述了基于JavaScript实现的快速排序算法.分享给大家供大家参考,具体如下: 首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成.这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了.然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出.以此类推直到所有被选出,冒泡结束. 通过分析可以得出,冒泡排序的时间复杂度为O(n2). 快速排序是对冒泡
-
javascript 数组排序与对象排序的实例
javascript 数组排序与对象排序的实例 数组排序 在使用JavaScript的时候,我们都发现了sort这个函数其实是按照字典顺序进行排序的,比如下面的这个例子: var ary = [2, 98, 34, 45, 78, 7, 10, 100, 99]; ary.sort(); console.log(ary); 控制台输出结果: Array [ 10, 100, 2, 34, 45, 7, 78, 98, 99 ] 这个也很显然验证了我之前所写的东西,上面的结果就是比较数组元素的第
-
JS实现的点击表头排序功能示例
本文实例讲述了JS实现的点击表头排序功能.分享给大家供大家参考,具体如下: 运行效果: 1.index.html文件: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html> <head> <title>jb51.net点击表头排序</t
-
JavaScript之排序函数_动力节点Java学院整理
排序算法 排序也是在程序中经常用到的算法.无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小.如果是数字,我们可以直接比较,但如果是字符串或者两个对象呢?直接比较数学上的大小是没有意义的,因此,比较的过程必须通过函数抽象出来.通常规定,对于两个元素x和y,如果认为x < y,则返回-1,如果认为x == y,则返回0,如果认为x > y,则返回1,这样,排序算法就不用关心具体的比较过程,而是根据比较结果直接排序. JavaScript的Array的sort()方法就是用于排序的,但是
-
基于JavaScript实现的希尔排序算法分析
本文实例讲述了基于JavaScript实现的希尔排序算法.分享给大家供大家参考,具体如下: 通过对直接插入排序的分析,可知其时间复杂度为O(n2),但是,如果待排序序列为正序时,其时间复杂度可提高至O(n).希尔排序正是对此进行改进的排序.希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻元素.通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔. 下图演示了希尔排序中间隔序列是如何运行的: 下面我们通过js来实现希尔排序,代码如下: <!DOCTYPE ht
-
JS实现简易的图片拖拽排序实例代码
由HTML5的拖放API,实现的简易图片拖放效果. 一.HTML5拖放API的知识点 首先我们得知道元素怎么才可以被拖放,需要设置它们的draggable属性,其中img和a标签的dragable属性默认是true,不需要我们手动设置. 拖放API的监听事件如下: dragstart: 源对象拖拽开始: drag: 源对象拖拽的过程中: dragend: 源对象拖拽结束: dragenter: 进入过程对象区域; dragover: 在过程对象区域内移动: dragleave: 离开过程对象区域
-
JS排序之快速排序详解
本文为大家分享了JS快速排序的具体代码,供大家参考,具体内容如下 说明 时间复杂度指的是一个算法执行所耗费的时间 空间复杂度指运行完一个程序所需内存的大小 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置 --JS快速排序-- 原理 从数组中选定一个基数,然后把数组中的每一项与此基数做比较,小的放入一个新数组,大的放入另外一个新数组.然后再采用这样的方法操作新数组.直到所有子集只剩下一个元素,排序完成. 时间复杂度,空间复杂度,稳
-
JS排序之冒泡排序详解
本文为大家分享了JS冒泡排序的具体代码,供大家参考,具体内容如下 说明 时间复杂度指的是一个算法执行所耗费的时间 空间复杂度指运行完一个程序所需内存的大小 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置 --JS冒泡排序-- 原理 依次比较相邻的两个值,如果后面的比前面的小,则将小的元素排到前面.依照这个规则进行多次并且递减的迭代,直到顺序正确. 时间复杂度,空间复杂度,稳定性 平均时间复杂度O(n*n) 最好情况O(n) 最差
-
JavaScript中数组随机排序的实现详解
目录 一.原地算法 二.Array.property.sort() 1.方法一(不推荐) 2.方法一改良 三.洗牌算法实现随机排序 1.换牌 2.抽牌 一.原地算法 在谈sort之前,我们先了解一下原地算法,什么事原地算法呢?所谓原地算法就是说基于原有的数据结构进行一定的操作修改,而不借助额外的空间.使用原地算法时,其内存干净,空间复杂度是O(1),可以减少没必要的内存,避免造成内存浪费和冗余.当然,减小内存损耗会带来算法复杂度和时间消耗的增加,所以是一个Tradeoff.Tradeoff 是一
-
Python 十大经典排序算法实现详解
目录 关于时间复杂度 关于稳定性 名词解释 1.冒泡排序 (1)算法步骤 (2)动图演示 (3)Python代码 2.选择排序 (1)算法步骤 (2)动图演示 (3)Python代码 3.插入排序 (1)算法步骤 (2)动图演示 (3)Python代码 4.希尔排序 (1)算法步骤 (2)Python代码 5.归并排序 (1)算法步骤 (2)动图演示 (3)Python代码 6.快速排序 (1)算法步骤 (2)动图演示 (3)Python代码 7.堆排序 (1)算法步骤 (2)动图演示 (3)P
-
JavaScript实现拖拽排序的方法详解
目录 实现原理概述 代码实现 完整代码实现 可拖拽排序的菜单效果大家想必都很熟悉,本次我们通过一个可拖拽排序的九宫格案例来演示其实现原理. 先看一下完成效果: 实现原理概述 拖拽原理 当鼠标在[可拖拽小方块](以下简称砖头)身上按下时,开始监听鼠标移动事件 鼠标事件移动到什么位置,砖头就跟到什么位置 鼠标抬起时,取消鼠标移动事件的监听 排序原理 提前定义好9大坑位的位置(相对外层盒子的left和top) 将9大砖头丢入一个数组,以便后期通过splice方法随意安插和更改砖头的位置 当拖动某块砖头
-
js正则表达式常用函数详解(续)
正则表达式对象的方法 1.test,返回一个 Boolean 值,它指出在被查找的字符串中是否存在模式.如果存在则返回 true,否则就返回 false. 2.exec,用正则表达式模式在字符串中运行查找,并返回包含该查找结果的一个数组. 3.compile,把正则表达式编译为内部格式,从而执行得更快. 正则表达式对象的属性 1.source,返回正则表达式模式的文本的复本.只读. 2.lastIndex,返回字符位置,它是被查找字符串中下一次成功匹配的开始位置. 3.input ($_),返回
-
JS库之Three.js 简易入门教程(详解之一)
开场白 webGL可以让我们在canvas上实现3D效果.而three.js是一款webGL框架,由于其易用性被广泛应用.如果你要学习webGL,抛弃那些复杂的原生接口从这款框架入手是一个不错的选择. 博主目前也在学习three.js,发现相关资料非常稀少,甚至官方的api文档也非常粗糙,很多效果需要自己慢慢敲代码摸索.所以我写这个教程的目的一是自己总结,二是与大家分享. 本篇是系列教程的第一篇:入门篇.在这篇文章中,我将以一个简单的demo为例,阐述three.js的基本配置方法.学完这篇文章
-
详解JS数组Reduce()方法详解及高级技巧
基本概念 reduce() 方法接收一个函数作为累加器(accumulator),数组中的每个值(从左到右)开始缩减,最终为一个值. reduce 为数组中的每一个元素依次执行回调函数,不包括数组中被删除或从未被赋值的元素,接受四个参数:初始值(或者上一次回调函数的返回值),当前元素值,当前索引,调用 reduce 的数组. 语法: arr.reduce(callback,[initialValue]) callback (执行数组中每个值的函数,包含四个参数) previousValue (上
-
关于动态执行代码(js的Eval)实例详解
熟悉javascript的朋友对Eval()函数可能都不会陌生,我们可以用它来实现动态代码的执行,我自己甚至写过一个网页专门用来计算算术表达式的,计算能力上比google.baidu的计算器还要好一些,至少精度要高,但是如果超出了四则运算的话,表达式的形式会复杂很,比如以百度给出的例子: log((5+5)^2)-3+pi需要写成Math.log(Math.pow(5+5,2))*Math.LOG10E-3+Math.PI才能用Eval进行计算,对于这一点我还没有想到理想的解决方案.好了,这不是
-
基于node.js之调试器详解
1.在命令行窗口中,可以使用"node debug" 命令来启用调试器,代码如下: node debug<需要被执行的脚本文件名>接下来根据一个实例进行学习调试过程: 编写app.js文件进行调试: console.log('hello,word') function foo(){ console.log('hello,foo') return 100; } var bar = 'This is a pen'; var http = require('http') var
随机推荐
- jquery ajax提交表单数据的两种方式
- Webpack+Vue如何导入Jquery和Jquery的第三方插件
- BootStrap轻松实现微信页面开发代码分享
- android webview中使用Java调用JavaScript方法并获取返回值
- iOS实现类似格瓦拉电影的转场动画
- C# 递归函数详细介绍及使用方法
- 服务器安全狗导致ASP.NET网站运行出错的一个案例
- php 远程图片保存到本地的函数类
- hashtable桶数通常会取一个素数分析
- XSL简明教程(5)XSL的索引
- JQuery 封装 Ajax 常用方法(推荐)
- Jquery动态改变图片IMG的src地址示例
- shell脚本连接并重启远程服务器的方法
- jQuery中find()方法用法实例
- SQLServer数据库的各种管理方法
- jQuery实现验证年龄简单思路
- Java配置JDK开发环境及环境变量
- 解密DDoS攻击——“缓存溢出”新变形
- Laravel中Trait的用法实例详解
- Java基于JDBC实现事务,银行转账及货物进出库功能示例