Javascript排序算法之计数排序的实例

  次阅读 作者:智能小宝 来源:互联网 2016-01-26 10:57 我要评论(0)

计数排序是一种高效的线性排序,它通过计算一个集合中元素楚翔的次数来确定集合如何排列,计数排序不需要进行数据的比较,所有他的运行效率前面介绍的都高

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组Count_arr,其中第i个元素是待排序数组Arr中值等于i的元素的个数。然后根据数组Count_arr来将Arr中的元素排到正确的位置。

分为四个步骤:

1.找出待排序的数组中最大和最小的元素

2.统计数组中每个值为i的元素出现的次数,存入数组Count_arr的第i项

3.对所有的计数累加(从Count_arr中的第一个元素开始,每一项和前一项相加)

4.反向遍历原数组:将每个元素i放在新数组的第Count_arr(i)项,每放一个元素就将Count_arr(i)减去1

实例:

代码如下:

/**

* 计数排序是一个非基于比较的排序算法

* 该算法于1954年由 Harold H. Seward 提出。

* 它的优势在于在对一定范围内的整数排序时,

* 它的复杂度为 (n+k)(其中k是整数的范围),

* 快于任何比较排序算法

*

*/

function countSort(arr, min, max) {

var i, z = 0, count = [];

for (i = min; i <= max; i++) {

count[i] = 0;

}

for (i=0; i < arr.length; i++) {

count[arr[i]]++;

}

for (i = min; i <= max; i++) {

while (count[i]-- > 0) {

arr[z++] = i;

}

}

return arr;

}

// test

var i, arr = [];

for (i = 0; i < 100; i++) {

arr.push(Math.floor(Math.random() * (141)));

}

countSort(arr, 0, 140);

本站文章信息来源于网络以及网友投稿,本站只负责对文章进行整理、排版、编辑,是出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如果您有什么意见或建议,请联系QQ28-1688-302!

人工智能实验室
相关文章相关文章
  • 未来两年人工智能要怎么走?看这篇就够了

    未来两年人工智能要怎么走?看这篇就够了

  • 英国研发“杀生”机器人 通过生命体获取能量

    英国研发“杀生”机器人 通过生命体获取能量

  • 韩春雨称已能重复实验结果 近期将有消息公布

    韩春雨称已能重复实验结果 近期将有消息公布

  • 无人驾驶汽车如何改变城市生活?听听他们怎么说

    无人驾驶汽车如何改变城市生活?听听他们怎么说

网友点评网友点评
阅读推荐阅读推荐

据国外媒体报道,在过去两年内,聊天机器人(chatbot)、人工智能以及机器学习的研发和采用取得了巨大进展。许多初创公司正利用人工智能和...

霍金 视觉中国 图 英国著名物理学家霍金(Stephen Hawking)再次就人工智能(AI)发声,他认为:对于人类来说,强大AI的出现可能是最美妙的...

文|郑娟娟 今年,人工智能(AI) 60岁了。在AI60岁的时候,笔者想要介绍一下AI100,一个刚刚2岁的研究项目,但它的预设寿命是100年,甚至更长...

AlphaGo与李世石的人机大战,为大众迅速普及了人工智能的概念。 但对谷歌而言,除了下围棋,现在的人工智能进展到哪一步了?未来,人工智能...