为什么是“不稳定排序”？被认为不好
只是想知道是否有人可以解释为什么“不稳定排序”被认为是不好的？基本上我看不到任何情况下它真的很重要。有人愿意提供一个吗？
Just wondering if someone could explain why an "unstable sort" is considered bad? Basically I don't see any situations where it would really matter. Could anyone care to provide one?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您有一个 GUI，允许人们通过单击该列对各个列进行排序，并且您使用稳定排序，那么了解的人可以通过单击 C 列对 A、B、C 列进行多列排序，按B、A的顺序。因为排序是稳定的，所以当您点击 B 时，B 下任何具有相同键的记录仍将按 C 排序，因此点击 B 后，记录将按 B、C 排序。同样，点击 A 后，记录将按 C 排序。由 A、B、C 编写
。（不幸的是，上次我在某些 Microsoft 产品或其他产品上尝试此操作时，看起来它没有使用稳定的排序，因此这个技巧不为人所知也就不足为奇了）。
If you have a GUI that allows people to sort on individual columns by clicking on that column, and you use a stable sort, then people who know can get a multi-column sort on columns A,B,C by clicking on columns C,B,A in that order. Because the sort is stable, when you click on B any records with equal keys under B will still be sorted by C so after clicking on B the records are sorted by B, C. Similarly, after you click on A, the records are sorted by A, B, C.
(Unfortunately, last time I tried this on some Microsoft product or other, it looked like it didn't use a stable sort, so it's not surprising this trick is not better known).
想象一下，您想要组织一副纸牌。您可以先按花色排序，然后按数值排序。如果你使用稳定排序，你就完成了。如果你使用不稳定的排序，那么它们会按数字顺序排列，但花色又会变得混乱。在实际的开发问题中会出现很多类似的情况。
Imagine that you wanted to organize a deck of cards. You could sort first by suit, then by numeric value. If you used a stable sort, you'd be done. If you used an unstable sort, then they'd be in numeric order, but the suits would be all messed up again. There are lots of equivalent situations that come up in real development problems.
只有少数情况需要稳定的排序算法。一个例子是，如果您正在实现基数排序之类的东西，这取决于用作构建块的比较排序算法是稳定的这一想法。 （基数排序可以在线性时间内进行操作，但它的输入比比较排序算法受到更多限制。（比较排序需要 O(n lg n) 时间））
不稳定的排序并不一定是“坏”的；相反，更重要的是，一种稳定的类型“在某些情况下是可取的”。这就是为什么编程语言（例如 C++ 的标准模板库）提供了这两种功能（例如
std::sort和std::stable_sort），它们允许您指定何时需要稳定性，当你不这样做时。There are just a few cases where you need a sort algorithm that's stable. An example of this is if you're implementing something like a Radix sort, which depends on the idea that the comparison sorting algorithm used as the building block is stable. (Radix sort can operate in linear time, but it's inputs are more restricted than comparison sorting algorithms. (Comparison sorts require O(n lg n) time))
It's not necessarily that a sort that is unstable is "bad"; it's more that a sort that is stable is "desirable in some cases". That's why programming languages, e.g. C++'s Standard Template Library, provide both -- e.g.
std::sortandstd::stable_sort-- which allow you to specify when you need stability, and when you don't.因为他们可以做得比我更好...来自 开发人员融合：
请注意，快速排序等排序算法不稳定或不稳定。实现将决定它是哪一个。
无论如何，稳定并不一定比不稳定更好或更差——只是有时你需要保证两个相等元素的顺序。当您确实需要这种保证时，unstable 就不适合。
Because they can do better than I could do...from Developer Fusion:
Note that sorting algorithms like quick sort are not stable or unstable. The implementation will determine which it is.
In any case, stable is not necessarily better or worse than unstable - it's just that sometimes you need the guarantee of the order to two equal elements. When you do need that guarantee, unstable would not be suitable.