js排序算法:计数排序的实现方法

时间: 2017-12-21阅读: 1515标签: js知识

计数排序的基本思想

计数排序是一种线性排序算法,用于确定范围的整数的线性时间排序算法,不用进行比较。基本思想是对于每个元素x,找出比x小的数的个数,从而确定x在排好序的数组中的位置。

计数排序他的主要目的是对整数排序并且会比普通的排序算法性能更好。例如,输入[1, 3, 5, 2, 1, 4]给计数排序,会输出[1, 1, 2, 3, 4, 5]。


计数排序的步骤

1.查找待排序数组中最大和最小的元素 

2.统计每个值为i的元素的出现次数 

3.对所有计数开始累加(从min开始,每一项和前一项相加) 

4.反向填充目标数组,将每个元素i放在新数组的第C[i]项,每放一个元素,计数-1.置。


js计数排序实例

function countingSort(arr){
  var len = arr.length,
      Result = [],
      Count = [],
      min = max = arr[0];
  console.time('countingSort waste time:');
  /*查找最大最小值,并将arr数置入Count数组中,统计出现次数*/
  for(var i = 0;i<len;i++){
    Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1;
    min = min <= arr[i] ? min : arr[i];
    max = max >= arr[i] ? max : arr[i];
  }
  /*从最小值->最大值,将计数逐项相加*/
  for(var j = min;j<max;j++){
    Count[j+1] = (Count[j+1]||0)+(Count[j]||0);
  }
  /*Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据*/
  for(var k = len - 1;k>=0;k--){
    /*Result[位置] = arr数据*/
    Result[Count[arr[k]] - 1] = arr[k];
    /*减少Count数组中保存的计数*/
    Count[arr[k]]--;
    /*显示Result数组每一步详情*/
    console.log(Result);
  }
  console.timeEnd("countingSort waste time:");
  return Result;
}
var arr = [1, 3, 5, 2, 1, 4];
console.log(countingSort(arr));

输出如下:



站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/267

关闭

js dom是什么?_JS中的DOM知识概览

JS中的DOM知识概览:文档对象模型,是针对 HTML 和 XML 文档的一个 API (应用程序编程接口), 描绘了一个层次化的节点树。 web 浏览器浏览一个页面的时候,DOM 就在幕后把你编辑的网页文档转换成一个文档对象。

基于规则评分的密码强度检测算法分析及实现(JavaScript)

用正则表达式做用户密码强度的通过性判定,过于简单粗暴,不但用户体验差,而且用户帐号安全性也差。那么如何准确评价用户密码的强度,保护用户帐号安全呢?本文分析介绍了几种基于规则评分的密码强度检测算法

js中“=”,“==”,“===”的使用和深入理解

Js支持“=”、“==”和“===”的运算符,我们需要理解这些 运算符的区别 ,并在开发中小心使用。它们分别含义是:= 为对象赋值 ,== 表示两个对象toString值相等,=== 表示两个对象类型相同且值相等

Js中constructor指向问题

首先用一个例子指出来constructor存在形式。由上面的代码我们总结出结论1:上面的代码在控制台可以看出constructor是指向构造器Fruit的引用。这个地方就有点奇怪了。这个constructor到底指向的是那个实例的构造器?

js设备判断_判断移动端还是PC端?判断android还是ios?判断移动端浏览器类型?

js判断用户的浏览设备是移动设备还是PC?判断详细浏览器设备信息。判断微信、新浪、QQ打开。判断是android系统还是ios系统...

js中的相等性判断

Js提供了三种不同的比较操作符===,==,Object.is。ECMAScript 提供了四种比较操作符:非严格相等(==)、严格相等(===)、零值相等、同值相等。

Js实现点击查看全文(类似今日头条、知乎日报效果)

这篇文章主要为大家详细介绍了原生JS+css仿QQ今日头条、知乎日报点击查看全文的效果,具有一定的参考价值,感兴趣的小伙伴们可以参考一下.

js浮点数精度丢失问题_如何解决js中浮点数计算不精准?

理解javascript中浮点数计算不精准的原因,如何解决浮点数的四则运算(加减乘除)。js中除了toFixed方法以外的实现方法总汇

js变量引用(指针)

基本类型:Number,Boolen,null,String,Underfined 存放在栈内存中,数据长度是固定的。引用类型:Object存在堆内存中,数据长度是变化的(同时有栈内存中有一个指针指向这个Object的)。

instanceof与constructor的区别

instanceof 的作用是判断实例对象是否为构造函数的实例,实际上判断的是实例对象的__proto__属性与构造函数的prototype属性是否指向同一引用;constructor 的作用是返回实例的构造函数,即返回创建此对象的函数的引用

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!