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

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

输出如下:



JavaScript中的魔幻代理Proxy

什么是 JavaScript 代理?通过 Proxy 我们可以拦截并改变一个对象的几乎所有的根本操作,包括但不限于属性查找、赋值、枚举、函数调用等等。利用 Proxy,我们可以拦截并不存在的属性的读取

适配器在JavaScript中的体现

适配器设计模式在JavaScript中非常有用,在处理跨浏览器兼容问题、整合多个第三方SDK的调用,都可以看到它的身影。适配器模式是一种软件设计模式,允许从另一个接口使用现有类的接口。它通常用于使现有的类与其他类一起工作,而无需修改其源代码。

JavaScript中的循环和作用域

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

JavaScript中的行为委托

行为委托简单来说就是一种设计模式,不同于传统的构造函数的类式设计。这里每个例子会通过构造函数,class和行为委托来不同实现,不过不会评论class,是否使用class取决于你的观点。

打造自己的JavaScript武器库

作为战斗在业务一线的前端,要想少加班,就要想办法提高工作效率。这里提一个小点,我们在业务开发过程中,经常会重复用到日期格式化、url参数转对象、浏览器类型判断、节流函数等一类函数,这些工具类函数

(...)这三个点在JavaScript中意味着什么?

解释JavaScript中三个点的作用:数组/对象扩展运算符、rest运算符(使用函数的参数时,无论是完全替换参数还是与函数的参数一起替换参数,这三个点也称为rest运算符)

await在forEach不起作用解决

我们知道await这个机制肯定是没问题的,如果真的有问题肯定不会轮到我测出来,那么其实剩下来的问题只能是for遍历的原因了。lodash的forEach和[].forEach不支持await,如果非要一边遍历一边执行await,可使用for-of

你不知道的 js 保留字

先是笼统的说一下有什么保留字,保留字的话根据犀牛书的划分,可有分为以下几类:基础保留字、严格模式下的保留字、严格模式下的不完全保留字、ECMAScript3的保留字、ECMAScipt 5 的保留字、全局变量和函数

js实现获取手机相册并上传

当初有很多人说使用form方法将文件封装来上传,可是因为要照顾到从相机中选择图片,所以一直没有去做。 后来看到了Uploader的方法来传文件,感觉自己找到了 。是使用plus.uploader来完成的

js中offset、scroll、event、client的区别和使用

用一句话概述:offset用于获取元素的实际显示尺寸 , scroll用于获取滚动后全部尺寸 , client用于获取不包括滚动条的实际显示尺寸,event用于获取鼠标的坐标位置。下面就详细介绍它们之间的使用和区别