稳定性之所以重要，有几个原因。一个是，如果两个记录不需要交换，交换它们可能会导致内存更新，一个页面被标记为脏，并且需要重新写入磁盘(或其他慢介质)。

这取决于你做什么。

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

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

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

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

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

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

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

peach
straw
apple
spork

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

apple
peach
straw
spork

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

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

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

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

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

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

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

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

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

如果你假设你正在排序的只是数字，并且只有它们的值才能识别/区分它们(例如，具有相同值的元素是相同的)，那么排序的稳定性问题是没有意义的。

然而，排序中具有相同优先级的对象可能是不同的，有时它们的相对顺序是有意义的信息。在这种情况下，不稳定排序会产生问题。

例如，你有一个数据列表，其中包含所有玩家在游戏中使用关卡[L]清理迷宫的时间成本[T]。 假设我们需要根据玩家清理迷宫的速度来对他们进行排名。然而，这里还有一个附加规则:无论花费多长时间，以更高级别清理迷宫的玩家总是拥有更高的等级。

当然，你也可以尝试着将配对值[T,L]映射到一个实数[R]，然后根据[R]值对所有玩家进行排序。

然而，如果稳定排序是可行的，那么你可以简单地按照[T](更快的玩家优先)和[L]对整个列表进行排序。在这种情况下，玩家的相对顺序(根据时间成本)不会在你根据他们清理的迷宫级别对他们进行分组后发生改变。

PS:当然，对特定问题进行两次排序的方法并不是最好的解决方案，但对于解释海报的问题来说，这应该足够了。

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

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

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

稳定排序算法是将相同的元素按照它们在输入中出现的相同顺序进行排序，而不稳定排序可能不满足这种情况。-我感谢我的算法讲师Didem Gozupek提供了关于算法的见解。

我再次需要编辑这个问题，因为有些人没有理解演讲的逻辑。它演示了对w.r.t. first元素进行排序。另一方面，您可以考虑由键-值对组成的示例。

稳定排序算法:

插入排序 归并排序 冒泡排序 蒂姆排序 计数排序 块排序 Quadsort 图书馆分类 鸡尾酒摇酒器 Gnome排序 奇偶排序

不稳定排序算法:

堆排序 选择排序 壳类 快速排序 Introsort(受制于快速排序) 树的种类 循环排序 Smoothsort 比赛排序(以Hesapsort为准)

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

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

源

Some more examples of the reason for wanting stable sorts. Databases are a common example. Take the case of a transaction data base than includes last|first name, date|time of purchase, item number, price. Say the data base is normally sorted by date|time. Then a query is made to make a sorted copy of the data base by last|first name, since a stable sort preserves the original order, even though the inquiry compare only involves last|first name, the transactions for each last|first name will be in data|time order.

一个类似的例子是经典的Excel，它一次只能对3列进行排序。要对6列进行排序，首先对最低有效度的3列进行排序，然后对最高有效度的3列进行排序。

A classic example of a stable radix sort is a card sorter, used to sort by a field of base 10 numeric columns. The cards are sorted from least significant digit to most significant digit. On each pass, a deck of cards is read and separated into 10 different bins according to the digit in that column. Then the 10 bins of cards are put back into the input hopper in order ("0" cards first, "9" cards last). Then another pass is done by the next column, until all columns are sorted. Actual card sorters have more than 10 bins since there are 12 zones on a card, a column can be blank, and there is a mis-read bin. To sort letters, 2 passes per column are needed, 1st pass for digit, 2nd pass for the 12 11 zone.

后来(1937年)出现了卡片整理(合并)机，可以通过比较字段来合并两副牌。输入是两副已经排序的牌，一副主牌和一副更新牌。整理器将两个甲板合并为一个新的主箱和一个存档箱，存档箱可选地用于主副本，以便新的主箱在出现副本时只有更新卡。这可能是最初(自底向上)归并排序背后思想的基础。