为什么是一种“不稳定的那种”认为是不好的

只是想知道，如果有人可以解释为什么一个“不稳定的一种”被认为是坏？基本上我没有看到任何情况下它真的很重要。任何人都可以提供一个吗？为什么是一种“不稳定的那种”认为是不好的

2011-05-11 Maxim Gershkovich

谁认为它“不好”？你有报价或参考或链接？这将有助于为这种价值判断提供一些背景。 – 2011-05-11 03:18:51

可能的重复[有什么好处排序算法是稳定的？]（http://stackoverflow.com/questions/808617/what-is-the-benefit-for-a-sort-algorithm-tobe - 稳定） – nawfal 2014-06-13 15:59:47

如果你有一个图形用户界面，允许人们通过单击该列进行排序的单个列，并使用一个稳定的排序，那么谁知道人们可以列通过点击获得多列排序A，B，C在列C，B，A上依次排列。因为排序是稳定的，所以当你点击B时，在B下有相同键的任何记录仍然会被C排序，所以在点击B之后，记录按B，C排序。同样，在你点击A之后，记录被排序（不幸的是，上次我在某些微软产品或其他产品上试用过这款产品时，它看起来好像没有使用稳定的排序方式，所以这并不奇怪）。

来源

2011-05-11 03:56:06 mcdowella

很好的例子。但是，你的意思是说有一个微软产品不稳定？令人震惊！ :) – 2011-05-11 17:15:02

很高兴我读到这个。我不会想到这样的事情不会使用可靠的排序。 – 2012-08-14 14:34:07

但是，通过添加一个rownum/index或其他类型的唯一计数器作为复合排序键中的最后一个元素，总是不能稳定排序吗？除非我错过了一些东西，否则似乎微不足道。 – drake7707 2015-02-14 15:53:14

试想一下，你想组织的一副牌。您可以先按西装排序，然后按数字值排序。如果你使用稳定的排序，你就完成了。如果你使用了不稳定的排序，那么他们会按数字顺序排序，但套装会再次混乱。有很多相同的情况出现在实际的开发问题中。

来源

2011-05-11 03:11:45

我不认为这是一个很好的比较，因为任何比较函数都应考虑套装和数量。还要注意，如果你使用稳定的排序方法，你必须按数字排序，然后适合，但不是其他方式。 – 2011-05-11 03:15:40

我不是跟着你，@比利。首先，如果且没有稳定的排序，您需要一个比较函数来考虑这两个因素。否则，你可以有一个简单的比较函数，它在动态语言中可以一般地写成按名称排序。其次，你似乎觉得只有一种方法来组织一副牌。我向你保证，“组织”可以用多种方式来解释。 – 2011-05-11 04:02:33

只是有你需要一个排序算法这是稳定的少数情况下。一个例子就是如果你正在实现一个基类排序，这取决于用作构建块的比较排序算法是稳定的。（基数排序可以在线性时间内运行，但其输入比比较排序算法更受限制（比较排序需要O（n lg n）时间））

不一定不稳定的排序是“不好” ;更多的是稳定的那种“在某些情况下是可取的”。这就是编程语言的原因，例如C++的标准模板库，提供 - 例如std::sort和std::stable_sort - 可让您指定何时需要稳定性，何时不需要。

来源

2011-05-11 03:21:00

@Downvoter：这个答案究竟有什么问题？ – 2011-06-29 21:36:38

不知道谁是downvoted，但我想他们发现你使用稳定的排序来执行另一种排序的例子有点不典型。 – Mehrdad 2012-08-14 10:35:29

“，这取决于用作构建块的比较[基于]排序算法是稳定的想法” - 你在说什么？什么是基数排序的“构建块”，为什么它需要稳定？无论是否有意义，在某些情况下，排序并不是一个很好的例子，说明为什么稳定排序是可取的。 – Dukeling 2013-12-01 18:39:33

因为他们可以做得比我能做的......从Developer Fusion：

有两种排序算法0：“稳定排序”和 “不稳定排序”。这些术语是指当两个的值相等时所采取的操作。如果你有数组T0..size有两个元素Tn的和Tk对于n < K，和这两个元素比较平等，稳定排序它们将出现在与在Tn的价值排序输出在Tk之前的。输出订单保留原始输入订单。一个不稳定排序，相比之下，有没有输出这两个元素的顺序的保证。

需要注意的是，如快速排序排序算法并不稳定或不稳定。实施将决定它是哪一个。

在任何情况下，稳定不一定比不稳定好还是坏 - 它只是有时你需要的顺序的两个相等的元素的保证。当你做需要保证时，不稳定将不适合。

来源

2011-05-11 03:22:11 JasCav

我想OP理解这两种排序之间的区别是什么。他在问为什么一种不稳定的东西会是“坏的” - 这意味着他知道是什么使得一种不稳定的东西。 – 2011-05-11 03:23:07

@比利 - 非常真实。我想，为了更好的回答，我想明确说明它是什么，所以我可以说我的最后一段 - 除了特定情况下，其中一段不一定是“坏”或“好”。 – JasCav 2011-05-11 03:24:36

为什么是一种“不稳定的那种”认为是不好的

回答

相关问题