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

时间: 2017-12-21阅读: 668标签: 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));

输出如下:



instanceof与constructor的区别

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

前端与编译原理——用JS写一个JS解释器

说起编译原理,印象往往只停留在本科时那些枯燥的课程和晦涩的概念。作为前端开发者,编译原理似乎离我们很远,对它的理解很可能仅仅局限于“抽象语法树(AST)”。但这仅仅是个开头而已。编译原理的使用,甚至能让我们利用JS直接写一个能运行JS代码的解释器。

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

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

理解 JavaScript 执行栈

所有的 JS 代码在运行时都是在执行上下文中进行的。执行上下文是一个抽象的概念,JS 中有三种执行上下文:全局执行上下文,函数执行上下文,Eval 执行上下文。通常,我们的代码中都不止一个上下文,那这些上下文的执行顺序应该是怎样的?

一眼看穿JS变量,作用域和内存问题

这篇文章将梳理下环境,作用域链,变量对象和活动对象,以及内存管理问题。基本类型和引用类型的值,我们都知道JS中的数据类型有两大类,基本数据类型和引用数据类型,下面从三个方面来解剖他们

js基础_如何理解作用域和作用域链?

作用域外,无法引用作用域内的变量;离开作用域后,作用域的变量的内存空间会被清除,比如执行完函数或者关闭浏览器,作用域与执行上下文是完全不同的两个概念。我曾经也混淆过他们,但是一定要仔细区分。JavaScript代码的整个执行过程,分为两个阶段,代码编译阶段与代码执行阶段。

Js中的命名空间(namespace)

全局变量应该由有系统范围相关性的对象们保留,并且它们的命名应该避免含糊并尽量减少命名冲突的风险。在实践中,这意味着你应该避免创建全局对象,除非它们是绝对必须的。 所以你对此是怎么做的?传统方法告诉我们,最好的消除全局策略是创建少数作为潜在模块和子系统的实际命名空间的全局对象。

js 实现栈和队列

js实现栈或者队列有两种方式: 1.数组:数组本身提供栈方法(push,pop),队列方法(push,shift)。 2.链表:构造链表结构,说白了就是链表的插入(尾插),移除(栈:末尾节点移除,队列:头结点移除)

javascript的Object. hasOwnProperty方法

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

js常见知识点整理总结

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

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

广告赞助文章投稿关于web前端网站点搜索站长推荐网站地图站长QQ:522607023

小程序专栏: 土味情话心理测试脑筋急转弯