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

时间: 2017-12-21阅读: 1855标签: 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.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

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

js变量引用(指针)

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

理解js中prototype和__proto__和的区别和作用?

在js中有句话叫一切皆对象,而几乎所有对象都具有__proto__属性,可称为隐式原型,除了Object.prototype这个对象的__proto__值为null。Js的prototype属性的解释是:返回对象类型原型的引用。每个对象同样也具有prototype属性,除了Function.prototype.bind方法构成的对象外。

js常见知识点整理总结

一些常用的JavaScript 知识点整理,包括:两个函数是否等价、NaN是什么?它是什么类型?如何检测一个变量是否是NaN?作用域相关问题?js小数计算不准确的bug,js算法/思路相关,js类型强制转换

深入理解javascript中的事件循环event-loop

人们把javascript调控同步和异步任务的机制称为事件循环,首先来看事件循环机制的可视化描述,主线程运行的时候,产生堆和栈,栈中的代码调用各种外部API,异步操作执行完成后,就在消息队列中排队。

js可以设置网页默认为横屏状态吗?js设置网页横屏和竖屏切换

打开页面时通过 window.orientation 可以判断网页是横屏还是竖屏,如果是竖屏,给整个页面添加样式 transform: rotate(90deg); 这样,你的页面就显示横屏的效果了。 总的来说,结合window.orientationchange和window.orientation可以灵活的对网页进行变换。

javascript怎么判断按钮被点击?

JavaScript可以通过Event对象的target事件或srcElement(IE浏览器支持)来判断按钮是否被点击。Event对象代表事件的状态,比如事件在其中发生的元素、键盘按键的状态、鼠标的位置、鼠标按钮的状态。

JavaScript中的循环和作用域

JavaScript有一个特点,也许会让开发者头痛, 是与循环和作用域相关的.const。最简单的方案是用 let 声明、另外一个非常普遍的解决这个问题是使用pre-ES6代码, 同时它被称作即时调用函数表达式(IIFE)

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

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

javascript的Object. hasOwnProperty方法

hasOwnProperty() 方法会返回一个布尔值,指示对象自身属性中(非继承属性)是否具有指定的属性,如果 object 具有带指定名称的属性,则 hasOwnProperty 方法返回 true,否则返回 false。

js中的相等性判断

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

点击更多...

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