计数排序是一个非基于比较的[排序算法],该算法于1954年由 Harold H. Seward 提出。 它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围), 快于任何比较排序算法。
[1] 当然这是一种牺牲空间换取时间的做法, 而且当O(k)>O(n\*log(n))的时候其效率反而不如基于比较的排序 (基于比较的排序的时间复杂度在理论上的下限是O(n\*log(n)), 如归并排序,堆排序)
以上是 百度百科 (最近无法科学上网..)关于 记数排序 的描述。核心点如下:
非比较排序就是说 不比较数组中元素的大小关系。而是通过记录索引的方式巧妙的将原数组进行排序。这样说比较绕,接下来就分步骤说明:
比如说,现在有一个这样的数组:
const arr = [2,1,2,2,3,8,5,5,9]
如果要对其进行记数排序的话,大概需要这几步:
1. 定义累计数组 其中length是原数组的最大值+1
// 原数组最大值
const max = Math.max(...arr);
// 定义一个累计数组 数组长度是最大值+1 元素都是0
// 累计数组第一位的空位0 所以长度要+1
const _arr = new Array(max + 1).fill(0);
2. 将原数组中的值转换为累计数组的索引
将原数组中的值转换为累计数组的索引,遇到重复的元素,就在累计数组中进行累加。
比如: 在原数组中的元素1出现了1次,那么在累计数组中索引为1的元素的值为1。在原数组中的元素2重复出现了3次,那么在累计数组中索引为2的元素的值为3。在原数组中的元素5重复出现了2次,那么在累计数组中索引为5的元素的值为2。
其他以此类推。此时累计数组就变成了:(其实通过此步,就已经将数组排好序了,因为值越大 索引越靠后)
_arr = [0,1,3,1,0,2,0,0,1,1]
3. 将累计数组进行累加,计算最终要回写的位置
为什么要累加呢?仔细想想 累加的是什么? 是值吗?表面上是累计数组中的值进行累加,其实本质上是原数组的索引进行累加,因为最终要通过该索引确定原数组中各个元素的位置。
从累计数组的第2个元素开始(因为累计数组中的第一个元素是空位0),它的每一项等于它前一项+它本身的和。这样做的目的是为了计算出最终要回写到结果数组的索引。
for(let i = 1; i < _arr.length; i++){
// 它的每一项 等于 它的前一项 加 它本身的和
_arr[i] = _arr[i-1] + _arr[i];
}
计算完毕后,此时的累计数组就变成了:
[0,1,4,5,5,7,7,7,8,9]
4.通过最终的累计数组的值来确定最终结果数组的每个元素的最终索引
因为通过第三步,就完整的记录了原数组的值(累计数组索引)和原数组的索引(累计数组值)。那既然有了索引和值,一个数组不就确定了吗?
// 定义一个结果数组result_arr
// 数组长度和arr相同 用来保存最后结果
let result_arr = new Array(arr.length)
// 循环原数组
for (let j = 0; j < arr.length; j++) {
const p = _arr[arr[j]] - 1; // 获取最终要回写的索引
_arr[arr[j]]--; // 新的回写位置 以防万一 如果原数组中有相同的大小的元素 那么第二个元素要写入下一个 所以要-1
result_arr[p] = arr[j];
}
/**
* 记数排序
* @param {要排序的数组} arr
*/
function counting_sort(arr) {
// 最大值
const max = Math.max(...arr);
// 累计数组
const _arr = new Array(max + 1).fill(0);
// 结果数组
const result_arr = new Array(arr.length);
// 累计位递增 将arr中的元素数一遍 根据序号+1
arr.forEach((item, i) => _arr[arr[i]]++);
// 累计求和
for (let i = 1; i < _arr.length; i++) {
_arr[i] = _arr[i - 1] + _arr[i];
}
// 最终结果
for (let j = 0; j < arr.length; j++) {
const p = _arr[arr[j]] - 1;
_arr[arr[j]]--;
result_arr[p] = arr[j];
}
return result_arr;
}
const arr = [2, 1, 2, 2, 3, 8, 5, 5, 9];
console.log(counting_sort(arr));
/*
[
1, 2, 2, 2, 3,
5, 5, 8, 9
]
*/
本文内容仅供个人学习/研究/参考使用,不构成任何决策建议或专业指导。分享/转载时请标明原文来源,同时请勿将内容用于商业售卖、虚假宣传等非学习用途哦~感谢您的理解与支持!
有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法
使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。
给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。
racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。
JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题
这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!