稳定排序，即最小破坏性排序
假设我有一个事物列表（数字，为了简单起见），并且我有一个想要用来对它们进行排序的函数，使用 SortBy。 例如，以下按最后一位数字对数字列表进行排序：
SortBy[{301, 201}, Mod[#,10]&]
并注意这些数字中的两个（即所有）如何具有相同的最后一位数字。 因此，我们以哪种顺序返回它们并不重要。 在这种情况下，Mathematica 以相反的顺序返回它们。 我如何确保所有关系都被打破，有利于原始列表中的项目排序方式？
（我知道这有点微不足道，但我觉得这种情况时不时地会出现，所以我认为在 StackOverflow 上获取它会很方便。如果没有人比我更胜一筹，我会将我想到的任何内容作为答案发布.)
尝试使其更易于搜索：以最小的干扰进行排序，以最少的交换次数进行排序，自定义打破平局，以昂贵的交换进行排序，稳定排序。
Suppose I have a list of things (numbers, to keep things simple here) and I have a function I want to use to sort them by, using SortBy.
For example, the following sorts a list of numbers by last digit:
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: Thanks to Nicholas for pointing out that this is called stable sorting. It was on the tip of my tongue! Here's another link: Link
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
经过询问，我得到了令人满意的解释：
简短的回答：您希望
SortBy[list, {f}]获得稳定的排序。长答案：
SortBy[list, f]按照通过将 f 应用于列表的每个元素而确定的顺序对列表进行排序，使用 Sort 中解释的规范排序来打破联系。 （这是 SortBy 文档 中第二个记录的“更多信息”注释。 )SortBy[list, {f, g}]使用通过将 g 应用于每个元素而确定的顺序来打破平局。请注意，
SortBy[list, f]与SortBy[list, {f, Identity}]相同。SortBy[list, {f}]不会打破平局（并提供稳定的排序），这正是您想要的：最后，sakra 的解决方案
SortBy[list, {f, tie++ & ] }]实际上等同于SortBy[list, {f}]。After asking around, I was given a satisfying explanation:
Short answer: You want
SortBy[list, {f}]to get a stable sort.Long answer:
SortBy[list, f]sorts list in the order determined by applying f to each element of list, breaking ties using the canonical ordering explained under Sort. (This is the second documented "More Information" note in the documentation for SortBy.)SortBy[list, {f, g}]breaks ties using the order determined by applying g to each element.Note that
SortBy[list, f]is the same asSortBy[list, {f, Identity}].SortBy[list, {f}]does no tie breaking (and gives a stable sort), which is what you want:Finally, sakra's solution
SortBy[list, {f, tie++ &}]is effectively equivalent toSortBy[list, {f}].GatherBy 能满足您的要求吗？
Does GatherBy do what you want?
SortBy有一个变体，它通过使用附加排序函数来打破平局：SortBy[list,{f1, f2, ...}]通过计算平局，您可以获得稳定的排序：
产量
There is a variant of
SortBywhich breaks ties by using additional ordering functions:SortBy[list,{f1, f2, ...}]By counting ties you can thus obtain a stable sorting:
yields
这似乎有效：
但现在我看到 rosettacode 给出了一种更好的方法：
所以下单是关键！似乎 Mathematica 文档没有提到排序和排序这个有时很重要的区别。
This seems to work:
But now I see rosettacode gives a much nicer way to do it:
So Ordering is the key! It seems the Mathematica documentation makes no mention of this sometimes-important difference Sort and Ordering.