稳定排序，即最小化干扰的排序

Question

假设我有一组东西（为了简单起见，这里是数字），我想使用SortBy函数按照某个函数进行排序。例如，以下代码通过最后一位数字对数字列表进行排序：

SortBy[{301, 201}, Mod[#,10]&]

请注意这些数字中有两个（或者全部）数字的末位相同。因此，以哪种顺序返回它们并不重要。在这种情况下，Mathematica 以相反的顺序返回它们。如何确保所有平局都有利于按原始列表中的顺序排序的项目？

（我知道这有点琐碎，但我觉得这种情况时不时会出现，所以我认为把它放在 StackOverflow 上会很方便。如果没有人比我更快地想出答案，我会把我想到的任何东西作为答案发布。）

尝试使其更易搜索：最小干扰排序、最少交换排序、自定义平局处理、代价高昂的交换排序、稳定排序。

附注：感谢Nicholas指出这被称为稳定排序。我差一点就想到了！这里是另一个链接：Link

- dreeves

---

这里寻找的东西通常不是被称为稳定排序算法吗？参见：http://en.wikipedia.org/wiki/Sorting_algorithm#Stability - Nicholas Knight

Answer 1

询问后，我得到了一个令人满意的解释：

简短回答：您想要使用SortBy[list, {f}]来获得稳定排序。

详细回答：

SortBy[list, f]按照将f应用于列表的每个元素所确定的顺序进行排序，使用在Sort下解释的规范排序方法来打破平局。（这是SortBy文档中第二篇记录的“更多信息”注释。）

SortBy[list, {f, g}]使用将g应用于每个元素所确定的顺序来打破平局。

请注意，SortBy[list, f]与SortBy[list, {f, Identity}]相同。

SortBy[list, {f}]不进行平局处理（并提供稳定排序），这正是您想要的：

In[13]:= SortBy[{19, 301, 201, 502, 501, 101, 300}, {Mod[#, 10] &}]

Out[13]= {300, 301, 201, 501, 101, 502, 19}

最后，sakra的解决方案SortBy[list, {f, tie++ &}]等效于SortBy[list, {f}]。

- Andrew Moylan

---

哇，谢谢你，安德鲁！我读了这个之后就像“你只是随便问问吗？你在哪工作，沃尔夫拉姆研究？”然后我点击了你的名字，发现你确实在那里工作。 :) 我一直对StackOverflow吸引的专业水平感到惊讶。非常感谢你在这里！ - dreeves

Answer 2

GatherBy是否符合您的要求？

Flatten[GatherBy[{301, 201, 502, 501, 101}, Mod[#, 10] &]]

- Mark Fisher

---

哦，可能是这样的，谢谢！我没有想到使用GatherBy。我倾向于采用Ordering解决方案。如果你感兴趣并想通过时间测试比较迄今为止的解决方案，我会选择你的答案作为被接受的答案。（哦，你的解决方案有一个问题：你应该使用Flatten[..., 1]，否则如果元素实际上是列表，那么Flatten会破坏它们。） - dreeves

我认为在接受的答案的光芒下，这现在已经没有意义了。 - dreeves

Answer 3

有一种SortBy的变体，可以通过使用额外的排序函数来打破关系：

SortBy（list，{f1，f2，...}）

通过计算关系，您可以获得稳定的排序：

Module[{tie = 0}, 
 SortBy[{19, 301, 201, 502, 501, 101, 300}, {Mod[#, 10] &, (tie++) &}]]

产量

{300, 301, 201, 501, 101, 502, 19}

- sakra

---

谢谢，我之前不知道！事实证明，正如被接受的答案所示，它甚至更简单。 - dreeves

Answer 4

这似乎有效：

stableSortBy[list_, f_] := 
  SortBy[MapIndexed[List, list], {f@First[#], Last[#]}&][[All,1]]

但是现在我发现Rosetta Code提供了一种更好的方法：

stableSortBy[list_, f_] := list[[Ordering[f /@ list]]]

因此，排序是关键！看起来Mathematica文档有时没有提到Sort和Ordering之间的这个重要区别。

- dreeves

---

这种方法在Lisp圈子里被称为“装饰-排序-去装饰”习语，即使GatherBy可能是特定情况下稳定排序的最佳方法，但它在Mathematica中是一个非常有用的技巧。 - Pillsy

我很好奇这个解决方案在速度上与GatherBy相比如何，这将取决于列表在内部的实现方式。我的问题是，GatherBy可能只会一次性处理每个列表元素，而Ordering解决方案则需要至少两次：一次用于排序，一次用于重新排序元素。对于小型列表，这可能无关紧要。但是，没有实际操作，我怀疑对于更长的列表，GatherBy将提供更优秀的性能。 - rcollyer

我认为在接受的答案的情况下，这一切都是无意义的。 - dreeves