基于JavaScript实现的快速排序算法分析

本文实例讲述了基于JavaScript实现的快速排序算法。分享给大家供大家参考,具体如下:

首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成。这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了。然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出。以此类推直到所有被选出,冒泡结束。

通过分析可以得出,冒泡排序的时间复杂度为O(n2)

快速排序是对冒泡排序的一种改进,它是处理大数据集最快的排序之一,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列,不断重复该过程直到所有数据都是有序的。这个算法首先要选择一个基准值,围绕基准值进行。

示例如下:

算法思想如下:

选择一个基准元素,将列表分为两个子序列;

对列表重新排序,将所有小于基准元素的元素放前面,大的放后面;

分别对较小元素的子序列和较大元素的子序列重复上面两个步骤。

我们通过js实现代码如下:

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
  function qSort(nums) {//快速排序
    if(nums.length==0){
      return [];
    }
    var lesser=[];
    var greater=[];
    var pivot=nums[0];//选择基准元素
    for(var i=1;i<nums.length;i++){
      if(nums[i]<pivot){//分成两个之序列
        lesser.push(nums[i]);
      }else{
        greater.push(nums[i]);
      }
    }
    return qSort(lesser).concat(pivot,qSort(greater));//递归
  }
  function show(nums){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+' ');
    }
    document.write('<br>');
  }
  var nums=[68,80,12,80,95,70,79,27,88,93];
  show(nums);//newNums
  var newNums=qSort(nums);//希尔排序
  show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

就平均时间而言,快速排序是目前被认为最好的一种内部排序方法。快速排序非常适用于大型数据集合,在处理小数据集时性能反而会下降。其时间复杂度为O(nlog2n)

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

(0)

