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

时间: 2017-12-21阅读: 1315标签: 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.阿里云: 本站目前使用的是阿里云主机,安全/可靠/稳定。点击领取2000元代金券、了解最新阿里云产品的各种优惠活动点击进入

2.腾讯云: 提供云服务器、云数据库、云存储、视频与CDN、域名等服务。腾讯云各类产品的最新活动,优惠券领取点击进入

3.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

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

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

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

JavaScript 进阶问题列表

我在我的 Instagram 上每天都会发布 JavaScript 的选择题,并且同时也会在这个仓库中发布。从基础到进阶,测试你有多了解 JavaScript,刷新你的知识,或者帮助你的 coding 面试!

js判断日期是否为今天

需求如下:后端返回字符串数据,需要前端判断该日期是否为今天。比如返回日期格式为:2018-08-14,那么需要如何来实现呢,这篇文章整理实现的几种方式供大家参考。

js中async与defer

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

深入理解JS中引用类型和基本类型

javascript中基本类型指的是那些保存在栈内存中的简单数据段,即这种值完全保存在内存中的一个位置。 引用类型指那些保存在堆内存中的对象,意思是变量中保存的实际上只是一个指针,这个指针指向内存中的另一个位置,该位置保存对象。

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

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

javascript对dom的操作总汇,js创建,更新,添加,删除DOM的方法

HTML文档在浏览器解析后,会成为一种树形结构,我们需要改变它的结构,就需要通过js来对dom节点进行操作。dom节点(Node)通常对应的是一个标题,文本,或者html属性。

10个JavaScript难点:能够读懂这篇博客的JavaScript开发者,运气不会太差…

10个JavaScript难点包括:立即执行函数,闭包,使用闭包定义私有变量,prototype,模块化,变量提升,柯里化,apply, call与bind方法,Memoization,函数重载

WebSocket的原理及WebSocket API的使用,js中如何运用websocket

WebSocket是HTML5下一种新的协议,为解决客户端与服务端实时通信而产生的技术。其本质是先通过HTTP/HTTPS协议进行握手后创建一个用于交换数据的TCP连接

JavaScript 优雅的实现方式包含你可能不知道的知识点【转】

Js优雅的实现方式包含你可能不知道的知识点:简短优雅地实现 sleep 函数,js获取时间戳,js数组去重,js数字格式化,js交换两个整数,将 argruments 对象(类数组)转换成数组,数字取整等

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

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

小程序专栏: 土味情话心理测试脑筋急转弯幽默笑话段子句子语录成语大全运营推广