社区讨论

关于“新”排序算法的想法

学术版参与者 9已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mk707w5r
此快照首次捕获于
2026/01/09 23:01
上个月
此快照最后确认于
2026/01/11 22:15
上个月
查看原帖
如果一个长度为 100100 的序列,里面的元素是将 11001\sim100 随机打乱,那么升序排序后数字 ii 就会位于下标 ii 的位置。
于是我想到类似的方法。对于一个长度为 nn 的序列,值域为 [l,r][l,r],那么对于序列中的数字 xx 就分配到一个预期的下标
xlrl×n\left\lfloor\dfrac{x-l}{r-l}\times n\right\rfloor
对于 x>yx>yxx 的预期下标一定不小于 yy
当然,值相近的数字可能会被分配到同一个下标下,那就对 1,,n1,\dots,n 检查,如果下标被分配到的所有数相同就不管了,否则就按照上述办法继续分治。
求问正确性和复杂度,或者是不是已有算法。

回复

14 条回复,欢迎继续交流。

正在加载回复...