自定义数组排序算法
所以我想出了一种“新”排序算法：
function indexSort(array, min, max) {
var newArray = Array.from({length:Math.abs(max-min)}, () => 0);
for (let i = 0; i < max; i++) {
if (array.includes(array[i])) {
newArray[array[i]] = array[i];
}
}
for (let i = 0; i < newArray.length; i++) {
if (newArray[i] == 0) {
newArray.splice(i, 1);
i--;
}
}
return newArray;
}该算法按升序对数字进行排序，因此：
Input -> Output
indexSort([ 3, 1, 2 ], 1, 3) -> [ 1, 2, 3 ]
indexSort([ 64, 12, 9 ], 9, 64) -> [ 9, 12, 64 ]该算法对数组进行排序，速度相当慢，在当前状态下，与其他排序算法相比，它有一些主要的缺点：
- 只适用于正整数。
- 必须循环整个数组两次。
- 不允许重复的项目。
它可能还有其他的缺点，我目前无法想象。
所以我想知道的是：
- 为什么这个排序算法这么慢？
- 是否可以使用
else语句在一个循环中完成所有操作？ - 为什么这种类型的性能要好于泡泡排序呢？
- 这个算法的大O符号是什么？
- 这是否已经被发现，如果是的话，它的名字是什么？
回答 1
Code Review用户
发布于 2021-10-12 09:51:07
我将试着把评论中所说的话总结成一个答案，然后再加上我的两分钱。
首先，我认为这是因为您对如何排序数字有了一个想法，只是尝试实现它，看看它是如何工作的。这没什么错，但正如前面说过的，排序算法经过了很好的研究，如果它满足某种类型的需求(例如，循环排序 )，那么使用内建方法或实现其他人的算法总是更好。不快，但使用最小写入)。这并不意味着你不应该再乱搞排序，因为这可能是一个很好的方法来了解他们是如何工作和为什么。
至于算法，您的想法似乎如下：
- 创建一个适合每个数字的数组
- 使用它们的值作为索引，将它们所属的数字放在
- 移除所有填充物
现在，min / max参数的用途是明确的，它们用于限制步骤1数组的大小。正如@ggorlen所说，这种信息通常不会给出排序算法。如果需要这样做，您可能会迭代输入数组并以这种方式找到它们。这还可以防止向算法提供虚假值，从而导致无效输出(例如:给出1,2,3,4，2，2作为args生成<1空value>，1，2)。
至于复杂性，它至少是O(n平方)。过于简化的原因是，您在O(n)中迭代整个数组，在每次搜索或拼接(再次是O(n) )时，都会产生O(N)。但是，由于循环不是在n上迭代，而是在一个大小为max的数组上迭代，所以您的复杂度可能要高得多，如@ggorlens中关于[12341231, 143]大小写的注释所示。这个评论还回答了为什么气泡排序比它更好的问题；在一个数组上进行的不是一次，而是两次气泡排序复杂性的传递，这个数组可能比一个气泡排序所要处理的要大得多。
据我所知，这一点还没有被发现，可能是因为它没有现有算法那么快，也没有博戈索、走狗分类或斯大林排序那么有趣。
作为最后一点，计数排序可能对你很感兴趣。
https://codereview.stackexchange.com/questions/268889
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号