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

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

输出如下:



Web Worker 详细介绍_Web Workers的使用

web worker 是运行在后台的 JavaScript,独立于其他脚本,也就是说在Javascript单线程执行的基础上,开启一个子线程,进行程序处理,而不影响主线程的执行。Service Worker 是一个由事件驱动的 worker,它由源和路径组成,以加载 .js 文件的方式实现的。

数字在JavaScript中是如何编译的

JavaScript中的所有数字都是浮点数。这篇博客文章解释了这些浮点数如何在64位二进制内部表示。浮点数并不一定等于小数,定点数也并不一定就是整数。所谓浮点数就是小数点在逻辑上是不固定的,而定点数只能表示小数点固定的数值

window.location.href的用法(动态输出跳转)

javascript中的location.href有很多种用法,window.location.href 语句可以实现一个框架的页面在执行服务器端代码后刷新另一个框架的页面

js的解析的两个阶段_预解析阶段、执行阶段

js不像C语言那样只要编译一次之后成.exe文件之后就不用在编译可以直接使用了,js是一种解释型语言,js同理是边解析边执行。js的解析分为两个阶段 1.预解析阶段 2.执行阶段。

js秒数转换成时分秒_js如何将秒拼接为时分秒显示?

接口返回的是int类型的秒数,在前端显示要求拼接为时分秒显示,这篇文章主要讲解实现js秒数转换成时分秒的方法。

JavaScript中变量提升和函数提升的意义理解

在ES6之前,Js中是没有块级作用域的,只存在全局作用域和函数作用域。变量提升即将变量声明提升到它所在作用域的最开始的部分;函数提升只有函数声明中才发生。

JavaScript中公有、私有、静态、受保护的属性和方法

在开发中,我们需要限制某些属性和方法的暴露程度,使得它们不能通过对象实例本身被访问、修改或调用。要了解js面向对象,就必需先了解js中什么是公有、私有、静态、受保护。

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

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

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

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

javascript中关键词in用法介绍【js 关键字 in 的使用方法】

js中关键词...in... 从字面上理解就是什么在什么中,在js中差不多也是表达这个意思,主要作用:1用于数组和对象的判断、2 遍历数组或者对象