问题标签 [stable-sort]

我假设 stdlib 中良好的旧 qsort 函数不稳定，因为手册页没有说明它。这是我正在谈论的功能：

我假设如果我将比较函数更改为也包括我正在比较的地址，它将是稳定的。那是对的吗？

例如：

我认为问题标题很清楚：stable_sort() 是否可以在 C++ 中使用 std::list？还是我必须将其转换为 std::vector？

我问是因为我尝试了一个简单的示例，它似乎需要 RandomAccessIterators，而链表没有。那么，如何稳定排序 std::list()？

编辑：给我一个错误的示例代码：

g++ 给了我大约 30 行错误（太长无法粘贴），其中一些是指 RandomAccessIterators（以及称为 _merge_sort_loop 的东西）。这有点奇怪，因为我已经看到了一些链表的合并排序实现，它们几乎是“顺序的”。

该文档不保证这一点。还有其他地方记录吗？

我猜它可能是稳定的，因为列表上的 sort 方法保证稳定（注意第 9 点：“从 Python 2.3 开始，sort() 方法保证稳定”），并且 sorted 在功能上相似。但是，我无法找到任何明确的来源。

目的：如果主键在两条记录中相等，我需要根据主键和辅助键进行排序。如果 sorted() 保证稳定，我可以先按次键排序，再按主键排序，得到我需要的结果。

PS：为避免任何混淆，我使用 stable 的意思是“如果保证不改变比较相等的元素的相对顺序，则该排序是稳定的”。

我已经定义了一个结构 ABC 来包含一个 int ID、字符串名称、字符串 LAST_NAME；
我的程序是这样的：从输入文件中读取一行。将每一行解析为名字和姓氏并插入到 ABC 结构中。此外，结构的 ID 由输入行的编号给出。

然后，将结构 push_back 放入向量主列表中。我还将这些散列到定义为 vector<vector> 的散列表中，使用名字和姓氏作为关键字。那是，

如果我的数据是：
Garfield Cat
Snoopy Dog
Cat Man

然后将关键字 cash 哈希到包含 Garfield Cat 和 Cat Man 的向量。我再次使用 push_back 将结构插入哈希表。

问题是，当我在我的主列表上调用 stable_sort 时，我的哈希表由于某种原因受到影响。我认为这可能会发生，因为歌曲的排序方式不同，所以我尝试制作主列表的副本并对其进行排序，尽管原始主列表不受影响，但它仍然会影响哈希表。

任何想法为什么会发生这种情况？

编辑-发布的源代码：

这里是主要的

这是哈希表插入实现的片段：

假设我的输入是 ( a,b并c区分相等的键)

我的计数排序将另存为（丢弃a,b和c信息！！）

这会给我结果

那么，这种稳定的排序如何？我不确定它是如何“保持具有相等键的记录的相对顺序”的。

请解释。

考虑以下问题。

我们得到一个属于两个类的元素数组：红色或蓝色。我们必须重新排列数组的元素，以便所有蓝色元素排在第一位（所有红色元素紧随其后）。必须以稳定的方式进行重新排列，这意味着必须保留蓝色元素的相对顺序（红色元素也是如此）。

是否有一种聪明的算法可以就地执行上述重新排列？

当然，非就地解决方案很简单。

一个明显的就地解决方案是将任何稳定的排序算法应用于数组。然而，在数组上使用成熟的排序算法直觉上感觉有点过头了，特别是考虑到我们只处理两类元素的事实。

任何想法都非常感谢。

我知道 ECMA 脚本规范没有指定使用哪种算法对数组进行排序，也没有指定排序是否应该是稳定的。

我找到了 Firefox 的此信息，它指定 firefox 使用稳定的排序。

有人知道 IE 6/7/8、Chrome 和 Safari 吗？

我刚刚在Table.sort上阅读官方Lua 文档，并注意到它说：

“[Table.sort] 算法不稳定；也就是说，给定顺序认为相等的元素可能会因排序而改变它们的相对位置。”

任何想法什么时候Table.sort会在 Lua 中变得稳定？

我试图理解这篇论文：Stable minimum space partitioning in linear time。

该主张的一个关键部分似乎是

算法 B在 O(nlog ₂ n)时间和恒定额外空间内稳定地排序大小为n的位数组，但只进行O(n)次移动。

但是，该论文没有描述该算法，而仅引用了我无法访问的另一篇论文。我可以找到几种在时间范围内进行排序的方法，但是我很难找到一种既能保证 O(N) 移动又不需要超过恒定空间的方法。

这个算法B是什么？换句话说，给定

是否有一个函数可以使用PredicateB(Item* a, size_t N);作为排序键对 Predicate进行稳定排序，对 Predicate 的调用少于 nlog _{2 n，并且只对}a执行 O(N) 写入操作？

我有特定顺序的 ID

我需要查询集中的专辑，其顺序与 id 在album_ids. 任何人请告诉我如何维持订单？或者像在album_ids 中那样获取专辑？