后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 编程语言 > JavaScriptJavaScript

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

2021-05-19 13:04:42JavaScript人已围观

简介这篇文章主要介绍了基于JavaScript实现的快速排序算法,分析了快速排序的原理并结合实例形式给出了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程序设计有所帮助。

文章来源:https://www.jb51.net/article/111189.htm

Tags:JavaScript 快速排序 算法 

很赞哦! ()

后台-插件-广告管理-内容页广告位二(手机)
后台-插件-广告管理-内容页广告位三(手机)
后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计49227篇文章
  • 浏览统计3200次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们