稳定的排序，即最小干扰性排序 [英] Stable Sorting, ie, Minimally-Disruptive Sorting

问题描述

假设我有一个事物列表(数字，为了使事情在这里简单)，并且我想使用一个函数使用SortBy对其进行排序. 例如，以下内容按最后一位对数字列表进行排序:

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]&]

请注意，这些数字中的两个(即全部)如何具有相同的最后一位数字. 因此，退回它们的顺序无关紧要. 在这种情况下，Mathematica会以相反的顺序返回它们. 我该如何确保打破所有联系以支持原始列表中商品的订购方式?

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?

(我知道这很琐碎，但是我感觉不时出现这种情况，所以我认为在StackOverflow上获取它会很方便.如果没有人打败，我会把我想出的一切都作为答案我来吧.)

(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:感谢尼古拉斯指出这被称为稳定排序.它在我的舌尖上！这是另一个链接: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

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: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

推荐答案

问了问后，我得到了令人满意的解释:

After asking around, I was given a satisfying explanation:

简短的回答:您希望SortBy[list, {f}]得到稳定的排序.

Short answer: You want SortBy[list, {f}] to get a stable sort.

长答案:

SortBy[list, f]按照对列表的每个元素应用f所确定的顺序对列表进行排序，使用排序"中解释的规范顺序来<打破联系. (这是 SortBy文档中的第二个文档更多信息"注释. )

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}]使用将g应用于每个元素所确定的顺序来打破平局.

SortBy[list, {f, g}] breaks ties using the order determined by applying g to each element.

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

SortBy[list, {f}]不会打破平局(并给出稳定的排序)，这就是您想要的:

SortBy[list, {f}] does no tie breaking (and gives a stable sort), which is what you want:

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}].

Finally, sakra's solution SortBy[list, {f, tie++ &}] is effectively equivalent to SortBy[list, {f}].

这篇关于稳定的排序，即最小干扰性排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！