稳定排序,即最小破坏性排序

Question

假设我有一个事物列表(数字,为了简化这里),我有一个函数,我想用它来排序,使用SortBy.例如,以下按最后一位数字排序数字列表:

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

And notice how two of (ie, all of) those numbers have the same last digit. So it doesn't matter which order we return them in. In this case Mathematica returns them in the opposite order. How can I ensure that all ties are broken in favor of how the items were ordered in the original list?

(I know it's kind of trivial but I feel like this comes up from time to time so I thought it would be handy to get it on StackOverflow. I'll post whatever I come up with as an answer if no one beats me to it.)

Attempts at making this more searchable: sort with minimal disturbance, sort with least number of swaps, custom tie-breaking, sorting with costly swapping, stable sorting.

PS:感谢Nicholas指出这称为稳定排序.这是我的舌尖!这是另一个链接:http: //planetmath.org/encyclopedia/StableSortingAlgorithm.html

Answer 1

在四处询问之后,我得到了一个令人满意的解释:

简短的回答:你想SortBy[list, {f}]获得一个稳定的排序.

答案很长:

SortBy[list, f]按照通过将f应用于列表的每个元素确定的顺序对列表进行排序,使用在排序下解释的规范排序来断开关系.(这是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}].

Answer 2

GatherBy能做你想做的吗？

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

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}