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

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

输出如下:



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

JavaScript 进阶问题列表

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

JS 中的垃圾回收

对于开发者来说,JavaScript 的内存管理是自动的、无形的。我们创建的原始值、对象、函数……这一切都会占用内存。当某个东西我们不再需要时会发生什么?JavaScript 引擎如何发现它、清理它?

TS与JS中的Getters和Setter究竟有什么用?

在本文中,我们讨论了getter 和 setter 在现代 Web 开发中的实用性。它们有用吗?什么时候使用它们是有意义的?尽管我不同意 getter 和 setter 完全是一个反模式。但它们在几种情况下能带来更多的实用性。

JS中for循环的常见题型

for循环示例;让用户输入行数,使用for循环嵌套打出倒着的星星出来,行数等于用户输入的数字 ;有1,2,3,4这么4个数,能组成多少个互不相同且不含有重复数字的三位数?都是多少?

javascript:void(0)的含义

首先,void关键字是javascript当中非常重要的关键字,该操作符指定要计算或运行一个表达式,但是不返回值。语法格式:void func()、void(func())

前端基础之BOM和DOM

JavaScript分为 : ECMAScript,DOM,BOM。BOM(Browser Object Model)是指浏览器对象模型,它使 JavaScript 有能力与浏览器进行“对话”。DOM (Document Object Model)是指文档对象模型

解密JavaScript执行上下文

首先我们先了解一下什么是执行上下文栈(Execution context stack)。分别展示了栈、堆和队列,其中栈就是我们所说的执行上下文栈;堆是用于存储对象这种复杂类型,我们复制对象的地址引用就是这个堆内存的地址

javascript中的依赖注入

使用没有依赖的模块,显然这是很难实现的。即使你创建了很好的像黑盒一样的组件,但总有个将所有部分合并起来的地方。这就是依赖注入起作用的地方,当前来看,高效管理依赖的能力是迫切需要的,本文总结了原作者对这个问题的看法。

js中&与&&,|与||的区别

&、|、~都是位操作符,而&&、|、~|都是逻辑操作!。&&是逻辑与运算符假前真后,||是逻辑或运算符真前假后,&是按位与操作两个数值的个位分别相与,同时为1才得1,只要一个为0就为0。

Js常用基础算法

冒泡排序;插入排序 过程就像你拿到一副扑克牌然后对它排序一样;快速排序;回文字符串;翻转字符串;字符串中出现最多次数的字符;数组去重;二分查找

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

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

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