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

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

javascript中什么是句柄?

一个句柄是指使用的一个唯一的整数值,即一个4字节(64位程序中为8字节)长的数值,来标识应用程序中的不同对象和同类中的不同的实例。

javascript不可变性是什么?

不可变性即某个变量在进行了某个操作之后,其本身没有发生变化,比如对于字符串而言,对字符串的任何操作都会改变字符串本身的值,而是在字符串的基础上复制出来一个然后再改变,这样我们就说是不可变的

为什么javascript不起作用?

JavaScript是一种属于网络的脚本语言,已经被广泛用于Web应用开发,常用来为网页添加各式各样的动态功能,为用户提供更流畅美观的浏览效果。通常JavaScript脚本是通过嵌入在HTML中来实现自身的功能的。

javascript怎么判断按钮被点击?

JavaScript可以通过Event对象的target事件或srcElement(IE浏览器支持)来判断按钮是否被点击。Event对象代表事件的状态,比如事件在其中发生的元素、键盘按键的状态、鼠标的位置、鼠标按钮的状态。

javascript由几部分组成?

JavaScript有三部分组成。分别为核心(ECMAScript) 、文档对象模型(DOM)、浏览器对象模型(BOM)。这三部分分别描述了该语言的语法和基本对象、处理网页内容的方法和接口、与浏览器进行交互的方法和接口。

Js输出方式有哪些?

在编写JavaScript代码的时候, 一定要记住每一句代码后面都需要添加一个分号, 并且这个分号必须是英文的分号,我们会发现有时候不写分号程序也能够运行, 这里并不是因为不需要分号, 而是浏览器自动帮助我们添加了分号

7个常见的 JavaScript 测验及解答

我相信学习新事物并评估我们所知的东西对自己的进步非常有用,可以避免了我们觉得自己的知识过时的情况。在本文中,我将介绍一些常见的 JavaScript 知识。请享用!

Js中constructor指向问题

首先用一个例子指出来constructor存在形式。由上面的代码我们总结出结论1:上面的代码在控制台可以看出constructor是指向构造器Fruit的引用。这个地方就有点奇怪了。这个constructor到底指向的是那个实例的构造器?

javascript难点是什么?

javascript难点是什么?下面本篇文章就来给大家介绍一下10个JavaScript难点,感兴趣的小伙伴们可以参考一下,希望对大家有所帮助。立即执行函数,即Immediately Invoked Function Expression (IIFE),正如它的名字

Js如何获取ul中li的个数?

javascript如何获取ul中li的个数?下面本篇文章就来给大家介绍一下使用javascript获取ul中li个数的方法,希望对大家有所帮助。

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

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

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