代码之家 › 专栏 › 技术社区 › Steve Lorimer

从全局排序顺序排序n个不同列表的算法

sorting algorithm

Steve Lorimer · 技术社区 · 6 年前

我有N个项目列表

如:

它们被平展成一个长列表,用户根据自己的喜好选择一个顺序

如:

1, C, X, 3, B, A, Y, Z, 2, W, D, V

我需要重新排序n个原始列表,以便它们的相对排序顺序与用户的排序顺序相匹配

如:

简单的暴力方法是创建n个新的空容器,循环遍历用户的顺序,并在遇到时将每个项添加到相关容器中。

有没有更优雅的方法?

2 回复 | 直到 6 年前

corsiKa 6 年前

除非可以对数据的顺序作出假设,否则不可能有更优雅的方法。

您必须在某个时刻创建n个新容器中的每一个。

您还必须在某些时候向这些n个容器添加必要的元素。

这两件事是不可避免的。你的方法既有这些又没有更多,因此被证明是最小的。

一个小小的警告是块数组拷贝比迭代拷贝稍快,因此如果您知道相同的大块,那么您可以为这些块制作稍快的拷贝。但通常,为了获得这些信息,你必须首先访问并分析数据。因此,您不应该访问和分析,而应该访问并插入。

btilly 6 年前

您必须存储元素在开始时来自哪个容器的知识,或者存储元素到列表中位置的映射并将其用于排序。(或者节省内存并进行大量搜索。)

如果要重新排列所有列表,那么存储每个元素来自哪个容器的知识并按照您的建议进行操作会更有效。如果您只想重新排列一些列表(或重新排列将来的列表),那么将元素映射存储到列表中的位置并基于此进行排序可能更有意义。你可以用一个经过查找的比较函数,或者用一个 Schwartzian transform .

顺便问一下,你有没有想过如何处理重复的元素?

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前