如果两个具有相同键的对象在排序输出中以与在输入未排序数组中相同的顺序出现，则排序算法称为稳定的。一些排序算法本质上是稳定的，如插入排序，归并排序，冒泡排序等。有些排序算法不是，比如堆排序，快速排序等等。

然而，任何给定的不稳定排序算法都可以被修改为稳定排序算法。可以有排序算法特定的方法使其稳定，但一般来说，任何基于比较的排序算法本质上不稳定，都可以通过改变键比较操作来修改为稳定，以便两个键的比较将位置作为具有相同键的对象的一个因素。

引用: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

我知道这个问题有很多答案，但对我来说，罗伯特·哈维的这个答案总结得更清楚:

稳定排序是一种保留输入集原始顺序的排序，其中[不稳定]算法不区分两个或多个项。

源

如果两个具有相同键值的对象在排序输出中以与在待排序输入数组中相同的顺序出现，则排序算法称为稳定的。一些排序算法本质上是稳定的，如插入排序，归并排序，冒泡排序等。有些排序算法不是，比如堆排序，快速排序等等。

背景:一个“稳定的”排序算法使具有相同排序键的项保持有序。假设我们有一个5个字母的单词列表:

peach
straw
apple
spork

如果我们只根据每个单词的首字母对列表进行排序，那么稳定排序将产生:

apple
peach
straw
spork

在不稳定排序算法中，稻草和叉叉可能会互换，但在稳定排序算法中，它们的相对位置保持不变(即由于稻草在输入中出现在叉叉之前，因此在输出中也出现在叉叉之前)。

我们可以使用这个算法对单词列表进行排序:按第5列、第4列、第3列、第2列、第1列进行稳定排序。 最后，它将被正确排序。说服你自己。(顺便说一下，这个算法叫做基数排序)

现在来回答你的问题，假设我们有一个名字和姓氏的列表。我们被要求“先按姓，再按名”排序。我们可以先按名字排序(稳定或不稳定)，然后按姓氏排序。在这些排序之后，列表主要按照姓氏排序。但是，如果姓氏相同，则对名字进行排序。

你不能以同样的方式堆叠不稳定的类型。

稳定排序总是在相同的输入上返回相同的解(排列)。

例如，[2,1,2]将使用稳定排序作为排列[2,1,3](第一个是索引2，然后是索引1，然后是索引3)，这意味着输出总是以相同的方式洗牌。其他不稳定，但仍然正确的排列是[2,3,1]。

快速排序是不稳定的排序，同一元素之间的排列差异取决于选取枢轴的算法。有些实现是随机的，可以快速排序，使用相同的算法对相同的输入产生不同的排列。

稳定排序算法具有一定的确定性。

排序稳定性是指具有相同键的记录在排序前后保持相对顺序。

因此，当且仅当你要解决的问题需要保持相对顺序时，稳定性才重要。

如果你不需要稳定性，你可以从库中使用一个快速的、占用内存的算法，比如堆排序或快速排序，然后忘记它。

如果你需要稳定，那就更复杂了。稳定算法比不稳定算法具有更高的大o CPU和/或内存使用量。所以当你有一个大的数据集时，你必须在CPU和内存之间做出选择。如果CPU和内存都受到限制，就有问题了。一种较好的折衷稳定算法是二叉树排序;维基百科上有一个基于STL的c++实现，简单得可怜。

通过添加原始记录号作为每条记录的最后位置键，可以将不稳定的算法变为稳定的算法。

这取决于你做什么。

假设您有一些具有姓和名字段的人员记录。首先按名字排序。如果使用稳定的算法按姓氏对列表进行排序，那么您将得到一个按姓和名排序的列表。