JavaScript算法---排序(计数排序)【6】
2021/9/18 17:07:18
本文主要是介绍JavaScript算法---排序(计数排序)【6】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 该算法于1954年由 Harold H. Seward提出,通过计数将时间复杂度降到了O(N+k)。
- 计数排序分布式排序
原理:需要创建一个临时数组,存放出现的次数。等所有元素都计数完成后,迭代临时数组构建排序后的结果。
function countingSort(array) { if (array.length < 2) { // 如果待排序数组为空或只有一个元素,则不需运行排序 return array; } const maxValue = Math.max(...array); // {2} 从索引0开始,找到数组中的最大值 const counts = new Array(maxValue + 1); // {3} 创建计数数组,比如最大值为3,则创建4个,最后一个下标为3 array.forEach((element) => { if (!counts[element]) { // {4} 如果计数某个元素一开始没有初始化,则赋值为0 counts[element] = 0; } // 给计数数组对应的下标加 counts[element]++; // {5} }); // 辅助索引,帮助我们将值赋值到结果数组中的正确位置 let sortedIndex = 0; counts.forEach((count, i) => { while (count > 0) { // {6} array[sortedIndex++] = i; // {7} count--; // {8} } }); return array; } console.log(countingSort([3,5,1,9,2]));
满足下列2点可以最大程度发挥计数排序的优势
- 排序的元素必须是整数
- 排序元素的取值要在一定范围内,并且比较集中
这篇关于JavaScript算法---排序(计数排序)【6】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)