list - 稳定排序，即最小干扰排序

Question

假设我有一个事物列表（数字，以保持此处简单），并且我有一个函数我想使用 SortBy 对它们进行排序。例如，以下按最后一位数字对数字列表进行排序：

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

并注意这些数字中的两个（即所有）如何具有相同的最后一位数字。所以我们返回它们的顺序无关紧要。在这种情况下，Mathematica 以相反的顺序返回它们。我如何确保打破所有联系，以支持原始列表中的项目排序方式？

（我知道这有点微不足道，但我觉得这不时会出现，所以我认为在 StackOverflow 上获取它会很方便。如果没有人比我击败我，我会发布我想出的任何答案作为答案.)

尝试使其更易于搜索：以最小干扰排序，以最少交换次数排序，自定义平局，使用代价高昂的交换排序，稳定排序。

PS：感谢Nicholas指出这叫做稳定排序。它就在我的舌尖上！这是另一个链接：链接

score 24 · Accepted Answer

问了一圈后，得到了满意的解释：

简短的回答：你想得到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}].

score 6 · Accepted Answer

6

GatherBy 做你想做的事吗？

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

于 2010-07-22T11:11:39.220 回答

score 5 · Accepted Answer

有一个变体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}

score 3 · Accepted Answer

这似乎有效：

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

但现在我看到rosettacode提供了一种更好的方法：

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

所以订购是关键！似乎 Mathematica 文档没有提到排序和排序这个有时很重要的区别。

4 回答 4