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

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

输出如下:



JS 超类和子类

看到javascript高级程序设计的面向对象章节看到超类与子类这个概念词,不懂上度娘查了才知道是怎么一回事。说到超类与子类,就不得不提起原型模式,原型对象,原型链与原型链继承了

js中void 0 与 undefined

偶然看到一个问题:为什么有的编程规范要求用 void 0 代替 undefined?如果不知道这个答案的小伙伴,第一反应就要问void 0是什么鬼?

document.write和innerHTML的区别

document.write只能重绘整个页面,innerHTML可以重绘页面的一部分。 document.write是直接写入到页面的内容流,如果在写之前没有调用document.open, 浏览器会自动调用open。

js中delete关键字

delete关键字的作用:删除对象的属性 语法:delete 对象.属性、可以删除没有使用var关键字声明的全局变量(直接定义在window上面的属性)、删除数组元素、不能删除内置对象的属性、不能直接删除从原型上继承的属性

js的微任务和宏任务

宏任务:当前调用栈中执行的代码成为宏任务。微任务: 当前(此次事件循环中)宏任务执行完,在下一个宏任务开始之前需要执行的任务,可以理解为回调事件。

谈谈super(props) 的重要性

我听说 Hooks 最近很火。讽刺的是,我想用一些关于 class 组件的有趣故事来开始这篇文章。你觉得如何?本文中这些坑对于你正常使用 React 并不是很重要。 但是假如你想更深入的了解它的运作方式,就会发现实际上它们很有趣。

js中async与defer

async 异步加载,立即下载,不应妨碍页面其他操作,标记为 async 的异步脚本并不保证按照指定的先后顺序执行,用async很容易出错,async 是无序执行,自身加载完就会执行;

instanceof与constructor的区别

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

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

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

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

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

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

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

小程序专栏: 土味情话心理测试脑筋急转弯幽默笑话段子句子语录