相关推荐

  • JS实现简易的图片拖拽排序实例代码

    由HTML5的拖放API,实现的简易图片拖放效果. 一.HTML5拖放API的知识点 首先我们得知道元素怎么才可以被拖放,需要设置它们的draggable属性,其中img和a标签的dragable属性默认是true,不需要我们手动设置. 拖放API的监听事件如下: dragstart: 源对象拖拽开始: drag: 源对象拖拽的过程中: dragend: 源对象拖拽结束: dragenter: 进入过程对象区域; dragover: 在过程对象区域内移动: dragleave: 离开过程对象区域

  • JavaScript之排序函数_动力节点Java学院整理

    排序算法 排序也是在程序中经常用到的算法.无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小.如果是数字,我们可以直接比较,但如果是字符串或者两个对象呢?直接比较数学上的大小是没有意义的,因此,比较的过程必须通过函数抽象出来.通常规定,对于两个元素x和y,如果认为x < y,则返回-1,如果认为x == y,则返回0,如果认为x > y,则返回1,这样,排序算法就不用关心具体的比较过程,而是根据比较结果直接排序. JavaScript的Array的sort()方法就是用于排序的,但是

  • 利用JavaScript对中文(汉字)进行排序实例详解

    前言 在网页上展示列表时经常需要对列表进行排序:按照修改/访问时间排序.按照地区.按照名称排序. 对于中文列表按照名称排序就是按照拼音排序,不能简单通过字符串比较-- 'a' > 'b'--这种方式来实现. 比如比较 '北京' vs '上海',实际是比较 'běijīng' vs 'shànghǎi':比较 '北京' vs '背景',实际是比较 'běijīng' vs 'bèijǐng'. 一般需要获取到字符串的拼音,再比较各自的拼音. 实现方法 JavaScript 提供本地化文字排序,比如

  • JS排序之快速排序详解

    本文为大家分享了JS快速排序的具体代码,供大家参考,具体内容如下 说明 时间复杂度指的是一个算法执行所耗费的时间 空间复杂度指运行完一个程序所需内存的大小 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置 --JS快速排序-- 原理 从数组中选定一个基数,然后把数组中的每一项与此基数做比较,小的放入一个新数组,大的放入另外一个新数组.然后再采用这样的方法操作新数组.直到所有子集只剩下一个元素,排序完成. 时间复杂度,空间复杂度,稳

  • 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

  • Vue.js bootstrap前端实现分页和排序

    写之前先抱怨几句.本来一心一意做.net开发的,渐渐地成了只做前端.最近项目基本都用java做后台,我们这些.net的就成了前端,不是用wpf做界面,就是用html写web页面. 深知自己前端技术不足,以前虽说用asp.net前后台都做,但是,对于前端都是用现成的js库和页面模板,对于vue.js等框架基本没有接触过. 只怪自己不会写java,最近做一个项目,负责前端,后台传来数据不分页,前端收到所有数据后自己分页.我尽是无语. 正好最近在看vue.js.这个页面就用它来实现吧.顺便总结下. 效

  • 基于JavaScript实现的希尔排序算法分析

    本文实例讲述了基于JavaScript实现的希尔排序算法.分享给大家供大家参考,具体如下: 通过对直接插入排序的分析,可知其时间复杂度为O(n2),但是,如果待排序序列为正序时,其时间复杂度可提高至O(n).希尔排序正是对此进行改进的排序.希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻元素.通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔. 下图演示了希尔排序中间隔序列是如何运行的: 下面我们通过js来实现希尔排序,代码如下: <!DOCTYPE ht

  • 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 ] 这个也很显然验证了我之前所写的东西,上面的结果就是比较数组元素的第

  • 基于JavaScript实现的快速排序算法分析

    本文实例讲述了基于JavaScript实现的快速排序算法.分享给大家供大家参考,具体如下: 首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成.这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了.然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出.以此类推直到所有被选出,冒泡结束. 通过分析可以得出,冒泡排序的时间复杂度为O(n2). 快速排序是对冒泡

  • 基于JavaScript实现的插入排序算法分析

    本文实例讲述了基于JavaScript实现的插入排序算法.分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序. 内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程:外部排序指的是待排序的记录数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程. 下面介绍几种常见的内部排序方式: 插入排序 插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入已排好序的有序表中,从而得到一个新的.记录数加1的有

  • 基于javascript实现的快速排序

    function quickSort(arr){ //如果数组只有一个数,就直接返回: if(arr.length<1){ return arr; } //找到中间的那个数的索引值:如果是浮点数,就向下取整 var centerIndex = Math.floor(arr.length/2); //根据这个中间的数的索引值,找到这个数的值: var centerNum = arr.splice(centerIndex,1); //存放左边的数 var arrLeft = []; //存放右边的数

  • 基于JavaScript实现表单密码的隐藏和显示出来

    为了网站的安全性,很多朋友都把密码设的比较复杂,但是如何密码不能明显示,不知道输的是对是错,为了安全起见可以把密码显示的,那么基于js代码如何实现的呢? 当用户输入时密码显示为圆点或者星号, 为了确保用户输入的正确, 用户可以点击让密码显示的按钮. 直接就先看节目效果. 界面结构, 一个外层的pass-box, 然后内层加入input 和 一个 i 标签, 且给他们加入相应的class名称. <div class="pass-box"> <input type=&qu

  • 基于JavaScript表单脚本(详解)

    什么是表单? 一个表单有三个基本组成部分: 表单标签:这里面包含了处理表单数据所用CGI程序的URL以及数据提交到服务器的方法. 表单域:包含了文本框.密码框.隐藏域.多行文本框.复选框.单选框.下拉选择框和文件上传框等. 表单按钮:包括提交按钮.复位按钮和一般按钮:用于将数据传送到服务器上的CGI脚本或者取消输入,还可以用表单按钮来控制其他定义了处理脚本的处理工作. JavaScript与表单间的关系:JS最初的应用就是用于分担服务器处理表单的责任,打破依赖服务器的局面,尽管目前web和jav

  • 基于JavaScript实现动态创建表格和增加表格行数

    在工作,项目需求中,有时候表格的行数不能够满足我们的需求,这时需要我们动态的增加表格的行数,下面小编通过一段代码实例给大家介绍js创建表格和增加表格的行数的方法,并且还实现了隔行变色功能.对此感兴趣的朋友可以参考一下代码: js代码如下所示: <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>动态操作表格</title> </head>

  • 基于JavaScript将表单序列化类型的数据转化成对象的处理(允许对象中包含对象)

    表单序列化类型的数据是指url传递的数据的格式,形如"key=value&key=value&key=value"这样的key/value的键值对.一般来说使用jQuery的$.fn.serialize函数能达到这样的效果.如何将这样的格式转化为对象? 我们知道使用jQuery的$.fn.serializeArray函数得到的是一个如下结构的对象 [ { name: "startTime" value: "2015-12-02 00:00:

  • 基于JavaScript实现跳转提示页面

    先给大家展示下效果图,如果大家感觉还不错,请参考实现代码: 网页布局 <p>操作成功</p> <strong>5</strong><span>秒后回到主页</span><a href="javascript:history.back();">返回</a> 任务: 1.打开网页后,如果不做任何操作则返回到一个新的页面 var num=document.getElementsByTagName(

  • 基于JavaScript实现评论框展开和隐藏功能

    1.效果图如下所示, 点击评论会在对应的评论区域展开评论输入框,点击取消会取消对应的评论输入框 2.html代码:需要引入jQuery.js <div class="nr-comment"> <div class="nr-comment-con"> <div class="nr-comment-nav"> <div class="comment-number"> <span

随机推荐